Federated Search

Searching several engines that cannot be merged into one index. The three problems of describing each engine, selecting which to ask and merging what they return, with CORI and ReDDE as their papers define them, a proof that shared statistics make the merged list identical to a single index, the reason local idf misleads, the sampling variance behind ReDDE, and merging by weights, by normalization and by regression. An experiment splits Cranfield into ten engines and measures selection and merging against the single index. Worked problems compute a CORI belief, a ReDDE ranking and a merged list by hand.

Cranfield query 185 asks for experimental studies on panel flutter. Suppose the 1,400 abstracts are held by ten separate search engines, grouped by subject, each with its own index and its own statistics. Seven of the query's nine relevant abstracts are in one engine and two are in another. The other eight engines hold none. A searcher who asks all ten gets ten ranked lists whose scores mean ten different things. Which engines should be asked, and how are the lists to be made into one? Ask the few engines whose contents match the query, and put their documents on a common scale before sorting. This article is about how to do both without access to the engines' indexes.

Federated search, also called distributed information retrieval, is in the words of Shokouhi and Si (2011) "a technique for searching multiple text collections simultaneously". Queries go to the collections most likely to hold relevant documents, and the returned results are merged into one list. It differs from the partitioned index of search at scale in who is in charge. There one operator cuts one collection into shards, assigns documents at random and can give every shard the same statistics. Here the collections belong to different owners or serve different subjects, their engines may rank differently, and no one can merge the indexes. Callan (2000) divides the task into three problems, which organize this article: resource description, what the searcher knows about each engine; resource selection, which engines to ask; and results merging.

Here is the route. First we build the running example, Cranfield split into ten engines, and see what goes wrong when their lists are merged naively. Then we take the three problems in turn. For description, complete statistics and query-based sampling. For selection, CORI and ReDDE, each as its paper defines it. For merging, a proof that shared statistics give exactly the single-index result, and the methods that approximate that without sharing. Then the experiment measures all of it against the single merged index. The article assumes Okapi BM25 and the measures of retrieval evaluation. It links to two course pages that it does not repeat: Bayesian inference networks, from which CORI descends, and Rank Fusion, which merges lists over one collection. Its numbers are computed by tools/experiments/query-processing/federated-search.py.

Three kinds of statement appear. The exactness of merging with shared statistics, the local idf error, the sampling mean and variance behind ReDDE and the bound on round robin are proved on this page. The definitions of CORI, ReDDE and the merging methods, and what their authors measured, are cited. The Cranfield results are an experiment on a small collection cut artificially into engines, reported as what it showed.

Ten engines for one collection

The testbed is made from a collection the site already uses. The 1,400 Cranfield abstracts are clustered by spherical The k-means Algorithm on their TF-IDF vectors into ten groups, and each group becomes a shard: an engine with its own BM25 index, its own document count, document frequencies and average length. A second kind of split, for contrast, deals the abstracts at random into ten shards of 140. Each split is made for 30 seeds. The reference is the single merged index of the course, BM25 on all 1,400 abstracts, whose nDCG@10 over the 225 queries is 0.368.

The topical split of seed 1 is the running example. Its ten shards have 223, 217, 202, 174, 156, 149, 81, 75, 70 and 53 abstracts. For query 185, whose terms after stemming are experiment, studi, panel and flutter, the relevant abstracts lie as follows.

Shard Abstracts Relevant to query 185 Abstracts containing flutter containing panel
3 202 2 4 12
4 174 7 33 14
9 70 0 2 11
the other seven 954 0 17 8

Shard 4 is where flutter is studied: 33 of the collection's 56 abstracts containing the word are there. That concentration is what makes selection possible, and it is also what breaks merging.

What goes wrong with raw scores

Ask shards 4, 3 and 9, let each return its best abstracts with its own BM25 scores, and sort everything by score. This is a raw-score merge. The first six abstracts of the three lists, with the scores the single index gives the same abstracts:

Abstract Shard Shard's own score Single-index score Relevant
856 4 13.461 18.038 yes
857 4 12.262 16.564 yes
864 3 12.279 12.669 no
627 3 11.413 12.029 no
658 9 10.257 13.427 no
914 9 8.049 10.122 no

By the shards' own scores, abstract 864 outranks 857, and abstract 627 is close behind. By the single index, the two relevant abstracts lead by a wide margin. Shard 4 has marked its own documents down. The raw-score merge of the three full lists has an nDCG@10 of 0.663 on this query, against 0.830 when the same three shards score with shared statistics.

The cause is idf. BM25's idf for flutter is 3.211 in the whole collection. In shard 4, where 33 of 174 abstracts contain the word, it is 1.653. In shard 3, where 4 of 202 do, it is 3.809. The word that defines the query's subject counts for half as much in the shard about that subject as it does in a shard where it barely occurs.

The formal version. BM25's idf, $\ln\left(1 + \frac{N - \mathit{df} + 0.5}{\mathit{df} + 0.5}\right)$, is close to the plain $\ln(N/\mathit{df})$ when the term is in a small share of the documents, and the plain form shows the effect most simply. Write the plain idf as $\ln(N/\mathit{df})$, and let shard $j$ hold $N_j$ documents of which $\mathit{df}_j$ contain the term. The shard's idf minus the collection's is

$$\ln\frac{N_j}{\mathit{df}_j} - \ln\frac{N}{\mathit{df}} = -\ln\frac{\mathit{df}_j/N_j}{\mathit{df}/N}.$$

The fraction on the right is the term's concentration in the shard: the share of the shard's documents that contain it, over the share of all documents that do. Where the term is concentrated, the ratio exceeds one and the shard's idf is too low. Where it is scarce, the idf is too high. Search at Scale derives the same expression for random shards of equal size. There the ratio stays near one for common terms and departs from it only for rare ones, a term in one or two documents being over-represented in whichever shard holds it. In a collection divided by subject the ratio is large for common terms too, and exactly for the terms and the shards that matter to a query on that subject. Callan (2000) describes the effect in these terms: documents from databases where a query term is common, "probably a good database for the query", tend to have low scores because of low idf values.

The three problems are now concrete. We need to know that shard 4 is the place to look. We need to choose it. And we need to stop its documents from being penalized for living there.

Resource description

What can be known about an engine without holding its index? Two answers are in use.

Cooperative descriptions. Each engine publishes summary statistics of its collection. For the methods below, the useful ones are the engine's document frequency for every term and the size of its collection. In the experiment this is called the complete description. It needs the engines to cooperate, and Callan (2000) lists why that fails outside a single organization. A provider may be unable or unwilling, or may misrepresent its contents. And even honest descriptions are not comparable when engines stem, stop and tokenize differently.

Query-based sampling. The alternative asks nothing of an engine but that it answer queries. Send it a one-term query, download the few top documents, choose the next query term at random from the documents downloaded so far, and repeat. The documents collected are a sample of the collection, and their term statistics stand in for the collection's. Callan (2000) describes the method, with four documents taken per query and the first term drawn from another resource. Si and Callan (2003a) used it to collect 300 documents per database, which took about 80 queries. Callan's experiments found that the vocabulary and the term frequencies of a database were learned quickly, and that retrieval with learned descriptions was about as effective as with complete ones.

The sample has a second use that matters more than the first. The samples of all the engines, put together, form a small index of their own, the centralized sample index. It is the only place where documents from different engines are scored by the same statistics. ReDDE and the regression method of merging are both built on it.

In the experiment each shard is sampled until 30 abstracts are collected, or the whole shard in the few cases where a shard is smaller than that, which took a median of 16.7 queries per shard. In the running example that is 300 of 1,400 abstracts, a far larger share than the 300 documents per database of the papers, whose databases held thousands of documents. The experiment's sampled descriptions are therefore richer, in proportion, than a real system's would be.

The size of a collection is not in a sample, and ReDDE needs it. Si and Callan (2003a) estimate it by what they call sample-resample. Pick a term from the sample, and ask the engine how many documents match it. If the sample is representative, the term occurs in the same share of the sample as of the collection, $\mathit{df}_{\text{sample}}/n_j \approx \mathit{df}_j/N_j$, so

$$\hat N_j = \mathit{df}_j \cdot \frac{n_j}{\mathit{df}_{\text{sample}}},$$

their equation 8, averaged over a few terms. They used five. Si and Callan report that both their method and the one they compare it with "tended to underestimate database size". The formula alone does not settle the direction. One effect pushes the estimate down: a term can only be picked if it is in the sample, and terms that made it into a small sample are on average over-represented there, which inflates $\mathit{df}_{\text{sample}}$. Another pushes it up: the estimate is proportional to $1/\mathit{df}_{\text{sample}}$, a convex function, so random variation in $\mathit{df}_{\text{sample}}$ raises its average. And a query-based sample is not a uniform one. The net direction is an empirical matter, and here it agrees with theirs. In the running example the ten estimates add up to 1,100 for a true total of 1,400, and over the 30 topical splits the median of the mean absolute error ratio, $|\hat N_j - N_j|/N_j$ averaged over shards, is 0.279.

Resource selection

Given descriptions, which engines should a query be sent to? The standard of comparison is the ranking of the engines by the number of relevant documents each holds, which the literature calls the relevance-based ranking. Si and Callan (2003a) measure a selection method by how much of that it captures. If the method's ranking puts engines holding $E_1, E_2, \ldots$ relevant documents first, second, and so on, and the relevance-based ranking has $B_1 \ge B_2 \ge \cdots$, then

$$R_m = \frac{E_1 + \cdots + E_m}{B_1 + \cdots + B_m}$$

is the share of the relevant documents obtainable from $m$ engines that the method's first $m$ engines actually hold. (The paper writes $R_k$. This unit keeps $k$ for the number of documents wanted.) For query 185 the relevance-based ranking begins with shards 4 and 3, so $B_1 = 7$ and $B_2 = 2$.

CORI

Callan, Lu and Croft (1995) rank collections the way INQUERY ranks documents. Their observation is that ranking collections is analogous to ranking documents. The network of Bayesian inference networks then applies with a collection in the place of a document. The number of documents in the collection that contain a term takes the place of the term's frequency in a document, and the number of collections that contain the term takes the place of its document frequency. They call the result a collection retrieval inference network, or CORI net.

In the form given by Callan (2000, equations 5.1 to 5.3), the belief that engine $j$ satisfies a query term $t$ is

$$T = \frac{\mathit{df}_j}{\mathit{df}_j + 50 + 150\,\mathit{cw}_j/\overline{\mathit{cw}}}, \qquad I = \frac{\ln\frac{S + 0.5}{\mathit{cf}_t}}{\ln(S + 1)}, \qquad p(t \mid j) = d_b + (1 - d_b)\,T\,I,$$

where $\mathit{df}_j$ is the number of documents of engine $j$ that contain $t$, $\mathit{cw}_j$ the number of words in engine $j$'s collection, $\overline{\mathit{cw}}$ the mean of that over the engines, $S$ the number of engines, $\mathit{cf}_t$ the number of engines whose collections contain $t$, and $d_b = 0.4$ the default belief. (Callan writes $b$ for the default belief and $C$ for the number of engines.) The beliefs of a query's terms are combined by the query operators of the inference network. For a plain list of terms that is their mean.

Every part has a counterpart on the course page. $T$ is the saturating term-frequency curve of INQUERY's document belief, with a constant that grows with the size of the collection as the document's does with its length. $I$ is the scaled idf, counted over engines. The default belief is the same 0.4. The constants 50 and 150 come from the 1995 paper, which scaled $\mathit{df}_j$ by $\mathit{df}_j + K$ with $K$ a multiple of $(1 - \beta) + \beta\,\mathit{cw}_j/\overline{\mathit{cw}}$, and found a multiple of 200 with $\beta = 0.75$ best on its TREC collections: $200 \times 0.25 = 50$ and $200 \times 0.75 = 150$. (The paper's own letters for the multiple and for $\beta$ are $k$ and $b$, which this unit reserves for BM25.)

Two consequences follow from the formula. A belief lies between $d_b$, for an engine without the term, and $d_b + (1 - d_b)\,I$, approached as $\mathit{df}_j$ grows. So for a given query every engine's score lies between $R_{\min} = d_b$ and $R_{\max}$, the mean over the query's terms of $d_b + (1 - d_b)I$, which are the values Callan (2000) obtains by setting $T$ to 0 and to 1. And a term found in every engine has $I = \ln\frac{S + 0.5}{S}/\ln(S+1)$, close to zero, so it barely distinguishes engines.

Back to query 185. Flutter occurs in 7 of the 10 shards and panel in 6. Experiment and studi occur in all 10. For shard 4, with 22,589 words against a mean of 15,630.9, the constant is $50 + 150 \times 22{,}589/15{,}630.9 = 266.77$, and for flutter

$$T = \frac{33}{33 + 266.77} = 0.1101, \qquad I = \frac{\ln(10.5/7)}{\ln 11} = 0.1691, \qquad p = 0.4 + 0.6 \times 0.1101 \times 0.1691 = 0.4112.$$

The four beliefs of shard 4 are 0.4017 for experiment, 0.4012 for studi, 0.4070 for panel and 0.4112 for flutter, and their mean, the shard's score, is 0.4053. That is the highest of the ten. The next are shard 9 at 0.4042 and shard 3 at 0.4032, and the lowest is 0.4007. For this query $R_{\max} = 0.4665$. CORI's first three shards are 4, 9 and 3, which hold all nine relevant abstracts, so $R_1 = 7/7$, $R_2 = 7/9$ and $R_3 = 9/9$.

The scores are crowded into the bottom of their range, because the constants 50 and 150 were set for collections of tens of thousands of documents and these shards have at most a few hundred, so $T$ stays small. The ranking is what counts, and it is right at the top. Shard 9 is second for a reason the formula makes plain: 11 of its 70 abstracts contain panel, and its small size gives it a small constant. It holds abstracts about panels and none of the relevant ones.

ReDDE

CORI scores how well an engine's vocabulary matches the query. Si and Callan (2003a) argue for estimating directly the quantity that the relevance-based ranking is made of: how many relevant documents each engine holds. Their method is ReDDE, for relevant document distribution estimation.

Here is the idea in one sentence: rank the sample documents of all engines together, let each sample document stand for the many unsampled documents like it, and count how many of the best-ranked documents each engine would therefore contribute.

The method. Let engine $j$ hold $N_j$ documents, of which $n_j$ were sampled. The number of documents in engine $j$ relevant to the query is $\sum_{d \in j} P(\text{rel} \mid d)$. Each sampled document represents $N_j/n_j$ documents of its engine, so the sum is estimated from the sample (their equation 11):

$$\widehat{\text{Rel}}(j) = \sum_{d \,\in\, \text{sample of } j} P(\text{rel} \mid d)\;\frac{\hat N_j}{n_j}.$$

For $P(\text{rel} \mid d)$ they use a step. Imagine all the engines' documents in one index, the centralized complete database, searched by an effective method. A document is given a constant probability of relevance if it ranks within a fixed share of the top of that list, and zero otherwise (their equation 12). The share is a parameter, the ratio, which they set to 0.003. The complete index does not exist, so the rank of a sample document in it is estimated from the centralized sample index. Search the sample index, and count each document ranked above $d$ there as the $\hat N/n$ documents it represents (their equation 13):

$$\widehat{\text{rank}}(d) = \sum_{d' \text{ ranked above } d} \frac{\hat N_{j(d')}}{n_{j(d')}}.$$

The engines are ranked by $\widehat{\text{Rel}}(j)$, normalized to sum to one (their equation 14). The unknown constant cancels.

Back to query 185. The centralized sample index holds 300 abstracts, and the size estimates total 1,100. With 1,100 documents the paper's ratio of 0.003 would count three. The experiment uses 0.02, a cutoff of estimated rank 22. The top of the sample ranking is:

Sample abstract Shard Represents $\hat N_j/n_j$ Estimated rank before it Counted
899 7 3.10 0.00 yes
729 9 1.20 3.10 yes
753 5 4.19 4.30 yes
1290 4 6.66 8.49 yes
686 4 6.66 15.15 yes
202 7 3.10 21.81 yes
725 9 1.20 24.91 no

Shard 4 collects $2 \times 6.66 = 13.32$, shard 7 collects 6.20, shard 5 collects 4.19 and shard 9 collects 1.20, of a total 24.91. The estimated distribution is 0.535 for shard 4, 0.249 for shard 7, 0.168 for shard 5, 0.048 for shard 9 and zero for the rest. ReDDE ranks shard 4 first, as CORI does, and then goes astray: shards 7 and 5 hold no relevant abstract. So $R_1 = 1$ and $R_2 = R_3 = 7/9$. None of the seven sample abstracts in the table is relevant, and no sampled abstract of shard 3 ranked high enough to be counted. The estimate was built on six documents.

How much can a sample know?

That fragility can be quantified. The following result isolates the sampling step of ReDDE from its other approximations.

Theorem 1 (the scaled count is unbiased, with hypergeometric variance). Let engine $j$ hold $N_j$ documents, and let $A$ be a fixed set of documents, $a_j$ of them in engine $j$. Draw $n_j$ of the engine's documents uniformly at random without replacement, and let $X$ be the number of them in $A$. Then

$$E\!\left[\frac{N_j}{n_j}X\right] = a_j, \qquad \operatorname{Var}\!\left[\frac{N_j}{n_j}X\right] = \left(\frac{N_j}{n_j}\right)^{2} n_j\,\frac{a_j}{N_j}\left(1 - \frac{a_j}{N_j}\right)\frac{N_j - n_j}{N_j - 1}.$$

Proof. Write $N$, $n$ and $a$ for $N_j$, $n_j$ and $a_j$. For each of the $a$ documents of $A$ in the engine, let $Y_d$ be 1 if it is drawn and 0 otherwise, so that $X = \sum_d Y_d$. Each document is drawn with probability $n/N$, so $E[X] = a\,n/N$, and multiplying by $N/n$ gives $a$. For the variance, $\operatorname{Var}(Y_d) = \frac{n}{N}\left(1 - \frac{n}{N}\right)$. Two different documents are both drawn with probability $\frac{n(n-1)}{N(N-1)}$, so

$$\operatorname{Cov}(Y_d, Y_{d'}) = \frac{n(n-1)}{N(N-1)} - \frac{n^2}{N^2} = -\frac{n(N - n)}{N^2(N-1)}.$$

There are $a$ variances and $a(a-1)$ ordered pairs:

$$\operatorname{Var}(X) = a\,\frac{n(N-n)}{N^2} - a(a-1)\,\frac{n(N-n)}{N^2(N-1)} = \frac{a\,n\,(N-n)}{N^2}\cdot\frac{N - a}{N - 1} = n\,\frac{a}{N}\left(1 - \frac{a}{N}\right)\frac{N - n}{N - 1}.$$

Multiplying by $(N/n)^2$ gives the statement. $\blacksquare$

Take $A$ to be the relevant abstracts of query 185. Shard 4 holds 7 of them among 174 abstracts, and 30 are sampled. The expected number of relevant abstracts in the sample is $30 \times 7/174 = 1.21$. The scaled count has mean 7 and standard deviation 5.70. And the probability that the sample contains none of the seven is $\binom{167}{30}\big/\binom{174}{30} = 0.259$. A quarter of the time, a uniform sample of 30 has nothing relevant to rank for this shard, whatever is done with it afterwards. For shard 3, with 2 relevant among 202, that probability is 0.724.

The theorem is the favorable case. Query-based sampling is not uniform, the set that ReDDE counts is defined by estimated ranks and not by relevance, and the sizes are estimates. The theorem says that even with those removed, an estimate built on a sample of this size is coarse for an engine with few relevant documents. It also says what helps: the variance falls as $n_j$ approaches $N_j$.

Merging the results

The selected engines return ranked lists. The documents in them are different documents: the engines' collections do not overlap. That is the difference from Rank Fusion, and it removes the evidence fusion relies on. Si and Callan (2003b) draw the line the same way: in metasearch "multiple retrieval algorithms are applied to a single database or to similar databases", and agreement between the lists is informative. Here no document appears twice, and there is nothing to agree on.

With shared statistics, merging is exact

The easy case first. Suppose the engines cooperate fully: every engine scores with the same function and the same collection-wide statistics.

Theorem 2 (shared statistics reproduce the single index). Let every engine score its documents with the function, and the statistics, of the single merged index, and return its $k$ best. Then the $k$ best documents of the lists put together are exactly the $k$ best of the single index, in the same order, provided ties are broken by the same rule everywhere.

Proof. Each document has the same score in its engine as in the single index, so the two orderings agree on every pair of documents. Let $d$ be among the single index's $k$ best. Fewer than $k$ documents of the whole collection precede $d$, so fewer than $k$ documents of $d$'s own engine precede it, and $d$ is among the $k$ that engine returns. So all of the single index's $k$ best are among the returned documents. Sorting the returned documents by score puts them in the single index's order, and its $k$ best come first. $\blacksquare$

The script checks the theorem on every query of every split: with all ten shards scoring by global statistics and returning 20 abstracts each, the merged top ten is the single index's top ten. This is the arrangement Search at Scale describes for one operator's shards, with the global statistics computed periodically and distributed. Callan, Lu and Croft (1995) call it merging on normalized scores and use it as their baseline. It is not available when the engines are not ours.

Without them

Five ways to merge without shared statistics are measured below.

Round robin. Take the first document of each list, then the second of each, and so on. It needs only ranks. Callan, Lu and Croft (1995) found simple interleaving "extremely ineffective", because it promotes the documents of engines that have nothing relevant. A bound shows how much it can lose.

Example (the ceiling on round robin). Suppose $m$ engines are searched, all the relevant documents are in one of them, and each of the other engines returns at least $\lceil 10/m \rceil$ documents. Then round robin places at most $\lceil 10/m \rceil$ of the good engine's documents in the first ten, since each round contributes one from every engine. With three engines that is four, so precision at ten cannot exceed 0.4 however good the one engine is. The condition on the other engines matters: an engine that runs out of documents drops out of the rounds and leaves its places to the rest. In the experiment every shard returns 20. Reciprocal rank fusion does no better here. The lists are disjoint, so the document at rank $r$ of any list has the fused score $1/(60 + r)$ and nothing else. All the first-ranked documents tie, then all the second-ranked, and so on. Whatever rule breaks the ties within a rank, the result is a round-robin merge, with the engines taken in the order that rule gives.

Raw scores. Sort by the engines' own scores. This is right when the scores are comparable and wrong in the way the running example showed. The 1995 paper measured losses of 10 to 20 percent in average precision from it.

Weights from selection. The CORI papers' answer uses what selection already computed: an engine that scored high for the query is probably a good one, so its documents are raised. In the form of Callan (2000, equations 5.11 and 5.12), the engine's score $R_j$ is first placed within the range it could take for this query, and then scales the document score $D$:

$$R'_j = \frac{R_j - R_{\min}}{R_{\max} - R_{\min}}, \qquad D'' = \frac{D + 0.4\,D\,R'_j}{1.4}.$$

A document from the best possible engine keeps its score, and one from the worst possible engine is multiplied by $1/1.4$. Callan reports that these two equations were the core of INQUERY's distributed retrieval for several years. He then names their weakness, which is the idf effect of the running example: when collections are organized by subject, the correction is not enough.

Normalized scores. His remedy (equations 5.13 to 5.15) first divides each document's score by the range of scores its engine could give for the query:

$$D' = \frac{D - D_{\min,j}}{D_{\max,j} - D_{\min,j}}, \qquad D'' = \frac{D' + 0.4\,D'\,R'_j}{1.4}.$$

For BM25 the least possible score is 0, and the greatest, with every query term at saturation, is $D_{\max,j} = (k_1 + 1)\sum_{t} \mathit{idf}_j(t)$ over the query terms the engine holds. Dividing by it cancels the engine's idf scale, which is exactly the part of the score that is not comparable. The price, as Callan notes, is cooperation: the engine must report $D_{\max,j}$, because only it knows its own statistics.

For query 185, $D_{\max}$ is 16.096 in shard 4, 22.094 in shard 3 and 17.407 in shard 9. Abstract 857 has $D' = 12.262/16.096 = 0.762$ and abstract 864 has $D' = 12.279/22.094 = 0.556$. The order of the running example is repaired, and worked problem 3 carries the calculation through.

Regression on the sample. Si and Callan (2003b) remove the need for cooperation with the centralized sample index. Some of the documents an engine returns are also in the sample. For those, two scores are known: the engine's own, and the score in the sample index, which is on one scale for all engines. A straight line fitted through those pairs by least squares maps the engine's scores onto the common scale, and the line is then applied to all of the engine's returned documents. They call the method semisupervised learning, the overlap documents being the labeled data. In the version for engines of different kinds, each engine gets its own line. They require at least three overlap documents to fit a line and train on the ten best of them. When too many of the selected engines have fewer than three, they fall back on the CORI formula for the whole query. The experiment's version is simpler in two respects, stated here so that its numbers are not read as theirs. It trains on every overlap document among the 20 returned. And an engine without three of them uses the line fitted to the overlap documents of all the searched engines together.

The experiment

Every method above is run on all 225 Cranfield queries over each of the 30 topical splits. Selection methods see either the complete descriptions or the samples. Each selected shard returns its 20 best abstracts with its own BM25 scores. All figures are the median over the 30 splits of the mean over queries, and the interquartile ranges, given by the script, are at most 0.09 for the selection measures and under 0.03 for nDCG@10.

Selection

Method Description used $R_1$ $R_2$ $R_3$ $R_5$
CORI complete 0.801 0.843 0.882 0.949
CORI samples 0.708 0.758 0.818 0.914
ReDDE, ratio 0.02 samples, estimated sizes 0.680 0.747 0.807 0.892
ReDDE, ratio 0.02 samples, true sizes 0.699 0.758 0.811 0.895
Largest shards first sizes 0.244 0.347 0.472 0.683
Random order none 0.148 0.218 0.300 0.491

Four things can be read from it.

  • Selection works on topical shards. CORI's first shard holds 80 percent of the relevant abstracts that the best single shard holds, where a random shard holds 15 percent.
  • Sampling costs something. CORI on 30 sampled abstracts per shard loses 0.09 at $R_1$ against CORI on complete statistics.
  • ReDDE is below CORI here, clearly so only at the top. Against CORI on the same samples its median is 0.03 lower at $R_1$ and about 0.01 lower at $R_2$ and $R_3$. Split by split, ReDDE was the lower of the two at $R_1$ on 23 of the 30 splits, at $R_2$ on 21, at $R_3$ on 17 and at $R_5$ on 22, so at $R_3$ the two are nearly even. Against CORI on complete descriptions it was lower on all 30 splits at every cutoff. Si and Callan (2003a) found ReDDE as good as or better than CORI on all five of their testbeds. The clear gains were on testbeds where a few databases were far larger than the rest, and there was little difference where sizes were not very skewed. Two differences from their testbeds may explain the result here, and neither was tested: this testbed has no such giants, and its estimate rests on a handful of sample documents per query, the situation of Theorem 1.
  • Knowing the sizes exactly helps little. Replacing the sample-resample estimates by the true sizes raises $R_1$ by 0.02.

The ratio hardly changes $R_1$: it is 0.678 with the paper's 0.003 and 0.657 with 0.05, against 0.680 with 0.02. It does change $R_3$. With 0.003, $R_3$ falls to 0.735, because so few documents are counted that most shards tie at zero. With 0.05 it is 0.814.

Selection and merging together

How much of the single index's effectiveness survives? In both tables below, "chosen by CORI" means CORI on complete descriptions, the best selection in the table above, and ReDDE uses the samples. First with merging taken out of the question, by letting the selected shards score with shared statistics as in Theorem 2:

Shards searched Chosen by CORI Chosen by ReDDE Chosen by the relevance-based ranking
1 0.321 0.267 0.384
3 0.364 0.343 0.396
5 0.368 0.359 0.384
all 10 0.368 0.368 0.368

The entries are nDCG@10, and the single index scores 0.368. Three shards chosen by CORI on complete descriptions, out of ten, give 0.364. Five give the whole of it. Three shards chosen at random give 0.144. And the oracle that knows where the relevant abstracts are does better than the single index, 0.396 with three shards, because leaving out seven shards also leaves out their nonrelevant abstracts. Kulkarni and Callan (2015) report the same pattern at full scale for what they call selective search, where one operator deliberately cuts a collection into topical shards and searches a few. They found effectiveness on par with searching everything, at much lower cost, and an oracle ranking of shards able to outperform exhaustive search.

Now with real merging, each shard scoring by its own statistics:

Merging method Needs from the engines Three shards chosen by CORI All ten shards
Shared statistics global statistics 0.364 0.368
Regression on the sample nothing 0.316 0.293
Normalized scores $D_{\max}$ per query 0.315 0.261
Weights from selection nothing 0.301 0.254
Raw scores nothing 0.297 0.247
Round robin nothing 0.257 0.157

With CORI on sampled descriptions choosing the three shards, which is the selection a federation without cooperation would have, the three-shard column reads 0.348, 0.315, 0.298, 0.296, 0.291 and 0.242 from top to bottom. The order of the methods is the same.

Three observations.

  • Merging loses more than selection. Choosing three shards of ten costs less than 0.01 of nDCG@10 when the scores are right. Merging those three by raw scores costs a further 0.067. On this testbed the hard problem is the third one.
  • The methods rank as their authors' accounts suggest. Round robin is worst. Raw scores are next. The selection weights add a little, less than 0.01. Normalizing by $D_{\max}$ and regressing on the sample are the best of the methods without shared statistics and are close to each other, the regression needing no cooperation. With all ten shards searched, the regression had its three overlap documents for 77 percent of the returned lists. None of these methods comes within 0.04 of the shared-statistics result.
  • Searching more engines makes imperfect merging worse. Every method below the first row scores lower with all ten shards than with three. Selection is not only a saving. It also keeps out the lists that the merge would misplace.

Example (a common misstatement). "Federated search is a partitioned index whose shards happen to belong to different owners." The random split shows why that is wrong. With the abstracts dealt at random into ten shards, CORI's $R_1$ is 0.434 against 0.326 for a random order: there is little for selection to find, because every shard resembles every other. And the raw-score merge of all ten shards reaches 0.361, against 0.368 for the single index, because the local statistics of random shards are close to the global ones for all but rare terms. On the topical split the same merge reaches 0.247. Random shards make both problems disappear, which is why the operator of a partitioned index creates them. A federation does not get to choose how its documents are divided.

What the experiment does not show

The testbed is small and artificial. The shards have a few hundred abstracts where the papers' databases had thousands, the samples are a fifth of the collection, every engine runs the same BM25 with the same text processing, and Cranfield's queries are long. Engines that differed in their ranking functions would make the raw-score merge meaningless, not merely biased, and would favor the regression, which makes no assumption about how an engine scores. None of that is measured here. The published comparisons on TREC-based testbeds are the evidence for the methods. This experiment shows the mechanisms on a collection small enough to trace by hand.

The same three problems, for an assistant with tools

The setting of this article is no longer only that of library catalogs and web search engines. A language-model assistant that can call several retrieval tools is a federated searcher. The correspondence is direct, and it is offered here as an analogy, not as a measured result.

  • Description. What the assistant knows about each tool is a description written by the tool's provider, which is a cooperative description with the weaknesses Callan lists, or what it has learned from the tool's earlier answers, which is a sample.
  • Selection. Deciding which tool to call for a question is resource selection. Calling every tool for every question is the option that, in the experiment above, lowered effectiveness as well as raising cost.
  • Merging. The tools return results with scores on unrelated scales, or with none. The assistant has to combine them without comparable scores, which is the third problem.

This site is a small instance. Its interface for assistants, described at /openapi.json, offers a search over the pages and a separate listing of the bibliography, two resources with different contents and different kinds of result. A reader that reranks the returned passages itself, by reading them, is in the position of the search client that recomputes scores on its own side, one of the options Callan (2000) lists for merging when engines do not cooperate.

Worked problems

No course text sets exercises on federated search, so these five problems are posed on the running example, query 185 on the topical split of seed 1, and on the results proved above. The script recomputes every number.

Problem 1 (a CORI score by hand). Shard 9 of the running example holds 70 abstracts and 7,039 words. The mean over the ten shards is 15,630.9 words. Its document frequencies for experiment, studi, panel and flutter are 18, 17, 11 and 2, and the terms occur in 10, 10, 6 and 7 of the ten shards. Compute the shard's CORI score for query 185 and explain why it is second.

Solution. The score is 0.4042. The constant is $50 + 150 \times 7{,}039/15{,}630.9 = 117.55$. The scaled idf values are $\ln(10.5/10)/\ln 11 = 0.0203$ for the two terms found in every shard, $\ln(10.5/6)/\ln 11 = 0.2334$ for panel and $\ln(10.5/7)/\ln 11 = 0.1691$ for flutter.

Term $\mathit{df}_j$ $T = \mathit{df}_j/(\mathit{df}_j + 117.55)$ $I$ Belief $0.4 + 0.6\,T\,I$
experiment 18 0.1328 0.0203 0.4016
studi 17 0.1263 0.0203 0.4015
panel 11 0.0856 0.2334 0.4120
flutter 2 0.0167 0.1691 0.4017

The mean of the four beliefs is 0.4042. Nearly all of the shard's advantage over the default 0.4 comes from panel. Its belief of 0.4120 is higher than the 0.4070 that panel earns in shard 4, although shard 4 has more abstracts with the word, 14 against 11. Shard 4 is three times as large in words, so its constant is 266.77, and its $T$ for panel is $14/280.77 = 0.0499$. CORI normalizes by collection size as BM25 normalizes by document length, and a small collection dense in one query term scores well. Two terms carry almost no weight: experiment and studi are in every shard, and their $I$ is a tenth of the others'.

Problem 2 (a ReDDE ranking by hand). Use the table of sample abstracts in the ReDDE section. (a) Confirm the estimated distribution. (b) What would the ranking be with the true shard sizes, 81 for shard 7, 70 for shard 9, 156 for shard 5 and 174 for shard 4, a true total of 1,400, and the same ratio?

Solution. (a) The counted weights are 3.10 + 3.10 = 6.20 for shard 7, 1.20 for shard 9, 4.19 for shard 5 and 6.66 + 6.66 = 13.32 for shard 4. The total is 24.91, and the shares are $13.32/24.91 = 0.535$, $6.20/24.91 = 0.249$, $4.19/24.91 = 0.168$ and $1.20/24.91 = 0.048$.

(b) With true sizes each sample abstract represents $N_j/30$ abstracts: 2.70 for shard 7, 2.33 for shard 9, 5.20 for shard 5 and 5.80 for shard 4. The cutoff is $0.02 \times 1{,}400 = 28$. The estimated ranks before the seven abstracts are 0, 2.70, 5.03, 10.23, 16.03, 21.83 and 24.53, all below 28, so all seven are counted, and so is the eighth, abstract 444 of shard 8, whose rank is 26.87. The ninth, at 29.37, is not. The weights are 11.60 for shard 4, 5.40 for shard 7, 5.20 for shard 5, 4.67 for shard 9 and 2.50 for shard 8. The order is 4, 7, 5, 9, 8: the first four as before, since the same sample abstracts lead the list. Correcting the sizes changed the weights and not the evidence. That is the experiment's fourth finding in one query.

Problem 3 (merging three lists). For query 185, shards 4, 3 and 9 return the six abstracts of the table in the section on raw scores. The shards' CORI scores are 0.4053, 0.4032 and 0.4042, with $R_{\min} = 0.4$ and $R_{\max} = 0.4665$, and their $D_{\max}$ values are 16.096, 22.094 and 17.407. Merge the six abstracts by raw scores, by round robin in CORI's order of shards, by the selection weights, and by normalized scores, and compare with the single index.

Solution. The engine weights $(1 + 0.4R')/1.4$ come first. For shard 4, $R' = (0.4053 - 0.4)/0.0665 = 0.0791$ and the weight is 0.7369. For shard 9 the weight is 0.7324 and for shard 3 it is 0.7279.

Abstract Shard Own score $D$ Weighted $D''$ $D' = D/D_{\max}$ Normalized $D''$ Single-index score
856 4 13.461 9.920 0.836 0.616 18.038
857 4 12.262 9.036 0.762 0.561 16.564
864 3 12.279 8.938 0.556 0.405 12.669
627 3 11.413 8.308 0.517 0.376 12.029
658 9 10.257 7.512 0.589 0.432 13.427
914 9 8.049 5.895 0.462 0.339 10.122
  • Raw scores: 856, 864, 857, 627, 658, 914. A nonrelevant abstract is second.
  • Round robin, shards in the order 4, 9, 3: 856, 658, 864, 857, 914, 627. Nonrelevant abstracts are second and third.
  • Selection weights: 856, 857, 864, 627, 658, 914. The weight of shard 4 is just enough to lift 857 over 864, 9.036 against 8.938.
  • Normalized scores: 856, 857, 658, 864, 627, 914.
  • Single index: 856, 857, 658, 864, 627, 914.

The normalized merge reproduces the single index's order of these six, including the position of abstract 658, which every other method places too low or too high. On the full lists of 20 abstracts per shard the nDCG@10 for this query is 0.540 for round robin, 0.663 for raw scores, 0.709 for the selection weights, 0.826 for normalized scores and 0.830 for shared statistics. The single index itself scores 0.807 on this query, lower than the three-shard merges with shared statistics and with normalized scores, because its fourth abstract is a nonrelevant one from a shard that was not searched.

Problem 4 (what a sample of 30 can see). Shard 3 holds 202 abstracts, 2 of them relevant to query 185. Thirty are sampled uniformly at random. Find the probability that the sample contains neither relevant abstract, and the mean and standard deviation of the scaled count of Theorem 1.

Solution. The probability is 0.724. The first relevant abstract is missed with probability $172/202$, and given that, the second with probability $171/201$: $\frac{172 \times 171}{202 \times 201} = 0.724$, which is $\binom{200}{30}\big/\binom{202}{30}$. The scaled count has mean 2, by the theorem. Its variance is

$$\left(\frac{202}{30}\right)^2 \times 30 \times \frac{2}{202} \times \frac{200}{202} \times \frac{172}{201} = 45.338 \times 0.2517 = 11.41,$$

so the standard deviation is 3.38, larger than the mean. Nearly three times in four the sample gives ReDDE no relevant abstract from this shard, and when it gives one, the estimate jumps to 6.7. This is consistent with the running example, in which the sample of shard 3 held neither of its two relevant abstracts and none of its sample abstracts ranked within the cutoff. The sample there was query-based and not uniform, so the theorem describes it only roughly. The sample of shard 4 held none of its seven relevant abstracts either, an event of probability 0.259 for a uniform sample, and ReDDE still ranked shard 4 first, on the strength of two nonrelevant sample abstracts that ranked high for the query. ReDDE counts documents that rank well, and does not need them to be relevant.

Problem 5 (round robin's ceiling). Five engines are searched. One of them returns ten relevant documents at ranks 1 to 10, and the others return nothing relevant. Find the precision at ten of the round-robin merge, and of a merge that sorts by correct scores, assuming the relevant documents have the highest scores.

Solution. Round robin takes one document from each engine per round, so the first ten places are two rounds, and the good engine supplies two of them: precision at ten is 0.2, which is $\lceil 10/5 \rceil/10$. Sorting by correct scores puts the ten relevant documents first: precision 1. The loss is a factor of five, the number of engines searched. With ten engines the first ten places hold one relevant document. The same mechanism is at work in the experiment, where round robin scores 0.157 with all ten shards against 0.257 with three.

What we have learned

Searching several engines that cannot be merged is three problems. An engine is described by statistics it publishes or by a sample obtained through its own search interface, and the samples together form a small index on which documents from different engines can be compared. Engines are selected by CORI, which scores each as if it were one large document, or by ReDDE, which estimates how many of the best documents each would contribute. The estimate behind ReDDE is unbiased for a uniform sample and has hypergeometric variance, large when relevant documents are few. Merging is exact when engines share statistics. When they do not, each engine's idf is wrong by the logarithm of the term's concentration in it, lowest where the query's subject lives, and the remedies are weights from selection, normalization by the engine's largest possible score, and a regression onto sample scores. On Cranfield cut into ten topical engines, three engines chosen by CORI on complete descriptions kept nDCG@10 at 0.364 against 0.368 when scores were shared, and the best merges without shared statistics reached 0.316. Searching all ten engines made those merges worse.

That closes the unit. Its six articles took one engine's query from the postings it need not score, through the index that stays current and the answers that are remembered, to the case of many engines. The unit's page, Efficient Query Processing, lists them in order. The collection continues with Learning to Rank Methods.

References

  • Callan, J. (2000). Distributed information retrieval. In W. B. Croft (Ed.), Advances in Information Retrieval, chapter 5, 127–150. Kluwer Academic Publishers. record
  • Callan, J. P., Lu, Z., and Croft, W. B. (1995). Searching distributed collections with inference networks. In Proceedings of SIGIR 1995, 21–28. record
  • Kulkarni, A., and Callan, J. (2015). Selective search: Efficient and effective search of large textual collections. ACM Transactions on Information Systems, 33(4), 1–33. record
  • Shokouhi, M., and Si, L. (2011). Federated search. Foundations and Trends in Information Retrieval, 5(1), 1–102. record
  • Si, L., and Callan, J. (2003a). Relevant document distribution estimation method for resource selection. In Proceedings of SIGIR 2003, 298–305. record
  • Si, L., and Callan, J. (2003b). A semisupervised learning method to merge search engine results. ACM Transactions on Information Systems, 21(4), 457–491. record