Diversifying search results
Published 9 February 2009
Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, Samuel Ieong
Citations1,011
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work proposes an algorithm that well approximates this objective in general, and is provably optimal for a natural special case, and generalizes several classical IR metrics, including NDCG, MRR, and MAP, to explicitly account for the value of diversification.
Abstract
We study the problem of answering ambiguous web queries in a setting where there exists a taxonomy of information, and that both queries and documents may belong to more than one category according to this taxonomy. We present a systematic approach to diversifying results that aims to minimize the risk of dissatisfaction of the average user. We propose an algorithm that well approximates this objective in general, and is provably optimal for a natural special case. Furthermore, we generalize several classical IR metrics, including NDCG, MRR, and MAP, to explicitly account for the value of diversification. We demonstrate empirically that our algorithm scores higher in these generalized metrics compared to results produced by commercial search engines.
Keywords
Computer Science
Mathematical ProgrammingAn analysis of approximations for maximizing submodular set functions—I
4,458 Citations1978George L. Nemhauser, Laurence A. Wolsey +1 more
It is shown that a “greedy” heuristic always produces a solution whose value is at least 1 −[(K − 1/K]K times the optimal value, which can be achieved for eachK and has a limiting value of (e − 1)/e, where e is the base of the natural logarithm.
ACM SIGACT NewsApproximation Algorithms for NP-Hard Problems
3,133 Citations1997Dorit S. Hochba
This book reviews the design techniques for approximation algorithms and the developments in this area since its inception about three decades ago and the "closeness" to optimum that is achievable in polynomial time.
ACM SIGIR ForumThe Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries
2,210 Citations2017Jaime Carbonell, Jade Goldstein
A method for combining query-relevance with information-novelty in the context of text retrieval and summarization and preliminary results indicate some benefits for MMR diversity ranking in document retrieval and in single document summarization.
The use of MMR, diversity-based reranking for reordering documents and producing summaries
2,144 Citations1998Jaime Carbonell, Jade Goldstein
This paper presents a method for combining query-relevance with information-novelty in the context of text retrieval and summarization, and preliminary results indicate some benefits for MMR diversity ranking in document retrieval and in single document summarization.
Improving recommendation lists through topic diversification
1,839 Citations2005Cai-Nicolas Ziegler, Sean M. McNee +2 more
This work presents topic diversification, a novel method designed to balance and diversify personalized recommendation lists in order to reflect the user's complete spectrum of interests, and introduces the intra-list similarity metric to assess the topical diversity of recommendation lists.
ACM SIGIR ForumIR evaluation methods for retrieving highly relevant documents
1,466 Citations2017Kalervo Järvelin, Jaana Kekäläinen
The novel evaluation methods and the case demonstrate that non-dichotomous relevance assessments are applicable in IR experiments, may reveal interesting phenomena, and allow harder testing of IR methods.
IR evaluation methods for retrieving highly relevant documents
958 Citations2000Kalervo Järvelin, Jaana Kekäläinen
The novel evaluation methods and the case demonstrate that non-dichotomous relevance assessments are applicable in IR experiments, may reveal interesting phenomena, and allow harder testing of IR methods.
Novelty and diversity in information retrieval evaluation
951 Citations2008Charles L. A. Clarke, Maheedhar Kolla +5 more
This paper develops a framework for evaluation that systematically rewards novelty and diversity into a specific evaluation measure, based on cumulative gain, and demonstrates the feasibility of this approach using a test collection based on the TREC question answering track.
ACM SIGIR ForumBeyond Independent Relevance
567 Citations2015ChengXiang Zhai, William W. Cohen +1 more
A framework for evaluating subtopic retrieval is proposed which generalizes the traditional precision and recall metrics by accounting for intrinsic topic difficulty as well as redundancy in documents and a maximal marginal relevance (MMR) ranking strategy is proposed.
Learning diverse rankings with multi-armed bandits
518 Citations2008Filip Radlinski, Robert Kleinberg +1 more
This work presents two online learning algorithms that directly learn a diverse ranking of documents based on users' clicking behavior and shows that these algorithms minimize abandonment, or alternatively, maximize the probability that a relevant document is found in the top k positions of a ranking.
Overview of the TREC 2006.
469 Citations2006Ellen M. Voorhees
The fourteenth Text REtrieval Conference, TREC 2005, was held at the National Institute of Standards and Technology (NIST) 15 to 18 November 2005 and had 117 participating groups from 23 different countries.
Less is more
319 Citations2006Harr Chen, David R. Karger
Improving personalized web search using result diversification
235 Citations2006Filip Radlinski, Susan Dumais
Three methods to increase the diversity of the top results are proposed and evaluated and the effectiveness of these methods is evaluated.
Using the wisdom of the crowds for keyword generation
150 Citations2008Ariel Fuxman, Panayiotis Tsaparas +2 more
This work identifies queries related to a campaign by exploiting the associations between queries and URLs as they are captured by the user's clicks, and proposes algorithms within the Markov Random Field model to solve this problem.
Information Processing & ManagementA risk minimization framework for information retrieval
149 Citations2005ChengXiang Zhai, John Lafferty
A probabilistic information retrieval framework in which the retrieval problem is formally treated as a statistical decision problem, and how this framework can unify existing retrieval models and accommodate systematic development of new retrieval models is discussed.
Journal of the American Society for Information ScienceInformation retrieval: A sequential learning process
89 Citations1983Abraham Bookstein
It is argued that information retrieval should be envisioned as a process, in which the information retrieval system responds to a request by presenting documents to the patron in a sequence, gathering feedback as the process proceeds, and using this information to modify future retrieval.
Information Processing & ManagementBeyond topicality
84 Citations1982Bert R. Boyce
Topicality is an operationally necessary but insufficient condition for requestor judged relevance and a two stage system which generates a high recall set and discards imprecise documents by measuring their distance from a seed document can be iterated to provide topicality feedback without user input.
Sampling search-engine results
75 Citations2005Aris Anagnostopoulos, Andrei Broder +1 more
Information Storage and RetrievalA searching procedure for information retrieval
58 Citations1964William Goffman
A search procedure for an information retrieval system is developed whereby the answer to a question is obtained by maximizing an evaluation function of the system's output in terms of the probability of relevance.
ACM SIGIR ForumRisk minimization and language modeling in text retrieval dissertation abstract
33 Citations2002ChengXiang Zhai
A new text retrieval framework based on Bayesian decision theory is presented, which unifies several existing retrieval models, including the recently proposed language modeling approach, within one general probabilistic framework and allows for incorporating user factors beyond the traditional notion of topical relevance.