Найти все записи рядом с определенной записью, используя Map Уменьшить

Question

Я пытаюсь реализовать программу уменьшения карты, чтобы найти все записи в наборе данных 2 ГБ, которые близки друг другу (что-то вроде каждой записи и ее соседей должно быть выходом). Близко, я имею в виду эвклидово расстояние. В наборе данных каждая запись имеет координату x и y. Может ли кто-нибудь предложить мне какую-то интуицию для этого. Я знаю, что карта должна излучать каждую запись, а сокращение может просто запустить double для цикла каждой записи в списке, введенном для нее, чтобы найти соседей, но есть ли лучшее решение для этого, так как моя реализация ужасно медленная. Заранее спасибо.

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 y-buckets. Для данной записи [x1, y1] и расстояния d возьмем пересечение x-ведер [x1-d-1] с [x1 + d + 1] и y-ведрами [y1-d-1] до [ y1 + d + 1], а THEN проверит эвклидовое расстояние [x1, y1] против точек в полученном наборе.