mapoduce에서의 거리 계산

Question

hadoop map/reduce를 사용한 거리 계산 구현이 있습니까? 주어진 점 집합 사이의 거리를 계산하려고합니다.

모든 자원을 찾고 있습니다.

편집

이것은 매우 지능적인 솔루션입니다. 나는 첫 번째 알고리즘과 같은 것을 시도해 보았고, 내가 찾던 것을 거의 얻을 수 있었다. 나는 현재 프로그램을 최적화하는 것에 대해 관심이 없지만 dist (X, Y) 함수가 작동하지 않는다는 것이 문제였습니다. 감속기의 모든 점을 얻었을 때, 반복기의 모든 점을 통과하지 못하고 거리를 계산할 수 없었습니다. stackoverflow.com에서 누군가가 hadoop의 Iterator가 정상적인 JAVA Iterator와 다르다는 것을 알았습니다. 그러나 내가 dist() 함수에서 Iterator를 통과하는 간단한 방법을 찾을 수 있다면 최적화를 위해 두 번째 알고리즘을 사용할 수 있습니다. 당신이 정말로 조각으로 나누고 각각 독립적으로 조각을 계산 할 수없는 때문에이 문제에 적합 같은 소리하지 않습니다

//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으로 추가 할 필요가있다. 또한 나는 진정한 상수에 대해 확신하지는 않지만 같은 효과에 0 = 0을 쓸 수 있습니다. where 절은 동일한 거리를 두 번 또는 0 번 계산하는 것을 피하는 것입니다. 문제는 다음과 같습니다 : 당신이 hadoop에서주의 깊게 프로그래밍 할 수있는 방식으로 하이브를 최적화 할 것입니까? 나는 잘 모르겠다. 이것은 당신이 (그룹화에 영향을주지 않는) 차 정렬 키를 사용하여 X에 의해 예를 들면 다음 Y로, X는 어떤 순서로 정렬 감속기에 도착해야 할 일이 들어 하둡

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])) 

의 스케치입니다 . 이렇게하면 모든 감속기가 모든 점의 복사본을 가져 와서 생성하려고하는 거리 행렬의 열에서 작동합니다. 메모리 요구량은 최소화되어 있습니다. 모든 감속기가 최종 행렬의 정사각형 부분 행렬을 계산하고 점의 두 부분 집합 만 알고 모든 행렬 간의 거리를 계산하도록 계산을 다시 구성하여 메모리에 대한 일부 통신을 교환 할 수 있습니다. 이를 위해, 당신은

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를 방출하는 것을 볼 수 있습니다 Y, 당신은 X를 난을 저장하는 말, 당신의 점을 명시 적으로 순서를 확인해야합니다 이전 알고리즘은 N^2를 방출했다. 여기에 (N/k)^2 감속기와 다른 감속기가 있습니다. 각 감속기는 메모리에서 k 값을 보유해야합니다 (2 차 키 기술을 사용하여 모든 행이 모든 열보다 먼저 감속기에 도달하도록 함). 따라서 트레이드 오프가 있음을 알 수 있으며 두 번째 알고리즘의 경우 perf k에 k 파라미터를 사용할 수 있습니다.

Answer 2

지도-줄일 수 있습니다. 목록의 전체 그래프를 목록 (x1, y1, x2, y2)으로 생성하는 별도의 프로그램을 만들 수 있다면 거리를 얻기 위해 직선적 인지도를 작성할 수 있습니다.