基于mapreduce的knn连接方法

《基于mapreduce的knn连接方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于MapReduce的Knn连接方法----谢荣东论文观点展示Knn连接即K最近邻(kNN，k-NearestNeighbor)连接解决的问题：找出一个样本在特征空间中的k个最相邻的样本，根据其中的大多数属于某一个类别，来判断该样本也属于这个类别，并具有这个类别上样本的特性。不足之处：计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。H-BNLJ(HadoopBlockNestedLoopJoin)的方法简介：是一种直接的局部暴力解决KNN连接的算法，它利用MapReduc

2、e的循环嵌套算法。基本思想：把待连接的两个集合R和S分割成大小相等的n块，这里可以通过线性扫描的方法来进行，每个块中分别包含有

3、R

4、/n（或

5、S

6、/n）个元素。然后，在Map阶段，每个连接块包含一个来自于R的分割块一个来自于S的分割块（也就是总共有n2个连接块）。在Reduce阶段，采用了n2个reduce来处理每个mapper生成的中间结果。每个reduce在本地嵌套执行局部R和S的Knn连接，也就是，对每个局部块中的S通过嵌套循环找到在局部快中的R的knn。所有来自reduce的结果写入（n2）DFS文件再进行排序

7、。H-BNLJ的问题本质上是暴力解法未采用索引，当数据量大时，不能有效从外存（DFS）数据加载到内存中DSGMR-J（(DistributedSketchedGrid）引入分布式概略化网格索引来对数据进行划分和索引基本思想：先对数据进行网格化划分，根据R和S的变化范围生成m2个栅格，其中每个栅格的x和y变化范围为intervalx和intervaly。每个R或S中的元素根据它的x和y坐标确定所属的栅格。对每个栅格而言，我们分布地创建了对应于此栅格的分布式索引DSG。这样，每个reduce可以快速地通过本地DSG索引来发

8、现本地Knn而避免嵌套循环。R的空间范围:S的空间范围：相对应的空间范围：根据公式进行拓展，需要两次MapReduce基于R树的MapReduce-knn连接