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.
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.
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