Browse wiki

Jump to: navigation, search
An axiomatic approach for result diversification
Abstract Understanding user intent is key to designUnderstanding 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.sambiguation pages and a product database.
Added by wikilit team Added on initial load  +
Collected data time dimension Cross-sectional  +
Comments Data source = Wikipedia disambiguation pages
Conclusion This work presents an approach to characteThis work presents an approach to characterizing diversication systems using a set of natural axioms and an empirical analysis that qualitatively compares the choice of axioms, relevance and distance functions using the well-known measures of novelty and relevance. The choice of axioms presents a clean way of characterizing objectives independent of the algorithms used for the objective, and the speci c forms of the distance and relevance functions. Speci cally, we illustrate the use of the axiomatic framework by studying three objectives satisfying di erent subsets of axioms. The empirical analysis on the other hand, while being dependent on these parameters, has the advantage of being able to quantify the trade-o s between novelty and relevance in the diversi cation objective. In this regard, we explore two applications of web search and product search, each with di erent notions of relevance and distance. In each application, we compare the performance of the three objectives by measuring the trade-o in novelty and the trade-o in novelty and relevance.
Data source Experiment responses  + , Wikipedia pages  +
Google scholar url  +
Has author Sreenivas Gollapudi + , Aneesh Sharma +
Has domain Computer science +
Has topic Ranking and clustering systems +
Peer reviewed Yes  +
Publication type Conference paper  +
Published in WWW '09 Proceedings of the 18th international conference on World wide web +
Research design Experiment  + , Mathematical modeling  +
Research questions In this work, we initiate an axiomatic stuIn this work, we initiate an axiomatic study of result diversification. We propose a set of simple properties that any diversification system ought to satisfy and these properties help serve as a basis for the space of objective functions for result diversi cation. Generally, a diversi cation function can be thought of as taking two application speci c inputs viz, a relevance function that speci es the relevance of document for a given query, and a distance function that captures the pairwise similarity between any pair of documents in the set of relevant results for a given query. In the context of web search, one can use the search engine's ranking function1 as the relevance function. The characterization of the distance function is not that clear. In fact, designing the right distance function is key for having e ective result diversification. For example, by restricting the distance function to be a metric by imposing the triangle inequality d(u;w) d(u; v)+d(v;w) for all u; v;w 2 U, we can exploit efficient approximation algorithms to solve certain class of diversification objectives (see Section 3).iversification objectives (see Section 3).
Revid 11,128  +
Theories Undetermined
Theory type Design and action  +
Title An axiomatic approach for result diversification
Unit of analysis Article  +
Url  +
Wikipedia coverage Sample data  +
Wikipedia data extraction Live Wikipedia  +
Wikipedia language Not specified  +
Wikipedia page type Article  +
Year 2009  +
Creation dateThis property is a special property in this wiki. 15 March 2012 20:02:46  +
Categories Ranking and clustering systems  + , Computer science  + , Publications  +
Modification dateThis property is a special property in this wiki. 30 January 2014 20:53:47  +
hide properties that link here 
  No properties link to this page.


Enter the name of the page to start browsing from.