Stanford InfoLab Publication Server

Computing PageRank using Power Extrapolation

Haveliwala, Taher and Kamvar, Sepandar and Klein, Dan and Manning, Chris and Golub, Gene (2003) Computing PageRank using Power Extrapolation. Technical Report. Stanford.




We present a novel technique for speeding up the computation of PageRank, a hyperlink-based estimate of the ``importance'' of Web pages, based on the ideas presented in "Extrapolation Methods for Accelerating PageRank Computations". The original PageRank algorithm uses the Power Method to compute successive iterates that converge to the principal eigenvector of the Markov matrix representing the Web link graph. The algorithm presented here, called Power Extrapolation, accelerates the convergence of the Power Method by subtracting off the error along several nonprincipal eigenvectors from the current iterate of the Power Method, making use of known nonprincipal eigenvalues of the Web hyperlink matrix. Empirically, we show that using Power Extrapolation speeds up PageRank computation by 30% on a Web graph of 80 million nodes in realistic scenarios over the standard power method, in a way that is simple to understand and implement.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:PageRank, link analysis, search
Subjects:Computer Science
Computer Science > Databases and the Web
Related URLs:Project Homepage, Project Homepage, Project Homepage,,
ID Code:605
Deposited By:Import Account
Deposited On:15 Jul 2003 17:00
Last Modified:24 Dec 2008 10:05

Download statistics

Repository Staff Only: item control page