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.
Proceedings of ACM International Conference on Web Search and Data Mining (WSDM)
year
2009
month
February
posted-at
2009-01-21 10:00:16
location
Barcelona, Catalunya, Spain
citeulike-article-id
3919305
priority
0
comment
Considers a finite set of categories to which a document or query can belong.
Produces a diversified result set by a greedy method that picks the next document maximizing its marginal utility, defined as the product of its relevance and the probability that none of the documents already selected satisfied the user.
%0 Conference Paper
%1 Agrawal09
%A Agrawal, Rakesh
%A Gollapudi, Sreenivas
%A Halverson, Alan
%A Ieong, Samuel
%B Proceedings of ACM International Conference on Web Search and Data Mining (WSDM)
%D 2009
%K WebSearch WebSearchResults diversification evaluation
%T Diversifying Search Results
%U http://research.microsoft.com/apps/pubs/default.aspx?id=73931
%X 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.
@inproceedings{Agrawal09,
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.},
added-at = {2009-01-23T16:13:56.000+0100},
author = {Agrawal, Rakesh and Gollapudi, Sreenivas and Halverson, Alan and Ieong, Samuel},
biburl = {https://www.bibsonomy.org/bibtex/23a6d63fc66d79daf6205a346fa0e8398/mkroell},
booktitle = {Proceedings of ACM International Conference on Web Search and Data Mining (WSDM)},
citeulike-article-id = {3919305},
comment = {Considers a finite set of categories to which a document or query can belong.
Produces a diversified result set by a greedy method that picks the next document maximizing its marginal utility, defined as the product of its relevance and the probability that none of the documents already selected satisfied the user.},
description = {CiteULike: Diversifying Search Results},
interhash = {528f1eb8a1349f0a95343bf4fdebd992},
intrahash = {3a6d63fc66d79daf6205a346fa0e8398},
keywords = {WebSearch WebSearchResults diversification evaluation},
location = {Barcelona, Catalunya, Spain},
month = {February},
posted-at = {2009-01-21 10:00:16},
priority = {0},
timestamp = {2009-03-10T11:19:24.000+0100},
title = {Diversifying Search Results},
url = {http://research.microsoft.com/apps/pubs/default.aspx?id=73931},
year = 2009
}