[HADOOP] hadoop에서 mapreduce 거리 계산

hadoop에서 mapreduce 거리 계산

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

어떤 자원을 찾고 있습니다.

편집하다

이것은 매우 지능적인 솔루션입니다. 나는 첫 번째 알고리즘과 같은 방법을 시도했으며, 내가 찾던 것을 거의 얻었습니다. 나는 현재 프로그램 최적화에 대해 걱정하지 않지만 내 문제는 dist (X, Y) 함수가 작동하지 않았다는 것입니다. 감속기의 모든 점을 얻었을 때 Iterator의 모든 점을 통과하여 거리를 계산할 수 없었습니다. stackoverflow.com의 누군가가 hadoop의 Iterator가 일반적인 JAVA Iterator와 다르다고 말했지만 확실하지 않습니다. 그러나 내 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])) 

해결법

1. ==============================

   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 거리로 계산하지 않는 것입니다. 문제는 : 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에 의해 2 차 정렬 키를 사용하여 (그룹화에 영향을 미치지 않는) 순서대로 정렬 된 감속기를 가져 가야합니다. 이 방법으로 모든 감속기는 모든 점의 복사본을 가져오고 생성하려는 거리 행렬의 열에서 작동합니다. 메모리 요구 사항은 최소입니다. 계산을 다시 구성하여 모든 리듀서가 최종 행렬의 정사각 하위 행렬을 계산하여 점의 두 가지 하위 집합 만 알고 그 사이의 거리를 계산하도록 메모리 통신을 교환 할 수 있습니다. 이를 달성하려면 포인트의 순서를 명시 적으로 만들어야합니다 .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이 있습니다. 각 리듀서는 k 값을 메모리에 보유해야합니다 (2 차 키 기술을 사용하여 모든 행이 모든 열보다 먼저 리듀서에 도달하도록). 따라서 절충 사항이 있으며 두 번째 알고리즘의 경우 성능 조정에 매개 변수 k를 사용할 수 있습니다.

2. ==============================

   2.이 문제는 실제로 조각으로 나눌 수 없으며 각 조각을 독립적으로 계산할 수 없으므로 맵 축소에 적합하지 않은 것으로 보입니다. 포인트의 전체 그래프를 목록 (x1, y1, x2, y2)으로 생성하는 별도의 프로그램이있을 경우 거리를 얻기 위해 간단한지도를 만들 수 있습니다.

   이 문제는 실제로 조각으로 나눌 수 없으며 각 조각을 독립적으로 계산할 수 없으므로 맵 축소에 적합하지 않은 것으로 보입니다. 포인트의 전체 그래프를 목록 (x1, y1, x2, y2)으로 생성하는 별도의 프로그램이있을 경우 거리를 얻기 위해 간단한지도를 만들 수 있습니다.

from https://stackoverflow.com/questions/3380135/mapreduce-distance-calculation-in-hadoop by cc-by-sa and MIT license