| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/2003-45 | ||
| Submitted on | 16th of July 2003 | ||
| Author | Haveliwala, Taher; Kamvar, Sepandar; Klein, Dan; Manning, Chris; Golub, Gene | ||
| Title | Computing PageRank using Power Extrapolation | ||
| Date of publication | 2003 | ||
| Published in | Stanford University Technical Report | ||
| Citation | Haveliwala, Taher; Kamvar, Sepandar; Klein, Dan; Manning, Chris; Golub, Gene. Computing PageRank using Power Extrapolation, Stanford University Technical Report, 2003. | ||
| Number of pages | 12 | ||
| Language | English | ||
| Project | Stanford InfoLab; Database Group; Natural Language Processing Group | ||
| Type | Technical Report | ||
| Subject group | Computer Science; Databases and the Web; Miscellaneous | ||
| Abstract | 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. | ||
| Keywords | PageRank, link analysis, search | ||
| Contact address |
taherh@stanford.edu sdkamvar@stanford.edu klein@cs.stanford.edu | ||
| Sponsored by |
This paper is based on work supported in part by the National Science Foundation under Grants No.\ IIS-0085896 and CCR-9971010, and in part by the Research Collaboration between NTT Communication Science Laboratories, Nippon Telegraph and Telephone Corporation and CSLI, Stanford University (research project on Concept Bases for Lexical Acquisition and Intelligently Reasoning with Meaning). | ||
| Fulltext source |
| Management of the document by | siroker@db.stanford.edu
| |