Topic-based Index Partitions for Efficient and Effective Selective Search

Anagha Kulkarni, Jamie CallanLSDS-IR @ SIGIR 2010 · OpenReview

Introduction

In large-scale information retrieval, the standard approach to managing massive document collections is to partition them into shards distributed across multiple servers. Typically, search engines perform an exhaustive search, querying every shard and merging the results. While parallelization keeps this process fast, it is extremely resource-intensive, creating a significant bottleneck for organizations without massive computing clusters.

This paper explores selective search: the ability to identify and query only the few shards most likely to contain relevant documents. The authors demonstrate that by partitioning indexes into topic-based shards, it is possible to achieve search accuracy comparable to—or even exceeding—exhaustive search while processing as little as 1% to 6% of the total data.

Methodology: Scalable Topical Partitioning

The core challenge of selective search is organizing documents so that those relevant to a specific topic are clustered together. The authors compare three allocation policies:

  1. Random: Documents are assigned to shards with equal probability.
  2. Source-based: Documents are grouped by their URLs (e.g., keeping all pages from a single domain together).
  3. Topic-based: Documents are grouped by content using K-means clustering.

Scaling to Half a Billion Documents

Clustering 500 million documents is computationally prohibitive. To address this, the authors propose a scalable approximation technique:

  • Sampling: K-means is performed on a tiny, uniform sample of the collection (as low as 0.01%).
  • Projection: The remaining documents are projected into the nearest cluster using a negative Kullback-Leibler (KL) divergence metric.
  • Resource Selection: At query time, a variation of the ReDDE algorithm is used to rank and select the most relevant shards based on a "Central Sample Index."

Key Insights

The Power of Sampling

Based on Heaps’ Law, which describes the relationship between vocabulary size and corpus size, a very small sample of a large collection is sufficient to capture the overall "topic space." The authors found that increasing the sample size beyond a certain point yields diminishing returns for cluster quality while significantly increasing computation time.

Topical Coherence

The resulting shards exhibit remarkable semantic consistency. Instead of a random mix of documents, each shard becomes a specialized repository for specific subjects.

Example word distributions for nine topical shards, demonstrating high semantic coherence.

As shown in the table above, shards naturally organize into distinct categories such as politics (Topic A), cooking (Topic C), and music (Topic D). This concentration allows the search engine to ignore over 95% of the index for most queries without losing relevant information.

Noise Reduction

A surprising finding is that selective search on topical shards can sometimes outperform exhaustive search. By focusing only on the most relevant topical shards, the system effectively filters out "noise"—irrelevant documents from unrelated shards that might have matched query terms by chance.

Experimental Results

The authors evaluated their approach on three massive TREC datasets: Gov2 (~25 million documents), Clue-CatB (~50 million documents), and Clue-CatA-Eng (~504 million documents).

Efficiency and Effectiveness

Topic-based allocation consistently outperformed both random and source-based methods. On the Gov2 dataset, searching just a single topical shard (representing 1.24% of the collection) achieved high precision.

Performance comparison on the Gov2 dataset showing K-means superiority in precision and cost-efficiency.

On the larger ClueWeb datasets, searching the top 3 topical shards provided a 10% to 30% improvement in Precision at 10 (P10) over exhaustive search. This confirms that topical partitioning is not only efficient but also enhances the quality of the top results.

Conclusion

This research demonstrates that topic-based index partitioning is a viable and highly effective strategy for large-scale information retrieval. By using a scalable sampling and projection approach, systems can achieve state-of-the-art search performance while drastically reducing the computational cost. Future work may explore dynamic shard counts per query and methods for handling rapidly evolving document collections.

Summary updated

BibTeX
@inproceedings{kulkarni2010topic,
  author = {Anagha Kulkarni and Jamie Callan},
  title = {{Topic-based Index Partitions for Efficient and Effective Selective Search}},
  booktitle = {LSDS-IR @ SIGIR},
  year = {2010},
  url = {https://openreview.net/forum?id=SJZ_DUbdWB},
}
Figure