Extrapolation methods for accelerating PageRank computations

By Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, Gene H. Golub. The Web Conference, 2003

515 citations recorded by the source corpus.

Subfields: Information Systems, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/1d7c27e8083a4bf89b6f3bfb91455ccf0a7efd84

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

In Statistical and Nonlinear Physics

Citations in the corpus

A Survey on PageRank Computing (2005, methodology): “Diﬀerent recipes for choosing c range from 0.85 [Page et al., 1998], [Kamvar et al., 2003b] to 0.99 [Haveliwala et al., 2003b], [Kamvar et al., 2003c].”
Adaptive methods for the computation of PageRank (2004, unknown): “We describe why the L1 residual is an appropriate measure in [7].”
Comparing top k lists (2003, methodology): “Kamvar, Haveliwala, Manning, and Golub [KHMG03] have used one of our distance measures in evaluating the quality of an approximate version of the PageRank ranking algorithm.”
On the Embeddability of Random Walk Distances (2013, unknown): “linear algebraic optimization [19, 29] and Monte Carlo approximation algorithms [13, 3].”
ItemRank: A Random-Walk Based Scoring Algorithm for Recommender Engines (2007, methodology): “…PageRank has been analysed in [Langville and Meyer, 2003] and custom static score distribution vectors d have been applied to compute topic-sensitive PageRank [Haveliwala, 2002], reputation of a node in a peerto-peer network [Kamvar et al., 2003b] and for combating web spam [Gyongyi et al., 2004].”
Fast Incremental and Personalized PageRank (2010, methodology): “A family of the methods proposed in this category deal with accelerating the basic power iteration method for computing PageRank values [20–22].”
Deeper Inside PageRank (2004, methodology): “In order to reduce the number of iterations required by the PageRank power method, Kamvar et al. [71] produced an extrapolation method derived from the classic Aitken’s ∆ 2 method.”
ObjectRank: Authority-Based Keyword Search in Databases (2004, background): “A set of works [17, 10, 22, 23] have tackled the problem of improving the performance of the original PageRank algorithm.”
Automatic performance tuning of sparse matrix kernels (2003, background): “Can this property be exploited to further improve A ρ· x performance by judiciously dropping edges in the tiled representation? Moreover, if it is known that an optimization like SpMM can run 2–7× faster, will this permit new PageRank-like algorithms for specific search contexts [150, 175], or enabl”
Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments (2005, methodology): “…ranking algorithms has been extensively studied by the web-search community for measuring the speed of convergence in PageRank computations [Kamvar et al. 03b], the distortion of PageRank encodings [Haveliwala 03], and the quality of rank-aggregation methods [Fagin et al. 03b, Fagin et al.…”
The Second Eigenvalue of the Google Matrix (2003, methodology): “Previous work on accelerating PageRank computations assumed R S was unknown [6].”
Exploiting the Block Structure of the Web for Computing (2003, methodology): “Also, it should be noted that the BlockRank algorithm can be used in conjunction with other methods of accelerating PageRank, such as Quadratic Extrapolation [11], or GaussSeidel [6, 1] (or both).”
Reinforcement Ranking (2013, methodology): “An efficient procedure for computing Page Rank is given in Algorithm 1 [22, 23].”
Combating Web Spam with TrustRank (2004, background): “tage is important since substantial effort has been spent on making PakeRank computations efficient with very large data sets (for instance, see [5, 8]).”