Updating pagerank with iterative aggregation
Updating pagerank with iterative aggregation
复制标题
DOI：
10.1145/1013367.1013491
复制
发表时间：
2004-05
期刊：
影响因子：
--
通讯作者：
A. Langville;C. D. Meyer
中科院分区：
文献类型：
--
作者：
A. Langville;C. D. Meyer
我们提出了一种更新PageRank向量的算法[1]。由于网络的规模，谷歌每月只更新其著名的PageRank向量。然而，Web的变化要频繁得多。加速PageRank计算可以导致搜索引擎检索到的网页的更新鲜，更准确的排名。它还可以使实时个性化排名的目标触手可及。在网络的两个小的子集，我们的算法更新PageRank仅使用25%和14%，分别由原来的PageRank算法所需的时间。我们的算法使用迭代聚合技术[7，8]来关注马尔可夫链的缓慢收敛状态。该算法最令人兴奋的特点是，它可以与其他PageRank加速方法结合，例如悬挂节点集块算法[6]，二次外推[4]和自适应PageRank [3]，以实现更大的加速比（当所有算法组合时，可能是60倍或更多的加速比）。每隔几周我们的解决方案利用马尔可夫链的迭代聚合原则的力量，允许更频繁地更新有价值的排名向量。
We present an algorithm for updating the PageRank vector [1]. Due to the scale of the web, Google only updates its famous PageRank vector on a monthly basis. However, the Web changes much more frequently. Drastically speeding the PageRank computation can lead to fresher, more accurate rankings of the webpages retrieved by search engines. It can also make the goal of real-time personalized rankings within reach. On two small subsets of the web, our algorithm updates PageRank using just 25% and 14%, respectively, of the time required by the original PageRank algorithm. Our algorithm uses iterative aggregation techniques [7, 8] to focus on the slow-converging states of the Markov chain. The most exciting feature of this algorithm is that it can be joined with other PageRank acceleration methods, such as the dangling node lumpability algorithm [6], quadratic extrapolation [4], and adaptive PageRank [3], to realize even greater speedups (potentially a factor of 60 or more speedup when all algorithms are combined). every few weeks. Our solution harnesses the power of iterative aggregation principles for Markov chains to allow for much more frequent updates to the valuable ranking vectors.