使用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]的歐式距離與結果集中的點之間的距離。