Stanford Personalized PageRank Project

---

Overview

The PageRank algorithm, as used by the Google search engine, exploits the linkage structure of the web to compute global "importance" scores that can be used to influence the ranking of search results. While the use of PageRank has proven very effective, the web's rapid growth in size and diversity drives an increasing demand for greater flexibility in ranking. Ideally, each user should be able to define his own notion of importance for each individual query. While in principle a personalized version of the PageRank algorithm can achieve this task, its naive implementation requires computing resources far beyond the realm of feasibility. During 2002-2003, this project developed algorithms and techniques for the goal of scalable, online personalized web search. The focus was on the efficient computation of personalized variants of PageRank.

This research project was part of the Stanford Global Infobase Project, supported by NSF.

The members of the Stanford PageRank Project spun off to form the company Kaltix to commercialize personalized web search technologies. After a brief life, Kaltix was acquired by Google in late 2003.

People

• Taher Haveliwala, PhD Candidate, Computer Science
• Glen Jeh, PhD Candidate, Computer Science
• Sepandar Kamvar, PhD Candidate, Scientific Computing and Computational Mathematics
  
  
• Hector Garcia-Molina, Professor, Computer Science and Electrical Engineering
• Gene Golub, Professor, Computer Science and Scientific Computing and Computational Mathematics
• Christopher Manning, Assistant Professor, Computer Science and Linguistics
• Rajeev Motwani, Professor, Computer Science
• Jeff Ullman, Professor, Computer Science
• Jennifer Widom, Associate Professor, Computer Science
  
  
• Ian Spiro, Undergraduate, Computer Science, Webmaster

Affiliations

Stanford Database Group
Stanford Natural Language Processing Group
Stanford Scientific Computing and Computational Mathematics
Stanford Webbase Project

Publications

Taher Haveliwala, Sepandar Kamvar, Dan Klein, Christopher Manning, and Gene Golub. Computing PageRank using Power Extrapolation , Preprint, July 2003.

Taher Haveliwala, Sepandar D. Kamvar, and Glen Jeh. An Analytical Comparison of Approaches to Personalizing PageRank , Preprint, June 2003.

Sepandar D. Kamvar and Taher H. Haveliwala, The Condition Number of the PageRank Problem , Preprint, June 2003.

Taher H. Haveliwala and Sepandar D. Kamvar, The Second Eigenvalue of the Google Matrix , Preprint, April 2003.

Sepandar D. Kamvar, Taher H. Haveliwala, and Gene H. Golub. Adaptive Methods for the Computation of PageRank , Accepted to the International Conference on the Numerical Solution of Markov Chains, September 2003.

Glen Jeh and Jennifer Widom. Scaling Personalized Web Search , In Proceedings of the Twelfth International World Wide Web Conference, May 2003. (Best Paper Award)

Taher H. Haveliwala, Efficient Encodings for Document Ranking Vectors , Accepted to the International Conference on Internet Computing, June, 2003.

Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, and Gene H. Golub. Extrapolation Methods for Accelerating PageRank Computations In Proceedings of the Twelfth International World Wide Web Conference, May 2003.

Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, and Gene H. Golub. Exploiting the Block Structure of the Web for Computing PageRank , Preprint, March, 2003.

Taher H. Haveliwala, Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search IEEE Transactions on Knowledge and Data Engineering, 2003.

Taher H. Haveliwala, Topic-Sensitive PageRank In Proceedings of the Eleventh International World Wide Web Conference, May 2002. (Best Student Paper Award)