Topic-sensitive PageRank

ABSTRACT

In the original PageRank algorithm for improving the ranking of search-query results, a single PageRank vector is computed, using the link structure of the Web, to capture the relative "importance" of Web pages, independent of any particular search query. To yield more accurate search results, we propose computing a set of PageRank vectors, biased using a set of representative topics, to capture more accurately the notion of importance with respect to a particular topic. By using these (precomputed) biased PageRank vectors to generate query-specific importance scores for pages at query time, we show that we can generate more accurate rankings than with a single, generic PageRank vector. For ordinary keyword search queries, we compute the topic-sensitive PageRank scores for pages satisfying the query using the topic of the query keywords. For searches done in context (e.g., when the search query is performed by highlighting words in a Web page), we compute the topic-sensitive PageRank scores using the topic of the context in which the query appeared.

REFERENCES

• 1: The Google Search Engine: Commercial search engine founded by the originators of PageRank. http://www.google.com/.
• 2: The Open Directory Project: Web directory for over 2.5 million URLs. http://www.dmoz.org/.
• 3: 'More Evil Than Dr. Evil?' http://searchenginewatch.com/sereport/99/11-google.html.
• 4: 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]
• 5: Krishna Bharat , George A. Mihaila, When experts agree: using non-affiliated experts to rank popular topics, Proceedings of the 10th international conference on World Wide Web, p.597-602, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372162]
• 6: Sergey Brin, Rajeev Motwani, Larry Page, and Terry Winograd. What can you do with a web in your pocket. In Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 1998.
• 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: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 10: Lev Finkelstein , Evgeniy Gabrilovich , Yossi Matias , Ehud Rivlin , Zach Solan , Gadi Wolfman , Eytan Ruppin, Placing search in context: the concept revisited, Proceedings of the 10th international conference on World Wide Web, p.406-414, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372094]
• 11: Taher H. Haveliwala. Efficient computation of PageRank. Stanford University Technical Report, 1999.
• 12: Jun Hirai , Sriram Raghavan , Hector Garcia-Molina , Andreas Paepcke, WebBase: a repository of Web pages, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.277-293, June 2000, Amsterdam, The Netherlands
• 13: Glen Jeh and Jennifer Widom. Scaling personalized web search. Stanford University Technical Report, 2002.
• 14: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 15: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 16: Larry Page. PageRank: Bringing order to the web. Stanford Digital Libraries Working Paper, 1997.
• 17: Davood Rafiei , Alberto O. Mendelzon, What is this page known for? Computing Web page reputations, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.823-835, June 2000, Amsterdam, The Netherlands
• 18: Matthew Richardson and Pedro Domingos. The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank, volume 14. MIT Press, Cambridge, MA, 2002 (To appear).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Linguistic processing
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models; Information filtering

General Terms:
Algorithms, Experimentation

Keywords:
PageRank, link structure, personalized search, search, search in context, web graph