Можно ли сделать PageRank без всего набора данных? - PullRequest
Новая
       52

Можно ли сделать PageRank без всего набора данных?

6 голосов
/ 03 апреля 2012

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

Можно ли каким-то образом взять предыдущие оценки PageRank и применить их кновые наборы данных (я забочусь только о поиске страниц для самого последнего набора данных, но мне нужен просмотр страницы предыдущего набора для получения данных последних наборов)?

Имеет ли это смысл?Если да, то можно ли это сделать?

1 Ответ

5 голосов
/ 03 апреля 2012

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

Итерационные методы для вычисления собственных векторов требуют, чтобы вы сохраняли только несколько векторов вкаждая итерация (у каждого будет 100 миллиардов элементов).Они могут уместиться на вашей машине (с 4-х байтовыми числами вам потребуется около 375 ГБ на вектор).Как только у вас есть вектор ранжирования-кандидата, вы можете (очень медленно) применить к нему свою гигантскую матрицу, читая матрицу порциями (поскольку вы можете просматривать 32 миллиарда строк за раз, вам потребуется чуть более 3 порций).Повторите этот процесс, и вы получите основы метода power, который используется в PageRank.cf http://www.ams.org/samplings/feature-column/fcarc-pagerank и http://en.wikipedia.org/wiki/Power_iteration

Конечно, ограничивающим фактором здесь является количество проверок матрицы.Оказывается, что, сохраняя более одного вектора-кандидата и используя некоторые рандомизированные алгоритмы, вы можете получить хорошую точность при меньшем количестве чтений ваших данных.Это актуальная тема исследований в мире прикладной математики.Вы можете найти больше информации здесь http://arxiv.org/abs/0909.4061, здесь http://arxiv.org/abs/0909.4061 и здесь http://arxiv.org/abs/0809.2274.Здесь доступен код: http://code.google.com/p/redsvd/, но вы не можете просто использовать его в готовом виде для тех объемов данных, о которых вы говорите.

Еще один способ сделать это - посмотретьв "добавочный SVD", который может удовлетворить вашу проблему лучше, но немного сложнее.Обратите внимание на эту заметку: http://www.cs.usask.ca/~spiteri/CSDA-06T0909e.pdf и этот форум: https://mathoverflow.net/questions/32158/distributed-incremental-svd

...