Web metasearch: rank vs. score based rank aggregation methods

ABSTRACT

Given a set of rankings, the task of ranking fusion is the problem of combining these lists in such a way to optimize the performance of the combination. The ranking fusion problem is encountered in many situations and, e.g., metasearch is a prominent one. It deals with the problem of combining the result lists returned by multiple search engines in response to a given query, where each item in a result list is ordered with respect to a search engine and a relevance score. Several ranking fusion methods have been proposed in the literature. They can be classified based on whether: (i) they rely on the rank; (ii) they rely on the score; and (iii) they require training data or not. Our paper will make the following contributions: (i) we will report experimental results for the Markov chain rank based methods, for which no large experimental tests have yet been made; (ii) while it is believed that the rank based method, named Borda Count, is competitive with score based methods, we will show that this is not true for metasearch; and (iii) we will show that Markov chain based methods compete with score based methods. This is especially important in the context of metasearch as scores are usually not available from the search engines.

REFERENCES

• 1: Javed A. Aslam , Mark Montague, Models for metasearch, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.276-284, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384007]
• 2: J. C. Borda. Mémoire sur les élections au scrutin. Histoire de I'Académie Royal des Sciences, 1781.
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 4: James P. Callan , Zhihong Lu , W. Bruce Croft, Searching distributed collections with inference networks, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-28, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215328]
• 5: Nick Craswell, David Hawking, and Paul Thistlewaite. Merging results from isolated search engines. In 10th Australian Database Conf., 1999.
• 6: Daniel Dreilinger , Adele E. Howe, Experiences with selecting search engines using metasearch, ACM Transactions on Information Systems (TOIS), v.15 n.3, p.195-222, July 1997 [doi>10.1145/256163.256164]
• 7: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 8: Ronald Fagin , Edward L. Wimmers, Incorporating User Preferences in Multimedia Queries, Proceedings of the 6th International Conference on Database Theory, p.247-261, January 08-10, 1997
• 9: Joseph A. Fox, Edward Shaw. Combination of multiple sources: The TREC-2 interactive track matrix experiment. In ACM SIGIR-94, 1994.
• 10: Susan Gauch, Guijun Wang, and Mario Gomez. ProFusion: Intelligent fusion from multiple, distributed search engines. volume 2, pages 637--649, 1996.
• 11: Steve Lawrence , C. Lee Giles, Inquirus, the NECI meta search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.95-105, April 1, 1998
• 12: 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
• 13: 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]
• 14: D. G. Saari. The mathematics of voting: Democratic symmetry. The Economist, March 4 2000.
• 15: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 16: E. Selberg and O. Etzioni. The MetaCrawler architecture for resource aggregation on the Web. IEEE Expert, (January-February):11--14, 1997.
• 17: 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]
• 18: Ellen M. Voorhees, Narendra K. Gupta, and Ben Johson-Laird. The collection fusion problem. In D. K. Harman, editor, Proc. 3rd Text Retrieval Cconference (TREC-3), number 500--225, 1994. National Institute of Standards and Technology.
• 19: Ronald R. Yager , Alexander Rybalov, On the fusion of documents from multiple collection information retrieval systems, Journal of the American Society for Information Science, v.49 n.13, p.1177-1184, Nov. 1998 [doi>10.1002/(SICI)1097-4571(1998)49:13<1177::AID-ASI5>3.0.CO;2-E]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

Keywords:
meta-search, rank list aggregation