Elamur Research⌕
☰
home / papers / 2003 / Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search

Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search

Paper · 2003 · Taher H. Haveliwala

Summary

Standard PageRank gives each Web page a single importance score that ignores the query. As a result, heavily linked pages can rank highly even for topics where they have no real authority. Haveliwala addresses this by precomputing several PageRank vectors, each biased toward one topic. The bias comes from a nonuniform personalization (teleport) vector built from URLs in the 16 top-level categories of the Open Directory Project (ODP). This adds extra rank to topic pages during every iteration, rather than adjusting the standard vector afterward.

At query time, a multinomial naive-Bayes classifier estimates how closely the query relates to each topic. Where available, it also uses context such as the page around a highlighted term, past queries or user data. The final link score is a weighted linear combination of the stored vectors. Because the expensive link analysis runs offline, query cost stays close to ordinary PageRank. The author reports more accurate rankings than a single generic vector. Compressing the rank vectors makes the method practical at Web scale, and it became a foundation for personalized, context-aware search.

Key points

  • The system uses 16 topic-biased PageRank vectors, one for each top-level ODP category. Each is computed as PR(α, p) with a topic-specific personalization vector p.
  • Two usage scenarios are covered:
    • an ordinary keyword search, where the topic is inferred from the query terms;
    • "search in context", where the topic is inferred from surrounding text, query history, bookmarks or browsing history.
  • The rank vectors are compressed with lossy scalar quantizers. Six strategies were compared (linear, sqrt, log, mse-optimal, approx eq-depth, eq-depth). The log compander gave the lowest average KDist distortion (KDist = 1 − KSim) at every code length. This was measured on top-100 rankings for 86 test queries.
  • At 8 bits per value, all 16 vectors for a 120-million-page crawl fit in just under 2 GB of RAM. A query, including disk-based text-index lookup, takes about 1 second.
  • Planned future work includes:
    • finer-grained basis topics from deeper directory levels;
    • classifier-derived page topic weights for building p, which would make the vectors less sensitive to choices by 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 States567 works · 335,189 citations

 Fields, topics and concepts

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

🧭 Topics 1Research subjects and languages the work is about.Information retrieval & search · 561 works

Cite

Cite as Taher H. Haveliwala. 2003. Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search. IEEE TKDE 15(4), 2003.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1109/tkde.2003.1208999

@inproceedings{haveliwala2003topic,
  title = {{Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search}},
  author = {Taher H. Haveliwala},
  booktitle = {IEEE TKDE 15(4), 2003},
  year = {2003},
  doi = {10.1109/tkde.2003.1208999},
  url = {https://doi.org/10.1109/tkde.2003.1208999}
}

References

29 references, 5 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. ↗
  3. Krishna Bharat and Monika R. Henzinger. Improved algorithms for topic distillation in a hyperlinked environment. In Proceedings of the ACM-SIGIR, 1998. find
  4. 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
  5. 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
  6. 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. approx eq-depth linear eq-depth sqrt mse-optimal log (12)
  7. 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
  8. Soumen Chakrabarti. Mining the Web: Discovering Knowledge from Hypertext Data. Morgan-Kaufmann Publishers, San Francisco, CA, 2002. find
  9. Soumen Chakrabarti, Mukul M. Joshi, Kunal Punera, and David M. Pennock. The structure of broad topics on the web. In Proceedings of the Eleventh International World Wide Web Conference, 2002. find
  10. Michelangelo Diligenti, Marco Gori, and Marco Maggini. Web page scoring systems for horizontal and vertical search. In Proceedings of the Eleventh International World Wide Web Conference, May 2002. find
  11. 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
  12. Ronald Fagin, Ravi Kumar, and D. Sivakumar. Comparing top k lists. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2003. find
  13. 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
  14. Robert M. Gray and David L. Neuhoff. Quantization. IEEE Transactions on Information Theory, 44(6), October 1998. find
  15. Taher H. Haveliwala. Efficient computation of PageRank. Stanford University Technical Report, 1999. find
  16. Taher H. Haveliwala. Efficient encodings for document ranking vectors. Stanford University Technical Report, November 2002. find
  17. Taher H. Haveliwala. Topic-sensitive PageRank. In Proceedings of the Eleventh International World Wide Web Conference, May 2002.
  18. 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
  19. Glen Jeh and Jennifer Widom. Scaling personalized web search. In Proceedings of the Twelfth International World Wide Web Conference, May 2003. find
  20. 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. find
  21. Jon Kleinberg. Authoritative sources in a hyperlinked environment. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 1998.
  22. Andrew McCallum and Kamal Nigam. A comparison of event models for naive bayes text classification. In AAAI-98 Workshop on Learning for Text Categorization, 1998.
  23. Tom Mitchell. Machine Learning, chapter 6, pages 177–184. McGraw-Hill, Boston, 1997. find
  24. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, United Kingdom, 1995. find
  25. Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank citation ranking: Bringing order to the web. Stanford Digital Libraries Working Paper, 1998.
  26. David Pennock, Gary Flake, Steve Lawrence, Eric Glover, and C. Lee Giles. Winner’s don’t take all: Characterizing the competition for links on the web. In Proceedings of the National Academy of Sciences, 2002. find
  27. 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
  28. Matthew Richardson and Pedro Domingos. The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank, volume 14. MIT Press, Cambridge, MA, 2002. find
  29. Ian H. Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes. Morgan Kaufmann Publishers, San Francisco, 1999. find

Updated

↑ back to top

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