java - 使用 Map Reduce 查找靠近特定记录的所有记录

Question

我正在尝试实现一个 map reduce 程序来查找 2GB 数据集中的所有记录，这些记录彼此靠近（类似于每个记录及其邻居应该是输出）。接近，我的意思是欧几里得距离。在数据集中，每条记录都有一个 x 和 y 坐标。谁能建议我这样做的一些直觉。我知道地图应该发出每条记录，reduce 可以简单地对输入到它的列表中的每个条目运行一个双循环以查找邻居，但是有没有更好的解决方案，因为我的实现非常慢。提前致谢。

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)

process 函数只是将 elm2 作为邻居或将 elm1 作为 mongodb 数据库。我的 mongodb 数据库中的每条记录的结构如下

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

Answer 1

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