Efficient Diversification of Web Search Results

Gabriele Capannini, Franco Maria Nardini, Raffaele Perego, Fabrizio Silvestri

Abstract

In this paper we analyze the efficiency of various search results diversification methods. While efficacy of diversification approaches has been deeply investigated in the past, response time and scalability issues have been rarely addressed. A unified framework for studying performance and feasibility of result diversification solutions is thus proposed. First we define a new methodology for detecting when, and how, query results need to be diversified. To this purpose, we rely on the concept of "query refinement" to estimate the probability of a query to be ambiguous. Then, relying on this novel ambiguity detection method, we deploy and compare on a standard test set, three different diversification methods: IASelect, xQuAD, and OptSelect. While the first two are recent state-of-the-art proposals, the latter is an original algorithm introduced in this paper. We evaluate both the efficiency and the effectiveness of our approach against its competitors by using the standard TREC Web diversification track testbed. Results shown that OptSelect is able to run two orders of magnitude faster than the two other state-of-the-art approaches and to obtain comparable figures in diversification effectiveness.

Introduction

Modern Web Search Engines (WSEs) face a constant challenge: query ambiguity. A search for "apple" could refer to the fruit, the technology giant, or a record label. To maximize user satisfaction, WSEs employ diversification—the practice of re-ranking results to ensure the first page covers multiple potential intents.

However, diversification introduces a significant computational trade-off. Most state-of-the-art algorithms treat diversification as an NP-hard "covering" problem, using greedy iterative methods that are often too slow for real-time production environments. This paper introduces OptSelect, a novel algorithm designed to provide high-quality diversification with significantly lower latency.

Methodology

The proposed framework addresses diversification through two primary innovations: intent detection via query logs and the optimized OptSelect selection algorithm.

Ambiguity Detection via Query Logs

Rather than relying on expensive on-the-fly text analysis or static taxonomies, the system utilizes historical "query refinements" from search logs (AOL and MSN). If users frequently follow a search for "leopard" with "leopard mac os x" or "leopard tank," the system learns that the original query is ambiguous and identifies these refinements as the specific intents to be satisfied.

The OptSelect Algorithm

Traditional algorithms like IASelect and xQuAD are iterative: they select the best document, then re-calculate the "marginal utility" of all remaining candidates before picking the next. This results in a computational complexity of $O(nk)$, where $n$ is the number of candidate documents and $k$ is the size of the final results list.

OptSelect reframes diversification as a direct utility maximization problem. By slightly relaxing the constraints of the objective function, the authors eliminated the need to re-score the entire list at every step. Using efficient heap data structures, OptSelect reduces complexity to $O(n \log k)$.

Experimental Results

The researchers evaluated the framework using the TREC 2009 Web Track (ClueWeb-B dataset), comparing OptSelect against state-of-the-art baselines.

Efficiency and Scalability

OptSelect demonstrates a massive speedup over its competitors. As shown in the execution time analysis, OptSelect maintains millisecond-level performance even as the candidate set size ($|R_q|$) and result list size ($k$) grow.

Execution time comparison (ms) for OptSelect, xQuAD, and IASelect across different candidate set sizes and result list depths.

In scenarios with 100,000 candidate documents and a 1,000-result output, OptSelect completes in roughly 14ms, while xQuAD and IASelect require between 3,000 and 4,000ms—a performance difference of two orders of magnitude.

Effectiveness

Crucially, this efficiency does not sacrifice search quality. Effectiveness metrics, including $\alpha$-NDCG (measuring diversity) and IA-P (intent-aware precision), show that OptSelect performs comparably to the more computationally expensive state-of-the-art methods.

Effectiveness metrics (alpha-NDCG and IA-P) for OptSelect, xQuAD, and IASelect across various result list depths.

Conclusion

OptSelect proves that search result diversification can be achieved at web-scale without the prohibitive latency of traditional greedy algorithms. By leveraging query logs for intent discovery and optimizing the selection process through mathematical relaxation, the algorithm provides a 100x speedup while maintaining state-of-the-art effectiveness. Future work will focus on addressing the "cold start" problem for rare queries and exploring personalized diversification based on individual user history.

Summary updated

Abstract

In this paper we analyze the efficiency of various search results diversification methods. While efficacy of diversification approaches has been deeply investigated in the past, response time and scalability issues have been rarely addressed. A unified framework for studying performance and feasibility of result diversification solutions is thus proposed. First we define a new methodology for detecting when, and how, query results need to be diversified. To this purpose, we rely on the concept of "query refinement" to estimate the probability of a query to be ambiguous. Then, relying on this novel ambiguity detection method, we deploy and compare on a standard test set, three different diversification methods: IASelect, xQuAD, and OptSelect. While the first two are recent state-of-the-art proposals, the latter is an original algorithm introduced in this paper. We evaluate both the efficiency and the effectiveness of our approach against its competitors by using the standard TREC Web diversification track testbed. Results shown that OptSelect is able to run two orders of magnitude faster than the two other state-of-the-art approaches and to obtain comparable figures in diversification effectiveness.
BibTeX
@article{capannini2011efficient,
  author = {Gabriele Capannini and Franco Maria Nardini and Raffaele Perego and Fabrizio Silvestri},
  title = {{Efficient Diversification of Web Search Results}},
  journal = {Proc. VLDB Endow.},
  year = {2011},
  doi = {10.14778/1988776.1988781},
}
Figure