Как рассчитывается pagerank распределенным способом?

Я понимаю идею pagerank и реализовал ее (при чтении книги "программирование коллективного интеллекта" ).

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

Я нашел статью wiki, но это не объяснило многое.

Любые предложения о том, как это возможно? Кроме того, бонусный вопрос: является ли метод распространения распределенного pagerank исключительно для pagerank или может ли используемый метод применяться к другим алгоритмам машинного обучения, применяемым к графикам?

Ответ 1

Современный способ вычисления PageRank основан на структуре Google Pregel. Я почти уверен, что сейчас у них есть что-то более сложное, но это последнее опубликованное усилие.

Подробнее об этом читайте в исследовательском блоге. Или прочитайте опубликованную статью здесь.

Я работаю над версией Bulk Synchronous Parallel под названием Apache Hama. Существует также Apache Giraph, который исключительно фокусируется на графиках и множестве других.

Как упоминается mfrankli, существует также инфраструктура MapReduce (например, Apache Hadoop), которая может быть использована для вычисления PageRank, но она не эффективна для итеративных алгоритмов.

Примечательно, что оба решения (MapReduce и BSP) являются пакетными решениями, поэтому они могут использоваться для пересчета PageRank для полного веб-графика. Поскольку обновления Google намного быстрее, чем пакетные алгоритмы, вы можете ожидать, что они часто пересчитывают PageRank на подграфах.

Ответ 2

MapReduce предоставляет интересный фон и может прояснить, как ваш распараллеливать эту задачу.