algorithm - función - mapreduce google

cómo implementar el cálculo del valor propio con MapReduce/Hadoop?

Question

Es posible porque PageRank era una forma de valor propio y es por eso que se introdujo MapReduce. Pero parece que hay problemas en la implementación real, como que cada computadora esclava tiene que mantener una copia de la matriz.

Answer 1

Sospecho que es intratable para la mayoría de las matrices, excepto las que tienen estructuras especiales (por ejemplo, matrices dispersas o las que tienen ciertos patrones de bloques). Hay demasiado acoplamiento entre los coeficientes de la matriz y los valores propios.

PageRank usa una matriz muy dispersa de una forma especial, y cualquier conclusión a partir del cálculo de sus valores propios casi con certeza no se extiende a las matrices generales. (editar: aquí hay otra referencia que parece interesante)

Answer 2

PREÁMBULO :

Dado el correcto secuestro de datos, se podrían obtener resultados informáticos paralelos sin un conjunto de datos completo en cada máquina.

Tomemos por ejemplo el siguiente ciclo:

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

Y dado una matriz del siguiente diseño:

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

Existen construcciones paralelas tales que la columna J se puede enviar a cada computadora y las columnas individuales se calculan en paralelo. La parte difícil de la paralelización viene cuando tienes bucles que contienen dependencias.

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

Obviamente, un bucle como el anterior se vuelve extremadamente problemático (observe los indexadores de matrices). Pero existen técnicas para desenrollar estos tipos de bucles y crear algoritmos paralelos efectivos.

RESPUESTA :

Es posible que Google haya desarrollado una solución para calcular un valor propio sin mantener una copia de la matriz en todas las computadoras esclavas. O bien, usaron algo como Monte Carlo o algún otro Algoritmo de aproximación para desarrollar un cálculo "lo suficientemente cerca".

De hecho, iría tan lejos como para decir que Google habrá hecho todo lo posible para hacer que cualquier cálculo requerido para su algoritmo de PageRank sea lo más eficiente posible. Cuando está ejecutando máquinas como estas y esto (observe el cable Ethernet) no puede transferir grandes conjuntos de datos (cientos de gig) porque es imposible dadas las limitaciones de hardware de las tarjetas NIC básicas.

Dicho esto, Google es bueno para sorprender a la comunidad de programadores y su implementación podría ser completamente diferente.

POSTAMBLE :

Algunos buenos recursos para computación paralela incluirían OpenMP y MPI . Ambas implementaciones paralelas abordan la informática paralela desde paradigmas muy diferentes, algunos de los cuales se derivan de la implementación de la máquina (clúster frente a computación distribuida).

Answer 3

Puedo responderme a mí mismo ahora. El algoritmo de PageRank aprovecha una matriz dispersa donde debe converger en el valor propio con varias auto-multiplicaciones. Por lo tanto, en la práctica de PageRank, el procedimiento de Mapa / Reducir es válido. Puede realizar una multiplicación de matriz en el procedimiento Map y formar una matriz dispersa en el procedimiento Reducir. Pero para el hallazgo de valores propios de la matriz general, sigue siendo un problema difícil.

Answer 4

PageRank resuelve el problema del autovector dominante al encontrar iterativamente la condición de flujo discreto de estado estable de la red.

Si la matriz A de NxM describe el peso del enlace (cantidad de flujo) desde el nodo n al nodo m, entonces

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

En el límite donde p ha convergido a un estado estable (p_n + 1 = p_n), este es un problema de autovector con valor propio 1.

El algoritmo PageRank no requiere que la matriz se mantenga en la memoria, pero es ineficiente en matrices densas (no dispersas). Para matrices densas, MapReduce es la solución incorrecta, necesita localidad e intercambio amplio entre nodos, y debería mirar a LaPACK y MPI y sus amigos.

Puede ver una implementación de pagerank en funcionamiento en la biblioteca wukong (hadoop streaming para ruby) o en el submódulo de pagerank de Heretrix . (El código heretrix se ejecuta independientemente de Heretrix)

(descargo de responsabilidad: soy un autor de wukong.)

Answer 5

El proyecto apache hama tiene una implementación interesante del algoritmo de valor propio de Jacobi. Funciona en hadoop. Tenga en cuenta que la rotación ocurre en el escaneo de la matriz no en el mapa de reducir.