Condorcet fusion for improved retrieval

ABSTRACT

We present a new algorithm for improving retrieval results by combining document ranking functions: Condorcet-fuse. Beginning with one of the two major classes of voting procedures from Social Choice Theory, the Condorcet procedure, we apply a graph-theoretic analysis that yields a sorting-based algorithm that is elegant, efficient, and effective. The algorithm performs very well on TREC data, often outperforming existing metasearch algorithms whether or not relevance scores and training data is available. Condorcet-fuse significantly outperforms Borda-fuse, the analogous representative from the other major class of voting algorithms.

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: Brian Theodore Bartell, Optimizing ranking functions: a connectionist approach to adaptive information retrieval, University of California at San Diego, La Jolla, CA, 1994
• 3: Brian T. Bartell , Garrison W. Cottrell , Richard K. Belew, Automatic combination of multiple ranked retrieval systems, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.173-181, July 03-06, 1994, Dublin, Ireland
• 4: N. Belkin, P. Kantor, C. Cool, and R. Quatrain. Combining evidence for information retrieval. In Harman {15}, pages 35--43.
• 5: N. Craswell, D. Hawking, and P. Thistlewaite. Merging results from isolated search engines. In Proceedings of the Tenth Australasian Database Conference, Aukland, New Zealand, Jan. 1999. Springer-Verlag.
• 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, The Kluwer International Series on Information Retrieval, chapter~1. Kluwer Academic Publishers, 2000.
• 7: W. B. Croft, D. J. Harper, D. H. Kraft, and J. Zobel, editors. SIGIR'01, Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, New Orleans, Louisiana, USA, Sept. 2001. ACM Press, New York.
• 8: J. C. de~Borda. Mémoire sur les élections au scrutin. In Histoire de l'Academie Royale des Sciences. Paris, 1781.
• 9: M. de~Condorcet. Essai sur l'application de l'analyse à la probabilité des decisions rendues à la pluralité des voix, 1785.
• 10: H. L. Fisher and D. R. Elchesen. Effectiveness of combining title words and index terms in machine retrieval searches. Nature, 238:109--110, July 1972.
• 11: Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, July 1995
• 12: E. A. Fox, M. P. Koushik, 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.
• 13: E. A. Fox and J. A. Shaw. Combination of multiple searches. In Harman {15}, pages 243--249.
• 14: 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]
• 15: D. Harman, editor. The Second Text REtrieval Conference (TREC-2), Gaithersburg, MD, USA, Mar. 1994. U.S. Government Printing Office, Washington D.C.
• 16: 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]
• 17: J. S. Kelly. Social Choice Theory: An Introduction. Springer-Verlag, 1988.
• 18: Joon Ho Lee, Combining multiple evidence from different properties of weighting schemes, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.180-188, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215358]
• 19: 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
• 20: 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]
• 21: H. Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1988.
• 22: K. B. Ng. An Investigation of the Conditions for Effective Data Fusion in Information Retrieval. PhD thesis, School of Communication, Information, and Library Studies, Rutgers University, 1998.
• 23: K. B. Ng and P. B. Kantor. An investigation of the preconditions for effective data fusion in IR: A pilot study. In Proceedings of the 61th Annual Meeting of the American Society for Information Science, 1998.
• 24: K. B. Ng, D. Loewenstern, C. Basu, H. Hirsh, and P. B. Kantor. Data fusion of machine learning methods for the TREC5 routing task (and other work). In Voorhees and Harman {35}, pages 477--487.
• 25: W. H. Riker. Liberalism Against Populism. Waveland Press, 1982.
• 26: Erik Warren Selberg , Oren Etzioni, Towards comprehensive web search, 1999
• 27: 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.
• 28: Bo Shu , Subhash Kak, A neural network-based intelligent metasearch engine, Information Sciences—Informatics and Computer Science: An International Journal, v.120 n.1-4, p.1-11, Nov.1.1999 [doi>10.1016/S0020-0255(99)00062-6]
• 29: 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]
• 30: 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]
• 31: Christopher Charles Vogt , Garrison W. Cottrell, Adaptive combination of evidence for information retrieval, 1999
• 32: C. C. Vogt. How much more is better? Characterizing the effects of adding more IR systems to a combination. In Content-Based Multimedia Information Access (RIAO), pages 457--475, Paris, France, Apr. 2000.
• 33: 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]
• 34: 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 {35}, pages 503--515.
• 35: E. Voorhees and D. Harman, editors. The Fifth Text REtrieval Conference (TREC-5), Gaithersburg, MD, USA, 1997. U.S. Government Printing Office, Washington D.C.
• 36: Ellen M. Voorhees , Narendra K. Gupta , Ben Johnson-Laird, Learning collection fusion strategies, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.172-179, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215357]