Efficient Diversification of Web Search Results

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

TL;DR

Researchers from ISTI-CNR have developed OptSelect, a search result diversification algorithm that is two orders of magnitude faster than current state-of-the-art methods. By leveraging query logs to detect ambiguity and reframing diversification as a utility maximization problem, they achieved a 100x speedup while maintaining the same level of search relevance and diversity.

What Problem Does This Paper Address?

When you search for "apple," do you want the fruit, the tech giant, or the record label? To satisfy users, Web Search Engines (WSEs) use diversification—the practice of "packing" the first page of results with documents covering different possible intents.

The challenge is a classic trade-off between efficacy (how good the results are) and efficiency (how fast they appear). Most existing diversification algorithms are computationally expensive. They treat diversification as an NP-hard "covering" problem, using greedy algorithms that re-scan and re-score the entire candidate list for every single slot on the results page. In a world where Google co-founder Larry Page famously noted that even slight delays drive users away, these slow algorithms are often too "heavy" for real-time production environments.

Methods

The authors propose a two-part framework to solve this:

  1. Ambiguity Detection via Query Logs: Instead of relying on pre-defined categories or expensive on-the-fly text analysis, the system looks at historical "query refinements" in search logs. If users frequently follow a search for "leopard" with "leopard mac os x" or "leopard tank," the system learns that "leopard" is ambiguous and identifies its common specializations.
  2. The OptSelect Algorithm: This is the core innovation. Traditional algorithms like IASelect and xQuAD are "greedy" and iterative—they pick the best document, then re-calculate the "marginal utility" of all remaining documents before picking the next one.
  3. The "Aha" Moment: The authors realized they could simplify the objective function. By treating diversification as a direct maximization of overall utility across all specializations, they eliminated the need to re-score the list at every step.
  4. Implementation: OptSelect uses a collection of heaps (efficient data structures for finding the "top" items) to track the best documents for each specialization. This changes the computational complexity from $O(nk)$ to $O(n \log k)$, where $n$ is the number of candidate documents and $k$ is the size of the final results list.

Datasets

The researchers evaluated their approach using:

  • TREC 2009 Web Track (Diversity Task): Specifically the ClueWeb-B dataset, containing 50 million English web documents and 50 test topics with manually identified sub-topics.
  • AOL Query Log: ~20 million queries from 650,000 users.
  • MSN Search Query Log: ~15 million queries.
  • Yahoo! BOSS: Used as a baseline search engine to retrieve initial result sets for re-ranking.

Key Insights and Ideas

  • Query Logs as a Proxy for Intent: You don't need a manual taxonomy of the world's knowledge. Users tell you what they mean through their follow-up queries.
  • Efficiency is a Feature: The paper argues that an algorithm that is 1% more "effective" but 1000% slower is actually a failure in a web-scale context.
  • Mathematical Relaxation: By slightly relaxing the constraints of the diversification problem, the authors moved from a "covering" problem (which is slow) to a "utility maximization" problem (which is fast), without losing measurable quality in the eyes of the user.

Key Results

  • Massive Speedup: In tests with 100,000 candidate documents and a 1,000-result output list, OptSelect took roughly 14 milliseconds, while its competitors (xQuAD and IASelect) took nearly 3,000 to 4,000 milliseconds.
  • Comparable Quality: Despite the speed, OptSelect performed just as well as the slower state-of-the-art methods across standard metrics like $\alpha$-NDCG (which measures diversity) and IA-P (intent-aware precision).
  • Real-World Utility: When tested against the original Yahoo! BOSS results, the OptSelect re-ranking improved the "usefulness" measure of the results list by a factor of 5 to 10.

Limitations and Future Work

  • Cold Start Problem: The method relies on query logs. If a query is brand new or very rare, the system won't have the "specializations" needed to diversify it effectively.
  • Personalization: The current model diversifies for the "average" user. The authors suggest that future work could use an individual's specific search history to personalize which "slices" of the diversity are shown to them.
  • Parallelization: The authors suggest exploring how this diversification task could be performed in parallel with the initial document scoring phase to save even more time.

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},
}

Loading related content...

Figure