使用Map Reduce查找所有记录接近特定记录

Question

我想实现一个map reduce程序来查找2GB数据集中彼此接近的所有记录（类似于每个记录及其邻居应该是输出）。靠近，我的意思是欧式距离。在数据集中，每个记录都有一个x和y坐标。任何人都可以建议我做一些直觉。我知道地图应该发出每条记录，并且reduce可以简单地运行一个double for循环中的每个条目输入它以找到邻居，但是有更好的解决方案，因为我的实现速度非常慢。提前致谢。

map(rid,r): 
emit(key,r) 

reduce(key,lst=[r1,r2....]): 
for elm1 in lst: 
    for elm2 in lst: 
    if elm2 is in range of elm1: 
    process(elm1,elm2) 

进程函数简单地将elm2作为邻居或elm1作为mongodb数据库。我的mongodb数据库中的每条记录的结构如下

记录'R'|记录'R'的邻居列表

Answer 1

您可以通过对桶中的记录建立索引来加速实施。假设您的所有记录都在网格[0,100] x [0，100]中。创建99个x桶[0,1]，[1,2]，... [99,100]和99个桶。对于给定的记录[x1，y1]和距离d，取x桶[x1 - d - 1]到[x1 + d + 1]和y桶[y1 - d - 1]到[ y1 + d + 1]，然后测试[x1，y1]的欧式距离与结果集中的点之间的距离。