Using web-graph distance for relevance feedback in web search

ABSTRACT

We study the effect of user supplied relevance feedback in improving web search results. Rather than using query refinement or document similarity measures to rerank results, we show that the web-graph distance between two documents is a robust measure of their relative relevancy. We demonstrate how the use of this metric can improve the rankings of result URLs, even when the user only rates one document in the dataset. Our research suggests that such interactive systems can significantly improve search results.

REFERENCES

• 1: Lars Arge , Gerth Stølting Brodal , Laura Toma, On External-Memory MST, SSSP, and Multi-way Planar Graph Separation, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.433-447, July 05-07, 2000
• 2: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 3: N. Belkin, C. Cool, J. Koenemann, K. Ng, and S. Park. Using relevance feedback and ranking in interactive searching, 1996.
• 4: J. Dean and M. Henzinger. Finding related pages in the World Wide Web, 1999.
• 5: Andrew V. Goldberg , Chris Harrelson, Computing the shortest path: A search meets graph theory, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 6: Andrew V. Goldberg, Haim Kaplan, and Chris Harrelson. Reach for A*: Efficient point-to-point shortest path algorithms. In ALENEX, 2006.
• 7: Kalervo Järvelin , Jaana Kekäläinen, IR evaluation methods for retrieving highly relevant documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.41-48, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345545]
• 8: 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]
• 9: 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]
• 10: Jürgen Koenemann , Nicholas J. Belkin, A case for interaction: a study of interactive information retrieval behavior and effectiveness, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.205-212, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238487]
• 11: Kurt Mehlhorn , Ulrich Meyer, External-Memory Breadth-First Search with Sublinear I/O, Proceedings of the 10th Annual European Symposium on Algorithms, p.723-735, September 17-21, 2002
• 12: MSN search. http://search.msn.com.
• 13: Seda Ozmutlu , Amanda Spink , Huseyin C. Ozmutlu, A day in the life of web searching: an exploratory study, Information Processing and Management: an International Journal, v.40 n.2, p.319-345, March 2004 [doi>10.1016/S0306-4573(03)00044-X]
• 14: Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 15: Tao Qin , Tie-Yan Liu , Xu-Dong Zhang , Zheng Chen , Wei-Ying Ma, A study of relevance propagation for web search, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076105]
• 16: J. J. Rocchio. Relevance feedback in information retrieval. In The SMART Retrieval System: Experiments in Automatic Indexing, pages 324--336. Prentice Hall, Englewood Cliffs, NJ, 1971.
• 17: Azadeh Shakery and ChengXiang Zhai. Relevance propagation for topic distillation UIUC TREC 2003 Web Track Experiments. In TREC, pages 673--677, 2003.
• 18: Jaime Teevan , Susan T. Dumais , Eric Horvitz, Personalizing search via automated analysis of interests and activities, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076111]
• 19: Vishwa Vinay , Ken Wood , Natasa Milic-Frayling , Ingemar J. Cox, Comparing relevance feedback algorithms for web search, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062864]
• 20: Vivisimo search engine. http://www.vivisimo.com.
• 21: Yahoo mindset. http://mindset.research.yahoo.com.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
link analysis, relevance feedback, web search