基于MapReduce的knn連接方法課件

1、基于MapReduce的Knn連接方法-謝榮東論文觀點(diǎn)展示基于MapReduce的Knn連接方法-謝榮東論文觀點(diǎn)Knn連接即K最近鄰(kNN，k-NearestNeighbor)連接解決的問(wèn)題：找出一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本，根據(jù)其中的大多數(shù)屬于某一個(gè)類別，來(lái)判斷該樣本也屬于這個(gè)類別，并具有這個(gè)類別上樣本的特性。不足之處：計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。Knn連接即K最近鄰(kNN，k-NearestNeighbH-BNLJ(Hadoop Block Nested Loop Join)的方法簡(jiǎn)介：是一種直接的局部暴力解決

2、KNN連接的算法，它利用MapReduce的循環(huán)嵌套算法?；舅枷耄喊汛B接的兩個(gè)集合R和S分割成大小相等的n塊，這里可以通過(guò)線性掃描的方法來(lái)進(jìn)行，每個(gè)塊中分別包含有|R|/n（或|S|/n）個(gè)元素。然后，在Map階段，每個(gè)連接塊包含一個(gè)來(lái)自于R的分割塊一個(gè)來(lái)自于S的分割塊（也就是總共有n2個(gè)連接塊）。在Reduce階段，采用了n2個(gè)reduce來(lái)處理每個(gè)mapper生成的中間結(jié)果。每個(gè)reduce在本地嵌套執(zhí)行局部R和S的Knn連接，也就是，對(duì)每個(gè)局部塊中的S通過(guò)嵌套循環(huán)找到在局部快中的R的knn。所有來(lái)自reduce的結(jié)果寫入（n2）DFS文件再進(jìn)行排序。H-BNLJ(Hadoop Blo

3、ck Nested Loo基于MapReduce的knn連接方法課件H-BNLJ的問(wèn)題本質(zhì)上是暴力解法未采用索引，當(dāng)數(shù)據(jù)量大時(shí)，不能有效從外存（DFS）數(shù)據(jù)加載到內(nèi)存中H-BNLJ的問(wèn)題本質(zhì)上是暴力解法DSGMR-J（(Distributed Sketched Grid）引入分布式概略化網(wǎng)格索引來(lái)對(duì)數(shù)據(jù)進(jìn)行劃分和索引 基本思想：先對(duì)數(shù)據(jù)進(jìn)行網(wǎng)格化劃分，根據(jù)R和S的變化范圍生成m2個(gè)柵格，其中每個(gè)柵格的x和y變化范圍為intervalx和intervaly。每個(gè)R或S中的元素根據(jù)它的x和y坐標(biāo)確定所屬的柵格。對(duì)每個(gè)柵格而言，我們分布地創(chuàng)建了對(duì)應(yīng)于此柵格的分布式索引DSG。這樣，每個(gè)reduce可以快速地通過(guò)本地DSG索引來(lái)發(fā)現(xiàn)本地Knn而避免嵌套循環(huán)。DSGMR-J（(Distributed Sketched R的空間范圍:S的空間范圍：相對(duì)應(yīng)的空間范圍：根據(jù)公式進(jìn)行拓展，需要兩次MapReduceR的空間范圍:基于R樹(shù)的MapReduce-knn連接基于R樹(shù)的MapReduce-knn連接基于MapReduce的knn連接方法課件基于MapRe