как реализовать вычисление собственного значения с MapReduce/Hadoop?

решено ..... Когда у нас есть профиль обеспечения, тогда нам не нужна наша учетная запись разработчика, поскольку у нас есть сертификаты и профиль обеспечения, который дает нам мост учетных записей разработчика и разрешения устройств. Подписывание без проверки автоматически управляет подписью [ 110]

10
задан ShreevatsaR 23 December 2008 в 16:30
поделиться

5 ответов

Я подозреваю, что это тяжело для большинства матриц кроме тех w/специальных структур (например, разреженные матрицы или w/определенные составы блока). Существует слишком много связи между коэффициентами матрицы и собственными значениями.

PageRank использует очень разреженную матрицу специальной формы, и любые заключения из вычисления ее собственных значений почти наверняка не расширяются на общие матрицы. (редактирование: вот другая ссылка, которая выглядит интересной),

1
ответ дан 3 December 2019 в 20:44
поделиться

ПРЕАМБУЛА:

Учитывая правильную конфискацию имущества данных, можно было достигнуть результатов параллельных вычислений без полного набора данных на каждой машине.

Возьмите, например, следующий цикл:

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

Очевидно, цикл как тот выше становится чрезвычайно проблематичным (заметьте матричные индексаторы.), Но методы действительно существуют для того, чтобы развернуть эти типы циклов и создать эффективные параллельные алгоритмы.

ОТВЕТ:

Возможно, что Google разработал решение вычислить собственное значение, не поддерживая копию матрицы на всех ведомых компьютерах. - или Они использовали что-то как Монте-Карло или некоторый другой Алгоритм аппроксимации для разработки "достаточно близко" вычисления.

На самом деле я сказал бы даже, что Google перейдет в максимально большой из длин сделать любое вычисление требуемым для их алгоритма PageRank максимально эффективный. Когда Вы - беговые дорожки, такие как они, и это (заметьте кабель Ethernet), Вы не можете передавать большие наборы данных (100 с концертов), потому что это невозможно, учитывая их аппаратные ограничения товарных плат NIC.

После этих слов Google способен удивлять сообщество программиста, и их реализация могла совершенно отличаться.

ЗАКЛЮЧИТЕЛЬНАЯ ЧАСТЬ СООБЩЕНИЯ:

Некоторые хорошие ресурсы для параллельных вычислений включали бы OpenMP и MPI. Обе параллельных реализации приближаются к параллельным вычислениям от совсем других парадигм, некоторые из которых происходят от реализации машины (кластер по сравнению с распределенными вычислениями.)

6
ответ дан 3 December 2019 в 20:44
поделиться

PageRank решает проблему доминантного собственного вектора, итеративно находя стационарное состояние дискретного потока в сети.

Если матрица A NxM описывает вес канала (количество потока) от узла n до узел m, затем

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

В пределе, когда p сходится к стационарному состоянию (p_n + 1 = p_n), это проблема собственных векторов с собственным значением 1.

Алгоритм PageRank не требует удержания матрицы в памяти, но неэффективно на плотных (не разреженных) матрицах. Для плотных матриц MapReduce является неправильным решением - вам нужна локальность и широкий обмен между узлами - и вам следует вместо этого взглянуть на LaPACK, MPI и друзей.

Вы можете увидеть работающую реализацию pagerank в библиотеке wukong (потоковая передача hadoop для ruby) или в подмодуле Heranrix Pagerank .

9
ответ дан 3 December 2019 в 20:44
поделиться

Я могу ответить мне теперь. Алгоритм PageRank использует в своих интересах разреженную матрицу, где это должно сходиться в собственном значении с несколькими, самоумножаются. Таким образом, в практике PageRank, Отобразить/Уменьшить процедура действительна. Можно выполнить, умножение матриц в процедуре Карты и формируются, разреженная матрица в Уменьшают процедуру. Но для общего матричного открытия собственного значения, это - все еще хитрая проблема.

1
ответ дан 3 December 2019 в 20:44
поделиться

В проекте apache hama есть интересная реализация алгоритма собственных значений Якоби. Он работает на hadoop. Обратите внимание, что вращение происходит при сканировании матрицы, а не при уменьшении карты.

1
ответ дан 3 December 2019 в 20:44
поделиться
Другие вопросы по тегам:

Похожие вопросы: