hadoop mapreduce距離計算

Question

是否有使用hadoop map/reduce的距離計算實現。我試圖計算給定的一組點之間的距離。

尋找任何資源。

編輯

這是一個非常聰明的解決方案。我已經嘗試了一些如何使用第一種算法，並且幾乎獲得了我期待的內容。目前我並不擔心優化程序，但我的問題是dist（X，Y）函數不起作用。當我得到reducer上的所有點時，我無法遍歷迭代器上的所有點並計算距離。有人在stackoverflow.com告訴我，在hadoop上的迭代器是不同於正常的JAVA迭代器，我不知道這一點。但是如果我能找到一個簡單的方法來通過我的dist（）函數的迭代器，我可以使用第二個算法進行優化。

//This is your code and I am refering to that code too, just to make my point clear. 
map(x,y) { 
    for i in 1:N #number of points 
    emit(i, (x,y)) //i did exactly like this 

    reduce (i, X) 
    p1 = X[i] 
    for j in i:N 
     // here is my problem, I can't get the values from the Iterator. 
     emit(dist(X[i], X[j])) 

Answer 1

您需要對該數據集進行自加入。在蜂巢會是什麼樣子，那或多或少

select dist(P1.x,P1.y,P2.x, P2.y) from points P1 join points P2 on (True) where P1.x < P2.x or (P1.x = P2.x and P1.y < P2.y) 

功能DIST需要使用其他蜂巢的功能來實現，或者用Java編寫的，並添加作爲UDF。此外，我不確定True常數，但您可以將0 = 0寫入相同的效果。 where子句是爲了避免計算相同的距離兩倍或0距離。問題是：將Hive優化這種方式，你可以在Hadoop中仔細編程？我不確定。這是在Hadoop中

map(x,y) { 
    for i in 1:N #number of points 
    emit(i, (x,y)) 

reduce (i, X) 
    p1 = X[i] 
    for j in i:N 
    emit(dist(X[i], X[j])) 

草圖對於這個工作，你需要X去以某種順序排序的減速機，採用二次排序鍵例如通過X，然後由y（即不影響分組） 。通過這種方式，每個縮減器都會獲取所有點的副本，並在您嘗試生成的距離矩陣的列上工作。內存要求很小。您可以通過重新組織計算來交換一些通信內容，以便每個Reducer計算最終矩陣的方形子矩陣，只知道這些點的兩個子集並計算它們之間的距離。要做到這一點，你需要使你的觀點的明確順序，說你是存儲I，X，Y

map(i,x,y) { 
    for j in 1:N/k #k is size of submatrix 
    emit((i/k, j), ("row", (x,y))) 
    emit((j, i/k), ("col", (x,y))) 

reduce ((a,b), Z) 
    split Z in rows X and cols Y 
    for x in X 
    for y in Y 
    emit(dist(x,y)) 

在這種情況下，你可以看到地圖相僅發出2 * N * N/K點，而以前的算法發射N^2。在這裏，我們有（N/k）^ 2減速器與N對另一個。每個reducer必須在內存中保存k個值（使用輔助鍵技術使所有行都到達所有列之前的reducer），而之前只有2個。所以你看到有折衷，對於第二種算法，你可以使用參數k進行性能調整。

Answer 2

這個問題聽起來不太適合map-reduce，因爲你不能真正將它分解成片段並獨立計算每個片段。如果你可以有一個單獨的程序，生成你的點的完整圖形列表（x1，y1，x2，y2），那麼你可以做一個簡單的地圖來獲得距離。