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

Question

我正在尝试实现一个 map 缩减程序，以查找 2GB 数据集中彼此接近的所有记录(例如每个记录及其邻居应该是输出)。我所说的接近是指欧氏距离。在数据集中，每个记录都有一个 x 和 y 坐标。谁能建议我一些这样做的直觉。我知道映射应该发出每条记录，而reduce 可以简单地对输入到它的列表中的每个条目运行一个双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)

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] 与结果集中的点的欧氏距离。