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

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

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

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


graph neo4j graph-theory pagerank
person Lostsoul    schedule 03.04.2012    source источник
comment
Я предполагаю, что Riak может обрабатывать большие числа и может проходить по ссылкам с помощью MapReduce.   -  person Jesvin Jose    schedule 03.04.2012

Ответы (1)


arrow_upward
5
arrow_downward

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

Итерационные методы для вычисления собственных векторов требуют, чтобы вы сохраняли несколько векторов на каждой итерации (каждый из них будет иметь 100 миллиардов элементов). Они могут поместиться на вашем компьютере (с 4-байтовыми поплавками вам потребуется около 375 ГБ на вектор). Когда у вас есть вектор-кандидат ранжирования, вы можете (очень медленно) применить к нему свою гигантскую матрицу, читая матрицу по частям (поскольку вы можете просматривать 32 миллиарда строк за раз, вам понадобится чуть более 3 частей). Повторите этот процесс, и у вас будут основы метода мощности, который используется в рейтинге страниц. 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

person dranxo    schedule 03.04.2012
comment
yikes .. кажется намного сложнее, чем я надеялся. Я надеялся, что есть решение, которое позволит мне взять рейтинг страницы из предыдущего набора данных и применить это свойство к текущему набору (поскольку меня волнует только рейтинг страницы текущего набора узлов). Мне потребуется некоторое время, чтобы переварить то, что вы написали, но я прочитаю эти документы. - person Lostsoul; 03.04.2012
comment
Поскольку рейтинг страницы зависит от всей сети, я не думаю, что вы можете легко игнорировать старые данные при поиске обновленного рейтинга. Инкрементные методы решают эту проблему (см. последнюю ссылку), но я не знаю, сможете ли вы обойтись без чего-то сложного. - person dranxo; 03.04.2012