MapReduce/Hadoop을 사용하여 고유 값 계산을 구현하는 방법은 무엇입니까?

Question

PageRank가 고유 값의 한 형태이므로 MapReduce가 도입 된 이유는 이것이 가능합니다. 그러나 모든 슬레이브 컴퓨터가 매트릭스 사본을 유지해야하는 것과 같이 실제 구현에는 문제가있는 것 같습니다.

Answer 1

PREAMBLE : 데이터의 적절한 격리 주어

, 하나는 모든 시스템의 완전한 세트없이 병렬로 연산 결과를 얻을 수 있었다. 예

취하는 다음 루프 :

for (int i = 0; i < m[].length; i++) 
{ 
    for (int j = 0; j < m[i].length; j++) 
    { 
     m[i][j]++; 
    } 
} 

다음 레이아웃 매트릭스 주어진 :

 j=0 j=1 j=2 
i=0 [ ] [ ] [ ] 
i=1 [ ] [ ] [ ] 
i=2 [ ] [ ] [ ] 

병렬 구조는 존재 J 열의 각 컴퓨터 및 전송 될 수있다 단일 열은 병렬로 계산됩니다. 병렬화의 어려운 부분은 종속성을 포함하는 루프가있을 때입니다.

for (int i = 0; i < m[].length; i++) 
{ 
    for (int j = 0; j < m[i].length; j++) 
    { 
     //For obvious reasons, matrix index verification code removed 
     m[i][j] = m[i/2][j] + m[i][j+7]; 
    } 
} 

분명 같은 루프는 상기 (매트릭스 인덱서 알.) 매우 문제가된다하지만 기술 루프 이러한 유형의 풀림 효과적인 병렬 알고리즘을 만들기 위해 존재한다.

ANSWER :

가 Google 모든 슬레이브 컴퓨터 행렬의 카피를 유지하지 않고 고유 값을 계산하기위한 솔루션을 개발하는 것이 가능하다. 또는 그들은 Monte Carlo 또는 다른 Approximation Algorithm과 같은 것을 사용하여 "close enough"계산을했습니다.

사실 Google은 PageRank 알고리즘에 필요한만큼의 계산을 가능한 한 효율적으로 수행 할 수 있도록 최대한 길게 갈 것이라고 말하고 있습니다. these과 this (이더넷 케이블에주의)과 같은 기계를 운영 할 때, 상용 NIC 카드의 하드웨어 제한 사항을 감안할 때 대량 데이터 세트 (100 기가)를 전송할 수 없습니다.

Google은 프로그래머 커뮤니티가 놀랍고 자신의 구현이 완전히 다를 수 있다는 점을 잘 알고 있습니다.

꼬리말는 :

병렬 컴퓨팅을위한 좋은 자원 OpenMP 및 MPI 포함됩니다. 두 가지 병렬 구현은 매우 다른 패러다임에서 병렬 컴퓨팅에 접근합니다. 일부는 기계 구현 (클러스터 대 분산 컴퓨팅)에서 유래합니다.

Answer 2

특수 구조 (예 : 희소 행렬 또는 1)와 같은 대부분의 행렬에서는 다루기가 쉽지 않습니다. 특정 블록 패턴 포함). 행렬 계수와 고유치 사이에 너무 많은 결합이 있습니다.

PageRank는 특별한 형태의 매우 sparse matrix을 사용하며, 고유 값 계산의 결론은 일반적인 매트릭스로 거의 확장되지 않습니다. (편집 : 여기에 재미있어 보이는 another reference입니다)

Answer 3

나는 지금 스스로 대답 할 수 있습니다.페이지 랭크 (PageRank) 알고리즘은 자체 곱셈을 사용하여 고유 값에서 수렴해야하는 희소 매트릭스를 활용합니다. 따라서 PageRank 연습에서는 Map/Reduce 절차가 유효합니다. Map 프로 시저에서 행렬 곱하기를 수행하고 Reduce 프로 시저에서 희소 행렬을 형성 할 수 있습니다. 그러나 일반적인 행렬 고유치를 찾는 경우에도 여전히 까다로운 문제입니다.

Answer 4

PageRank는 네트워크의 정상 상태 이산 흐름 조건을 반복적으로 찾아 냄으로써 지배적 인 고유 벡터 문제를 해결합니다. 하여 N × M 행렬 A는 P는 정상 상태 (p_n + 1 = p_n)에 수렴 한계에이어서,

p_{n+1} = A . p_{n} 

를 m을 노드 n 노드로부터 링크 가중치 (유동의 양)을 설명하면

페이지 랭크 알고리즘은 행렬을 메모리에 보유 할 필요는 없지만 밀도가 높은 (비 스파 스) 행렬에서는 비효율적입니다. 밀도가 높은 행렬의 경우 MapReduce가 잘못된 솔루션입니다. 노드 간 지역 및 광범위한 교환이 필요하며 대신 LaPACK 및 MPI 및 친구들을 살펴 봐야합니다.

wukong library (루비에 대한 하프 루프 스트리밍) 또는 Heretrix pagerank submodule에서 작동중인 PageRank 구현을 볼 수 있습니다.

(면책 조항 : 나는 wukong의 저자입니다.)합니다 (heretrix 코드는 독립적으로 Heretrix의 실행)

Answer 5

그 파일은 아파치 hama 프로젝트는 코비 고유 알고리즘의 몇 가지 흥미로운 구현이있다. 그것은 hadoop에서 실행됩니다. 지도가 축소되지 않은 행렬 스캔에서 회전이 발생합니다.