An axiomatic approach for result diversification

ABSTRACT

Understanding user intent is key to designing an effective ranking system in a search engine. In the absence of any explicit knowledge of user intent, search engines want to diversify results to improve user satisfaction. In such a setting, the probability ranking principle-based approach of presenting the most relevant results on top can be sub-optimal, and hence the search engine would like to trade-off relevance for diversity in the results.

In analogy to prior work on ranking and clustering systems, we use the axiomatic approach to characterize and design diversification systems. We develop a set of natural axioms that a diversification system is expected to satisfy, and show that no diversification function can satisfy all the axioms simultaneously. We illustrate the use of the axiomatic framework by providing three example diversification objectives that satisfy different subsets of the axioms. We also uncover a rich link to the facility dispersion problem that results in algorithms for a number of diversification objectives. Finally, we propose an evaluation methodology to characterize the objectives and the underlying axioms. We conduct a large scale evaluation of our objectives based on two data sets: a data set derived from the Wikipedia disambiguation pages and a product database.

REFERENCES

• 1: Rakesh Agrawal , Sreenivas Gollapudi , Alan Halverson , Samuel Ieong, Diversifying search results, Proceedings of the Second ACM International Conference on Web Search and Data Mining, February 09-12, 2009, Barcelona, Spain [doi>10.1145/1498759.1498766]
• 2: A. Altman and M. Tennenholtz. On the axiomatic foundations of ranking systems. In Proc. 19th International Joint Conference on Artificial Intelligence, pages 917--922, 2005.
• 3: Kenneth Arrow. Social Choice and Individual Values. Wiley, New York, 1951.
• 4: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 5: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 6: Jaime Carbonell , Jade Goldstein, The use of MMR, diversity-based reranking for reordering documents and producing summaries, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.335-336, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291025]
• 7: Barun Chandra , Magnús M. Halldórsson, Approximation algorithms for dispersion problems, Journal of Algorithms, v.38 n.2, p.438-465, Feb. 2001 [doi>10.1006/jagm.2000.1145]
• 8: Harr Chen , David R. Karger, Less is more: probabilistic models for retrieving fewer relevant documents, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148245]
• 9: Charles L.A. Clarke , Maheedhar Kolla , Gordon V. Cormack , Olga Vechtomova , Azin Ashkan , Stefan Büttcher , Ian MacKinnon, Novelty and diversity in information retrieval evaluation, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390446]
• 10: Sreenivas Gollapudi , Rina Panigrahy, Exploiting asymmetry in hierarchical topic extraction, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183683]
• 11: R. Hassin, S. Rubinstein, and A. Tamir. Approximation algorithms for maximum dispersion. Operations Research Letters, 21(3):133--137, 1997.
• 12: J. Kleinberg. An Impossibility Theorem for Clustering. Advances in Neural Information Processing Systems 15: Proceedings of the 2002 Conference, 2003.
• 13: B. Korte and D. Hausmann. An Analysis of the Greedy Heuristic for Independence Systems. Algorithmic Aspects of Combinatorics, 2:65--74, 1978.
• 14: SS Ravi, D.J. Rosenkrantz, and G.K. Tayi. Facility dispersion problems: Heuristics and special cases. Proc. 2nd Workshop on Algorithms and Data Structures (WADS), pages 355--366, 1991.
• 15: S.S. Ravi, D.J. Rosenkrantz, and G.K. Tayi. Heuristic and special case algorithms for dispersion problems. Operations Research, 42(2):299--310, 1994.
• 16: SS Ravi, D.J. Rosenkrantzt, and G.K. Tayi. Approximation Algorithms for Facility Dispersion. In Teofilo F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC, 2007.
• 17: Stephen Robertson , Hugo Zaragoza, On rank-based effectiveness measures and optimization, Information Retrieval, v.10 n.3, p.321-339, June 2007 [doi>10.1007/s10791-007-9025-9]
• 18: Atish Das Sarma , Sreenivas Gollapudi , Samuel Ieong, Bypass rates: reducing query abandonment using negative inferences, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401916]
• 19: E. Vee, U. Srivastava, J. Shanmugasundaram, P. Bhat, and S.A. Yahia. Efficient Computation of Diverse Query Results. IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008, pages 228--236, 2008.
• 20: ChengXiang Zhai. Risk Minimization and Language Modeling in Information Retrieval. PhD thesis, Carnegie Mellon University, 2002.
• 21: Cheng Xiang Zhai , William W. Cohen , John Lafferty, Beyond independent relevance: methods and evaluation metrics for subtopic retrieval, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860440]
• 22: ChengXiang Zhai , John Lafferty, A risk minimization framework for information retrieval, Information Processing and Management: an International Journal, v.42 n.1, p.31-55, January 2006 [doi>10.1016/j.ipm.2004.11.003]
• 23: Cai-Nicolas Ziegler , Sean M. McNee , Joseph A. Konstan , Georg Lausen, Improving recommendation lists through topic diversification, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060754]

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
approximation algorithms, axiomatic framework, diversification, facility dispersion, search engine, wikipedia