The impact of database selection on distributed searching

Allison L. Powell, James C. French, James P. Callan, Margaret E. Connell, Charles L. VilesSIGIR 2000 · OpenReview

Abstract

The proliferation of online information resources increases the importance of effective and efficient distributed searching. Distributed searching is cast in three parts — database selection, query processing, and results merging. In this paper, we examine the effect of database selection on retrieval performance across three different distributed retrieval testbeds. Our findings reveal that high-quality database selection can result in better retrieval effectiveness than a centralized database. Furthermore, strong performance is achievable when only a few sites are selected, with effectiveness generally increasing as more sites are included. Crucially, we find that maintaining collection-wide information (CWI), such as global idf, is unnecessary when database selection is employed; local information can achieve superior performance. This suggests that distributed systems can be engineered with greater autonomy and less cooperation, and that conceptual database decomposition could even improve centralized system performance.

Introduction

In the early 2000s, the explosion of online resources made it impossible to crawl and index everything into a single, massive "centralized" database. The alternative is distributed searching: sending a query to multiple smaller databases, retrieving results, and merging them. Historically, distributed search was viewed as a "necessary evil" that inevitably performed worse than centralized search. Researchers assumed that to approach centralized performance, systems required topical clustering and expensive Collection-Wide Information (CWI) to normalize scores. This paper challenges these assumptions, demonstrating that with high-quality database selection, distributed searching can actually outperform centralized systems using only local information.

Methodology

The researchers compared three scenarios across different document organizations:

  • Centralized: All documents in one large index (the baseline).
  • dist-CWI: Distributed documents using global statistics for ranking.
  • dist-LI: Distributed documents where each database uses only its own Local Information (LI) for ranking.

To select which databases to search, they employed two methods:

  1. CORI: A realistic, automated selection algorithm.
  2. RBR (Relevant Binary Relation): An "Oracle" selection method that knows exactly where relevant documents reside, representing the theoretical upper bound of performance.

The study utilized 3GB of data from TREC-4 (~700,000 to 1,000,000 documents) partitioned into three testbeds: UBC-100 (100 databases of ~30MB), SYM-236 (236 databases organized by source and date), and UDC-236 (236 databases of 2,900 documents each).

Key Insights and Results

The most striking finding is that "Oracle" selection (RBR) consistently outperformed the centralized baseline. By isolating relevant documents into specific databases and ignoring the "noise" of a massive centralized index, retrieval quality actually improves. In the UBC-100 testbed, RBR selection achieved a precision of 0.686 at 5 documents, significantly higher than the centralized precision of 0.642.

Figure 1: Performance of Oracle (RBR) selection on the UBC-100 testbed, showing distributed search outperforming the centralized baseline.

The Autonomy Advantage

Contrary to expectations, the dist-LI approach often outperformed dist-CWI. This is a significant architectural win; it means distributed nodes can remain autonomous and do not need to constantly synchronize global word counts to be effective. In almost every test case, the dist-LI scenario was statistically superior or equal to the dist-CWI scenario.

The Selection Bottleneck

While the Oracle selection proved distributed search can be superior, the realistic CORI algorithm usually performed worse than the centralized baseline. This "selection gap" highlights that the primary challenge in distributed IR is not the searching or merging, but the selection step itself. Using CORI, precision improved steadily as the number of selected databases increased from 2 to 20, eventually approaching centralized performance.

Figure 2: Performance of the CORI selection algorithm, highlighting the performance gap between automated selection and the centralized gold standard.

Conclusion and Future Work

This research demonstrates that distributed search has a higher theoretical ceiling than centralized search. The primary limitation remains the "Selection Gap"—current automated algorithms like CORI cannot yet reach the performance levels of an Oracle selector.

Future work should focus on:

  1. Improving Selection Algorithms: Developing methods that approach "Oracle" performance.
  2. Pseudo-Distributions: Applying conceptual database decomposition in centralized systems to filter noise before ranking.
  3. Merging Strategies: Further exploring why local information normalization is so effective and how to optimize it.

Summary updated

Abstract

The proliferation of online information resources increases the importance of effective and efficient distributed searching. Distributed searching is cast in three parts — database selection, query processing, and results merging. In this paper we examine the effect of database selection on retrieval performance. We look at retrieval performance in three different distributed retrieval testbeds and distill some general results. First we find that good database selection can result in better retrieval effectiveness than can be achieved in a centralized database. Second we find that good performance can be achieved when only a few sites are selected and that the performance generally increases as more sites are selected. Finally we find that when database selection is employed, it is not necessary to maintain collection wide information (CWI), e.g. global idf. Local information can be used to achieve superior performance. This means that distributed systems can be engineered with more autonomy and less cooperation. This work suggests that improvements in database selection can lead to broader improvements in retrieval performance, even in centralized (i.e. single database) systems. Given a centralized database and a good selection mechanism, retrieval performance can be improved by decomposing that database conceptually and employing a selection step.
BibTeX
@inproceedings{powell2000impact,
  author = {Allison L. Powell and James C. French and James P. Callan and Margaret E. Connell and Charles L. Viles},
  title = {{The impact of database selection on distributed searching}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2000},
  url = {https://openreview.net/forum?id=HkbanHWdbB},
}
Figure