Models for metasearch

ABSTRACT

Given the ranked lists of documents returned by multiple search engines in response to a given query, the problem ofmetasearchis to combine these lists in a way which optimizes the performance of the combination. This paper makes three contributions to the problem of metasearch: (1) We describe and investigate a metasearch model based on an optimal democratic voting procedure, the Borda Count; (2) we describe and investigate a metasearch model based on Bayesian inference; and (3) we describe and investigate a model for obtaining upper bounds on the performance of metasearch algorithms. Our experimental results show that metasearch algorithms based on the Borda and Bayesian models usually outperform the best input system and are competitive with, and often outperform, existing metasearch strategies. Finally, our initial upper bounds demonstrate that there is much to learn about the limits of the performance of metasearch.

REFERENCES

• 1: Proceedi gs of the 24th Anual International ACM SIGIR Conference on Research and Development i Information Retrieval ,New Orleans,Louisiana,USA, 2001.ACM Press,New York.
• 2: Brian Theodore Bartell, Optimizing ranking functions: a connectionist approach to adaptive information retrieval, University of California at San Diego, La Jolla, CA, 1994
• 3: N.Belkin,P.Kantor,C.Cool,and R.Quatrain. Combining evidence for information retrieval.In Harman {11 },pages 35 -43.
• 4: William S. Cooper, Some inconsistencies and misnomers in probabilistic information retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.57-61, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122866]
• 5: W.S.Cooper,A.Chen,andF.C.Gey.Fulltext retrieval based on probabilistic equations with coe .cients .tted by logistic regression.In Harman {11 },pages 57 -66.
• 6: W.B.Croft.Combining approaches to information retrieval.In W.B.Croft,editor,Advances in Information Retrieval:Recent Research from the Center for Intelligent Information Retrieval , chapter 1.Kluwer Academic Publishers,2000.
• 7: The mathematics of voting:Democratic symmetry. The Economist ,page 83,Mar.2000.
• 8: E.A.Fox,M.P.Kouhik,J.Shaw,,R.Modlin,and D.Rao.Combining evidence from multiple searches. In D.Harman,editor,The First Text REtrieval Conference (TREC-1),pages 319 -328,Gaithersburg, MD,USA,Mar.1993.U.S.Government Printing Office, Washington D.C.
• 9: E.A.Fox and J.A.Shaw.Combination of multiple searches.In Harman {11},pages 243 -249.
• 10: Kevin L. Fox , Ophir Frieder , Margaret M. Knepper , Eric J. Snowberg, SENTINEL: a multiple engine information retrieval and visualization system, Journal of the American Society for Information Science, v.50 n.7, p.616-625, May 15, 1999 [doi>10.1002/(SICI)1097-4571(1999)50:7<616::AID-ASI6>3.0.CO;2-E]
• 11: D.Harman,editor.The Second Text REtrieval Conference (TREC-2),Gaithersburg,MD,USA,Mar. 1994.U.S.Government Printing O .ce,Washington D.C.
• 12: David A. Hull , Jan O. Pedersen , Hinrich Schütze, Method combination for document filtering, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.279-287, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243275]
• 13: Joon Ho Lee, Analyses of multiple evidence combination, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.267-276, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 14: R. Manmatha , T. Rath , F. Feng, Modeling score distributions for combining the outputs of search engines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.267-275, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384005]
• 15: Mark Montague , Javed A. Aslam, Metasearch consistency, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.386-387, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384030]
• 16: K.B.Ng.A Investigation of the Conditions for Effective Data Fusion in Information Retrieval .PhD thesis,School of Communication,Information,and Library Studies,Rutgers University,1998.
• 17: K.B.Ng and P.B.Kantor.An investigation of the preconditions for e .ective data fusion in ir:A pilot study.In Proceedi gs of the 61th Anual Meeting of the American Society for Information Science ,1998.
• 18: K.B.Ng,D.Loewentern,C.Bau,H.Hirh,and P.B.Kantor.Data fusion of machine-learning method for the TREC5 routing task (and other work).In Voorhees and Harman {32 },pages 477 -487.
• 19: Content-Based Multimedia Information Access (RIAO),Paris,France,Apr.2000.
• 20: D.G.Saari.Explaining all three-alternative voting outcomes.Journal of Economic Theory , 87(2):313 -355,Aug.1999.
• 21: J.Savoy,A.L.Calve,and D.Vrajitoru.Report on the TREC-5 experiment:Data fusion and collection fusion.In Voorhees and Harman {32},pages 489 -502.
• 22: E.Selberg and O.Etzioni.On the instability of web search engines.In RIAO {19},pages 223 -235.
• 23: Erik Warren Selberg , Oren Etzioni, Towards comprehensive web search, 1999
• 24: J.A.Shaw and E.A.Fox.Combination of multiple searches.In D.Harman,editor,Overview of the Third Text REtrieval Conference (TREC-3),pages 105 -108, Gaithersburg,MD,USA,Apr.1995.U.S.Government Printing Office,Washington D.C.
• 25: P. Thompson, A combination of expert opinion approach to probabilistic information retrieval, part 1: The conceptual model, Information Processing and Management: an International Journal, v.26 n.3, p.371-382, 1990 [doi>10.1016/0306-4573(90)90097-L]
• 26: P. Thompson, A combination of expert opinion approach to probabilistic information retrieval, part 2: Mathematical treatment of CEO model 3, Information Processing and Management: an International Journal, v.26 n.3, p.383-394, 1990 [doi>10.1016/0306-4573(90)90098-M]
• 27: M.van Erp and L.Schomaker.Variant of the borda count method for combining ranked classi .er hypotheses. In Proceedi gs of the Seventh International Workshop on Frontiers in Handwriting Recognition ,pages 443 -452,Amsterdam,Sept.2000. International Unipen Foundation.
• 28: Christopher Charles Vogt , Garrison W. Cottrell, Adaptive combination of evidence for information retrieval, 1999
• 29: C.C.Vogt.How much more is better?Characterizing the e .ects of adding more IR systems to a combination.In RIAO {19}, pages 457 -475.
• 30: Christopher C. Vogt , Garrison W. Cottrell, Fusion Via a Linear Combination of Scores, Information Retrieval, v.1 n.3, p.151-173, October 1999 [doi>10.1023/A:1009980820262]
• 31: C.C.Vogt,G.W.Cottrell,R.K.Belew,and B.T. Bartell.Using relevance to train a linear mixture of experts.In Voorhees and Harman {32},pages 503 -515.
• 32: E.Voorhees and D.Harman,editors.The Fifth Text REtrieval Conference (TREC-5),Gaithersburg,MD, USA,1997.U.S.Government Printing O .ce, Washington D.C.
• 33: E.Voorhees and D.Harman.Overview of the Eighth Text REtrieval Conference (TREC-8).In D.Harman, editor,The Eighth Text REtrieval Conference (TREC-8),Gaithersburg,MD,USA,2000.U.S. Government Printing O .ce,Washington D.C.

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.3 Information Search and Retrieval
          Subjects: Information filtering; Retrieval models

General Terms:
Algorithms, Design, Experimentation, Performance