Abstract
Prior research under a variety of conditions has shown the CORI algorithm to be one of the most effective resource selection algorithms, but the range of database sizes studied was not large. This paper shows that the CORI algorithm does not do well in environments with a mix of "small" and "very large" databases. A new resource selection algorithm is proposed that uses information about database sizes as well as database contents. We also show how to acquire database size estimates in uncooperative environments as an extension of the query-based sampling used to acquire resource descriptions. Experiments demonstrate that the database size estimates are more accurate for large databases than estimates produced by a competing method; the new resource ranking algorithm is always at least as effective as the CORI algorithm; and the new algorithm results in better document rankings than the CORI algorithm.
Introduction
In the field of federated search, also known as distributed information retrieval, a central broker must efficiently navigate hundreds or thousands of independent databases. The primary challenge is Resource Selection: identifying the small subset of databases most likely to contain relevant documents for a given query. In "uncooperative" environments, such as the open web, the broker lacks direct access to database statistics, making selection difficult.
For years, the CORI algorithm served as the industry standard, primarily relying on content similarity. However, as databases grew more diverse in scale, a critical flaw emerged. CORI often fails in environments with a mix of very small and very large databases. If a massive database and a tiny one share similar content profiles, the massive one likely contains significantly more relevant documents due to its scale. Without accounting for database size, content-based algorithms like CORI cannot weight these resources correctly.
Methodology
To address these limitations, Luo Si and Jamie Callan introduced ReDDE (Relevant Document Distribution Estimation). ReDDE explicitly estimates how relevant documents are distributed across multiple databases by incorporating size as a primary signal.
The Sample-Resample Method
Estimating the size of an uncooperative database requires a clever workaround. The authors propose a "sample-resample" technique. First, query-based sampling is used to pull a small set of documents and create a "resource description." Then, terms are selected from this sample and sent back to the database as queries. By comparing the document frequency of these terms within the sample against the total counts returned by the remote search engine, the total number of documents in the database can be mathematically estimated with high accuracy.
The ReDDE Algorithm
ReDDE moves beyond simple term overlap by estimating the actual number of relevant documents in each database. The process involves:
- Centralized Sample Database: Creating a "mini-world" index of all documents sampled from all sources.
- Global Ranking: Ranking the user's query against this centralized sample.
- Mapping and Scaling: Mapping the top-ranked sample documents back to their original databases and scaling these counts based on the estimated total size of each database. This predicts the global distribution of relevant documents.
Experimental Evaluation
The authors evaluated ReDDE against CORI using several TREC-based testbeds, ranging from uniform collections to highly skewed environments where a few databases were 10–20 times larger than others.
In uniform environments like trec123-100col, ReDDE performs comparably to CORI. However, its true strength is revealed in skewed datasets. In these scenarios, content similarity alone is a trap; ReDDE correctly identifies that larger databases hold more potential "hits."
Key Insights and Results
- Size is a Signal: In federated search, scale matters. ReDDE's ability to incorporate size estimates allows it to outperform algorithms that rely solely on content similarity.
- Accuracy in Uncooperative Environments: The "sample-resample" method proved significantly more accurate than previous baselines, particularly for large databases, with minimal overhead.
- Retrieval Precision: In the most challenging skewed environments, a modified version of ReDDE improved top-tier precision by over 46% compared to CORI. This was achieved by balancing aggressive selection with a "backoff" strategy to ensure the "long tail" of relevant documents in secondary databases wasn't entirely ignored.
Conclusion
ReDDE represents a significant advancement in resource selection by demonstrating that database size is as critical as content similarity. While the current implementation relies on some empirical constants, future work may automate these parameters through machine learning. ReDDE provides a robust framework for efficient search across the diverse and uncooperative landscape of the modern web.
Summary updated