基于MapReduce的knn連接方法課件

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

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

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