An axiomatic approach for result diversification
Top Cited Papers
- 20 April 2009
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 381-390
- https://doi.org/10.1145/1526709.1526761
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.Keywords
This publication has 19 references indexed in Scilit:
- Approximation Algorithms for Facility DispersionPublished by Informa UK Limited ,2007
- On rank-based effectiveness measures and optimizationInformation Retrieval Journal, 2007
- A risk minimization framework for information retrievalInformation Processing & Management, 2006
- Facility dispersion problems: Heuristics and special casesPublished by Springer Science and Business Media LLC ,2005
- Improving recommendation lists through topic diversificationPublished by Association for Computing Machinery (ACM) ,2005
- Approximation Algorithms for Dispersion ProblemsJournal of Algorithms, 2001
- Min-Wise Independent PermutationsJournal of Computer and System Sciences, 2000
- Approximation algorithms for maximum dispersionOperations Research Letters, 1997
- Heuristic and Special Case Algorithms for Dispersion ProblemsOperations Research, 1994
- An Analysis of the Greedy Heuristic for Independence SystemsAnnals of Discrete Mathematics, 1978