come implementare il calcolo degli autovalori con MapReduce/Hadoop?

Question

È possibile perché PageRank era una forma di autovalore ed è per questo che è stata introdotta MapReduce. Ma ci sono problemi nell'attuazione reale, come ogni computer slave deve mantenere una copia della matrice?

Answer 1

PREAMBOLO:

Dato il diritto di sequestro dei dati, si potrebbe ottenere risultati di calcolo parallelo senza un set di dati completo su ogni macchina.

Prendiamo ad esempio il seguente ciclo:

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

E data una matrice del seguente schema:

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

costrutti paralleli esistono tale che la colonna J può essere inviato a ciascun computer e la le singole colonne sono calcolate in parallelo. La parte difficile della parallelizzazione viene quando hai loop che contengono dipendenze.

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]; 
    } 
} 

Ovviamente un anello come quello sopra diventa estremamente problematico (notare le indicizzatori matrice.) Ma esistono tecniche di svolgimento questi tipi di cicli e creando algoritmi paralleli efficaci.

RISPOSTA:

È possibile che google ha sviluppato una soluzione per calcolare un autovalore senza mantenere una copia della matrice in tutti i computer slave. -Oppure hanno usato qualcosa come Monte Carlo o qualche altro Approximation Algorithm per sviluppare un calcolo "abbastanza vicino".

In effetti, andrei così lontano da dire che Google si è adoperato per quanto possibile per rendere qualsiasi calcolo necessario per il proprio algoritmo PageRank il più efficiente possibile. Quando si eseguono macchine come these e this (notare il cavo Ethernet) non è possibile trasferire set di dati di grandi dimensioni (100s di concerti) perché è impossibile, date le loro limitazioni hardware delle schede NIC di base.

Detto questo, Google è bravo a sorprendere la comunità dei programmatori e la loro implementazione potrebbe essere completamente diversa.

Postambolo:

Alcune buone risorse per il calcolo parallelo dovrebbe includere OpenMP e MPI. Entrambe le implementazioni parallele si avvicinano al calcolo parallelo da paradigmi molto diversi, alcuni dei quali derivano dall'implementazione della macchina (cluster vs calcolo distribuito)

Answer 2

Sospetto che sia intrattabile per la maggior parte delle matrici tranne quelle con strutture speciali (ad esempio matrici sparse o quelle con determinati schemi di blocco). C'è troppo legame tra i coefficienti di matrice e gli autovalori.

PageRank utilizza molto un sparse matrix di un modulo speciale e le conclusioni del calcolo dei suoi autovalori quasi certamente non si estendono alle matrici generali. (modifica: ecco another reference che sembra interessante)

Answer 3

Posso rispondere ora a me stesso.L'algoritmo PageRank sfrutta la matrice sparsa in cui convergere al valore autovalore con diverse auto-moltiplicazione. Pertanto, nella pratica PageRank, la procedura Mappa/Riduzione è valida. È possibile eseguire la moltiplicazione della matrice nella procedura Mappa e formare una matrice sparsa nella procedura Riduci. Ma per l'individuazione di autovalori a matrice generale, è ancora un problema complicato.

Answer 4

PageRank risolve il problema dell'autenticatore dominante individuando in modo iterativo la condizione di flusso discreto a regime costante della rete.

Se NxM matrice A descrive il peso di collegamento (quantità di flusso) dal nodo n al nodo m, quindi

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

Nel limite in cui p converge ad uno stato stabile (p_n + 1 = p_n) , questo è un problema di autovettore con autovalore 1.

L'algoritmo PageRank non richiede la matrice da conservare in memoria, ma è inefficiente su matrici dense (non sparse). Per le matrici fitte, MapReduce è la soluzione sbagliata: hai bisogno di una località e di un ampio scambio tra i nodi - e dovresti invece guardare LaPACK, MPI e gli amici.

si può vedere un implementazione pagerank di lavoro nel (streaming Hadoop per Ruby) wukong library o nel Heretrix pagerank submodule. (Il codice viene eseguito indipendentemente heretrix Heretrix)

(disclaimer: io sono un autore di Wukong.)

Answer 5

L'apache hama progetto ha alcune interessanti implementazione dell'algoritmo autovalore Jacobi. Funziona su hadoop. Nota la rotazione avviene nella scansione della matrice non nella mappa riduci.