Comparing relevance feedback algorithms for web search

ABSTRACT

We evaluate three different relevance feedback (RF)algorithms, Rocchio, Robertson/Sparck-Jones (RSJ)and Bayesian, in the context of Web search. We use a target-testing experimental procedure whereby a user must locate a specific document. For user relevance feedback, we consider all possible user choices of indicating zero or more relevant documents from a set of 10 displayed documents. Examination of the effects of each user choice permits us to compute an upper-bound on the performance of each RF algorithm.We ind that there is a significant variation in the upper-bound performance o the three RF algorithms and that the Bayesian algorithm approaches the best possible.

REFERENCES

• 1: Cox,I. J., Miller, M. L., Minka, T. P., Papathomas, T. V.,and Yianilos, P. N. The Bayesian Image Retrieval System, PicHunter: Theory, Implementation and Psychophysical Experiments. IEEE Transactions on Image Processing,9(1): 20--37,2000.
• 2: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Proceeding of the eighth international conference on World Wide Web, p.1467-1479, May 1999, Toronto, Canada
• 3: Donna Harman, Relevance feedback revisited, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.1-10, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133167]
• 4: Jansen,B. J., Spink, A.& Saracevic, T. 1999. The use of relevance eedback on the web:Implications for web IR system design.1999 World Conference on the WWW and Internet, Honolulu, Hawaii
• 5: MSN Search (http://search.msn.com)
• 6: Robertson, S. E., Sparck-Jones, K. Relevance weighting of search terms. Journal of the American Society or Information Science 27, 1976, pp.129--146.
• 7: Rocchio, J. Relevance feedback informarian retrieval. In Gerard Salton (ed.):The Smart Retrieval System - Experiments in Automatic Document Processing, pp.313--323. Prentice-Hall, Englewood Cliffs, N.J., 1971
• 8: Vinay, V., Cox, I. J., Milic-Frayling, N., Wood, K. Evaluating Relevance Feedback Algorithms for Searching on Small Displays. ECIR 2005.

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, Experimentation, Performance

Keywords:
evaluation, relevance feedback, web search