Elamur Research⌕
☰
home / papers / 2002 / Topic-Sensitive PageRank

Topic-Sensitive PageRank

Paper · 2002 · Taher H. Haveliwala

Summary

Standard PageRank assigns every Web page one query-independent importance score. As a result, heavily linked pages can rank well for queries outside their area of authority. Haveliwala proposes making link-based importance depend on the topic while keeping query-time cost close to ordinary PageRank. Offline, the method computes several biased PageRank vectors. Each one replaces the uniform teleportation (personalization) vector with one concentrated on URLs listed under a single top-level category of the Open Directory Project (ODP). At query time, a unigram language model classifier estimates how strongly the query relates to each topic. It can also use surrounding context, such as text around a highlighted term. The final page score is a linear combination of the topic vectors, weighted by these estimates. Examples such as the query "blues" show that the method separates music-related and mental-health-related results, whereas unbiased PageRank returns generic popular sites. The approach matters because it brings query sensitivity, similar to HITS, into a precomputed, spam-resistant ranking framework. It also offers a practical basis for personalized and context-aware search.

Key points

  • The system uses 16 topic-biased PageRank vectors, one per top-level ODP category. Each vector teleports uniformly to that category's URLs (1/|T_j| for members, 0 otherwise). The biasing is applied during the iteration itself, not as post-processing.
  • At query time, a unigram language model computes topic weights for the query or its context. These weights mix the precomputed vectors, so link analysis stays offline.
  • The paper considers two scenarios: ordinary keyword search and search in context, where a user highlights a term in a page. The author also discusses query history, bookmarks, and browsing history as further sources of context.
  • The author highlights four claimed advantages of using basis topics: flexibility, transparency, privacy, and efficiency. On privacy, a client could send only topic weights to the server instead of browsing history or document text.
  • Planned work includes finer-grained ODP levels, which raise cost because computation grows linearly with the number of topics. Another plan is a damping vector built from classifier-assigned topic weights for all pages (Eq. 11), intended to reduce sensitivity to individual ODP editors.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Stanford UniversityStanford · United States506 works · 330,052 citations

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksInformation Systems · 1,730 works

Cite

Cite as Taher H. Haveliwala. 2002. Topic-Sensitive PageRank. WWW 2002 (Best Student Paper).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1145/511446.511513

@inproceedings{haveliwala2002topic,
  title = {{Topic-Sensitive PageRank}},
  author = {Taher H. Haveliwala},
  booktitle = {WWW 2002 (Best Student Paper)},
  year = {2002},
  doi = {10.1145/511446.511513},
  url = {https://doi.org/10.1145/511446.511513}
}

References

18 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  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 and Monika R. Henzinger. Improved algorithms for topic distillation in a hyperlinked environment. In Proceedings of the ACM-SIGIR, 1998. find
  5. Krishna Bharat and George A. Mihaila. When experts agree: Using non-affiliated experts to rank popular topics. In Proceedings of the Tenth International World Wide Web Conference, 2001. find
  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. find
  7. Sergey Brin and Larry Page. The anatomy of a large-scale hypertextual web search engine. In Proceedings of the Seventh International World Wide Web Conference, 1998.
  8. S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, P. Raghavan, and S. Rajagopalan. Automatic resource compilation by analyzing hyperlink structure and associated text. In Proceedings of the Seventh International World Wide Web Conference, 1998. find
  9. Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proceedings of the Tenth International World Wide Web Conference, 2001. find
  10. Lev Finkelstein, Evgeniy Gabrilovich, Yossi Matias, Ehud Rivlin, Zach Solan, Gadi Wolfman, and Eytan Ruppin. Placing search in context: the concept revisited. In Proceedings of the Tenth International World Wide Web Conference, 2001. find
  11. Taher H. Haveliwala. Efficient computation of PageRank. Stanford University Technical Report, 1999. find
  12. J. Hirai, S. Raghavan, H. Garcia-Molina, and A. Paepcke. Webbase: A repository of web pages. In Proceedings of the Ninth International World Wide Web Conference, 2000. find
  13. Glen Jeh and Jennifer Widom. Scaling personalized web search. Stanford University Technical Report, 2002. find
  14. Jon Kleinberg. Authoritative sources in a hyperlinked environment. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 1998.
  15. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, United Kingdom, 1995. find
  16. Larry Page. PageRank: Bringing order to the web. Stanford Digital Libraries Working Paper, 1997. find
  17. Davood Rafiei and Alberto O. Mendelzon. What is this page known for? Computing web page reputations. In Proceedings of the Ninth International World Wide Web Conference, 2000. find
  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). find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/haveliwala-2002-topic-sensitive-pagerank/