Abstract
Federated search links multiple search engines into a single, virtual search system. Most prior research of federated search focused on selecting search engines that have the most relevant contents, but ignored the retrieval effectiveness of individual search engines. This omission can cause serious problems when federating search engines of different qualities. This paper proposes a federated search technique that uses utility maximization to model the retrieval effectiveness of each search engine in a federated search environment. The new algorithm ranks the available resources by explicitly estimating the amount of relevant material that each resource can return, instead of the amount of relevant material that each resource contains. An extensive set of experiments demonstrates the effectiveness of the new algorithm.
Introduction
Federated search, also known as distributed information retrieval, typically involves three critical phases: resource description (discovering what is in remote databases), resource selection (choosing the best databases for a specific query), and result merging. Historically, the research community has focused heavily on the "content" aspect of resource selection—identifying which databases contain the most relevant documents.
However, this approach overlooks a critical real-world variable: the quality of the remote search engine itself. A database might contain highly relevant documents, but if its internal search algorithm is poorly tuned or outdated (e.g., a basic Boolean engine), those documents may never be returned to the user. This paper introduces Returned Utility Maximization (RUM), an algorithm designed to model and account for the retrieval effectiveness of individual search engines within a federation.
Methodology: Returned Utility Maximization (RUM)
The core innovation of RUM is shifting the optimization goal from maximizing contained utility to maximizing returned utility. Since the internal mechanics of remote search engines are often opaque (the "Hidden Web" problem), RUM employs a surrogate approach to estimate effectiveness.
Effectiveness Profiling
RUM builds a "retrieval effectiveness profile" for each resource by sending a set of training queries to the remote engines. The results are compared against a "gold standard"—a well-tuned centralized retrieval algorithm (like INQUERY) running on a local sample of the data. By analyzing the consistency between the remote engine's rankings and the gold standard, RUM can identify which engines are likely to underperform.
Probability Mapping and Optimization
The system uses a logistic model to map centralized document scores to actual probabilities of relevance. Resource selection is then formalized as an optimization problem: given a query, which combination of resources is statistically most likely to return the highest number of relevant documents?
Experimental Setup
The researchers evaluated RUM using two primary TREC (Text REtrieval Conference) testbeds, representing different scales and data distributions.
- Trec123: Comprising 100 collections from TREC CDs 1, 2, and 3, this testbed represents a heterogeneous environment with relatively balanced resource sizes.
- WT10g: A larger-scale web collection partitioned into 934 collections by server, characterized by many small and "noisy" resources.
To simulate real-world variability in search engine quality, the authors introduced "ineffective" engines into the federation, using algorithms like Extended Boolean or poorly tuned Language Models.
Results and Discussion
The experiments compared RUM against the long-standing CORI baseline and the Unified Utility Maximization (UUM) model.
Performance in Uncooperative Environments
RUM demonstrated its greatest strengths in environments with low-quality search engines. When one-third of the engines in the Trec123 federation were ineffective, RUM significantly outperformed UUM.
As shown in Table 2, RUM achieved precision gains of 13.5% to 16.0% over UUM. When the proportion of ineffective engines was increased to two-thirds, the performance gap widened further, with RUM outperforming UUM by 15% to 24%. Analysis confirmed that RUM successfully learned to bypass resources using inferior algorithms, favoring those with more robust engines like SMART or INQUERY.
Scaling and Robustness
On the WT10g testbed, RUM's advantage was present but slightly less pronounced. This is attributed to the small size of many resources in that collection; shorter ranked lists provide less data for building accurate effectiveness profiles. Crucially, RUM proved to be "safe": in environments where all search engines were highly effective, RUM performed at parity with existing state-of-the-art models.
Conclusion
RUM addresses a significant gap in federated search by recognizing that content relevance is only half the battle; the effectiveness of the retrieval engine is equally vital. By modeling returned utility, RUM provides a more robust framework for searching the diverse and often uncooperative landscape of the deep web. Future work will focus on refining effectiveness profiles for small resources and reducing the computational overhead of the training phase.
Summary updated