Download presentation
Presentation is loading. Please wait.
1
基于MapReduce的Knn连接方法 ----谢荣东论文观点展示
2
Knn连接 即K最近邻(kNN，k-NearestNeighbor) 连接
3
H-BNLJ(Hadoop Block Nested Loop Join)的方法
简介：是一种直接的局部暴力解决KNN连接的算法，它利用 MapReduce的循环嵌套算法。 基本思想：把待连接的两个集合R和S分割成大小相等的n 块，这里可以通过线性扫描的方法来进行，每个块中分别 包含有|R|/n（或|S|/n）个元素。然后，在Map阶段，每个 连接块包含一个来自于R的分割块一个来自于S的分割块 （也就是总共有n2个连接块）。在Reduce阶段，采用了n2个 reduce来处理每个mapper生成的中间结果。每个reduce在本 地嵌套执行局部R和S的Knn连接，也就是，对每个局部块中 的S通过嵌套循环找到在局部快中的R的knn。所有来自 reduce的结果写入（n2）DFS文件再进行排序。
5
H-BNLJ的问题 本质上是暴力解法 未采用索引，当数据量大时，不能有效从外存（DFS）数 据加载到内存中
6
DSGMR-J（(Distributed Sketched Grid）
引入分布式概略化网格索引来对数据进行划分和索引 基本思想：先对数据进行网格化划分，根据R和S的变化 范围生成m2个栅格，其中每个栅格的x和y变化范围为 intervalx和intervaly。每个R或S中的元素根据它的x和y坐标 确定所属的栅格。对每个栅格而言，我们分布地创建了 对应于此栅格的分布式索引DSG。这样，每个reduce可以 快速地通过本地DSG索引来发现本地Knn而避免嵌套循 环。
7
R的空间范围: S的空间范围： 相对应的空间范围： 根据公式进行拓展，需要两次MapReduce
8
基于R树的MapReduce-knn连接
Similar presentations
