Local methods for estimating pagerank values

ABSTRACT

The Google search engine uses a method called PageRank, together with term-based and other ranking techniques, to order search results returned to the user. PageRank uses link analysis to assign a global importance score to each web page. The PageRank scores of all the pages are usually determined off-line in a large-scale computation on the entire hyperlink graph of the web, and several recent studies have focused on improving the efficiency of this computation, which may require multiple hours on a workstation.

However, in some scenarios, such as online analysis of link evolution and mining of large web archives such as the Internet Archive, it may be desirable to quickly approximate or update the PageRanks of individual nodes without performing a large-scale computation on the entire graph. We address this problem by studying several methods for efficiently estimating the PageRank score of a particular web page using only a small subgraph of the entire web. In our model, we assume that the graph is accessible remotely via a link database (such as the AltaVista Connectivity Server) or is stored in a relational database that performs lookups on disks to retrieve node and connectivity information. We show that a reasonable estimate of the PageRank value of a node is possible in most cases by retrieving only a moderate number of nodes in the local neighborhood of the node.

REFERENCES

• 1: Serge Abiteboul , Mihai Preda , Gregory Cobena, Adaptive on-line page importance computation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775192]
• 2: A. Arasu, J. Cho, H. Garcia-Molina, and S. Raghavan. Searching the web. ACM Transactions on Internet Technologies, 1(1), June 2001.
• 3: A. Arasu, J. Novak, Tomkins A, and J. Tomlin. Pagerank computation and the structure of the web: Experiments and algorithms. In Poster presentation at the 11th Int. World Wide Web Conference, May 2002.
• 4: Ricardo A. Baeza-Yates , Felipe Saint-Jean , Carlos Castillo, Web Structure, Dynamics and Page Quality, Proceedings of the 9th International Symposium on String Processing and Information Retrieval, p.117-130, September 11-13, 2002
• 5: Krishna Bharat , Andrei Broder , Monika Henzinger , Puneet Kumar , Suresh Venkatasubramanian, The connectivity server: fast access to linkage information on the Web, Proceedings of the seventh international conference on World Wide Web 7, p.469-477, April 1998, Brisbane, Australia
• 6: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 7: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 8: Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
• 9: Soumen Chakrabarti , Byron E. Dom , S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins , David Gibson , Jon Kleinberg, Mining the Web's Link Structure, Computer, v.32 n.8, p.60-67, August 1999 [doi>10.1109/2.781636]
• 10: Yen-Yu Chen , Qingqing Gan , Torsten Suel, I/O-efficient techniques for computing pagerank, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584882]
• 11: S. Chien, C. Dwork, R. Kumar, D. Simon, and D. Sivakumar. Link evolution: Analysis and algorithms. In Workshop on Algorithms and Models for the Web Graph, 2002.
• 12: Junghoo Cho , Hector Garcia-Molina , Lawrence Page, Efficient crawling through URL ordering, Proceedings of the seventh international conference on World Wide Web 7, p.161-172, April 1998, Brisbane, Australia
• 13: T.H. Haveliwala. Efficient computation of pagerank. Technical report, Stanford University, October 1999. Available at tt http://dbpubs.stanford.edu:8090/pub/1999-31.
• 14: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 15: Monika R. Henzinger , Allan Heydon , Michael Mitzenmacher , Marc Najork, On near-uniform URL sampling, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.295-308, June 2000, Amsterdam, The Netherlands
• 16: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 17: Sepandar D. Kamvar , Taher H. Haveliwala , Christopher D. Manning , Gene H. Golub, Extrapolation methods for accelerating PageRank computations, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775190]
• 18: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 19: Yanhong Li, Toward a Qualitative Search Engine, IEEE Internet Computing, v.2 n.4, p.24-29, July 1998 [doi>10.1109/4236.707687]
• 20: Marc Najork , Janet L. Wiener, Breadth-first crawling yields high-quality pages, Proceedings of the 10th international conference on World Wide Web, p.114-118, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371965]
• 21: Andrew Y. Ng , Alice X. Zheng , Michael I. Jordan, Stable algorithms for link analysis, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.258-266, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384003]
• 22: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Computer Science Department, Stanford University, 1999.
• 23: Gopal Pandurangan , Prabhakar Raghavan , Eli Upfal, Using PageRank to Characterize Web Structure, Proceedings of the 8th Annual International Conference on Computing and Combinatorics, p.330-339, August 15-17, 2002
• 24: M. Richardson and P. Domingos. The intelligent surfer: Probabilistic combination of link and content information in pagerank. In Advances in Neural Information Processing Systems, 2002.
• 25: Design and Implementation of a High-Performance Distributed Web Crawler, Proceedings of the 18th International Conference on Data Engineering, p.357, February 26-March 01, 2002

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services

General Terms:
Algorithms, Performance

Keywords:
external memory algorithms, link database, link-based ranking, out-of-core, pagerank, search engines