IR Lecture 9 on Federated Search | Guest Lecture by Djoerd Hiemstra

How do search engines decide what's relevant? It depends on your application and the data you have available:

  • Ad hoc: language models, BM25
  • Spam filters: Naive Bayes (using examples)
  • Network data: PageRank
  • Clicks: Learning to rank
  • Conversational search: BERT

Big data fallacy

"If we have more data, we can learn the ultimate ranking function"

This is a fallacy because there is no "one-size fits all" in IR. You have to decide what you focus on:

  • Web: Web graph, anchor text
  • Videos: Views, likes, content-based features
  • Advertisements: Bids, click-through-rate
  • Tweets: Retweets, likes
  • Restaurants: Geo location, reviews
  • Products: Price, stock numbers.

What's our search specialization?

Examples of types of data sets:

  • LifeCLEF - images of plants, birds
  • ProtestNews - news
  • eHealth - medical content
  • eRISK - social media
  • CheckThat! - political debates
  • PersonalisedIR - web data
  • ImageCLEF - lifelog data

CLEF is a European alternative to TREC.

New strategy: delegate

  1. What is the query about?
  2. Send query to the right CLEF systems
    • If it's medical, send to the best performing system on medical data
  3. Re-order results, get hopefully near perfect output.

"Universal search"?

Also things like Google apply a similar strategy and use different engines for different things:

  • General search
  • News
  • Knowledge graph
  • Images
  • Books
  • Videos
  • etc. (Scholar, Shopping, Flights, Maps)

But in this case all search engines are still controlled e.g. by Google.

Federated Search

"A federation is a group of computing or network providers agreeing upon standards of operation in a collective fashion" (Wikipedia)

So relies heavily on standards.

Standards

ANSI/NISO Z39.50 is a relevant standard for information retrieval. REVIEW 11.

Open problems:

  • Different schemas and different query langauges
  • Resources rank document using secret algorithms
  • Resources do not export metadata & statistics
  • Pre-WWW standards.

Q: Why are standards so important for federated search?

Q: What are some open problems for Federated Search, relating to standards?

Q: What's the difference between Federated Search and Universal Search?

Z39 standards:

  • Z39.84: DOI
  • Z39.85: Dublin Core
  • Z39.88 OpenURL

STARTS protocol

1997:

  • Web based
  • Shares document statistics like idf

Old approach: GLOSS* ranking

Glossary of Servers Server: routes queries to appropriate information sources based on previously collected frequency statistics about the sources.

Approach: Estimate the result size of a query in each resource, to estimate which of the databases to use for retrieval.

Each resource provides database size and df for every term $t_i$.

$$score(db, t_1, ..., t_n)=size(db)*\prod_{i=1}{n}\frac{df(t_i,db)}{size(db)}$$

Looks quite a bit like language models if we replace document frequency

The problem with GLOSS: Brin & Page 1998: critique the GLOSS model, because there is a lot of administration costs. Each server needs to continually update and send its size and its dictionary. As we know, Brin & Page argued instead for a centralized search engine.

Q: Explain GLOSS

Q: Does GLOSS assume a cooperative or uncooperative environment?

Q: What role does database size play in GLOSS?

Document frequency of a given term is of course higher for a larger database. To compensate for this effect GLOSS scales the df statistic down proportional to the database size. We are interested in statistics to estimate the relevance of results; not find the database with the most results.

Cooperative vs. Uncooperative environments

In GLOSS* people can also cheat when informing about database sizes etc. I.e. servers need to be cooperative.

  • Cooperative: Collections inform brokers about their contents by providing information such as their term statistics.
  • Uncooperative: No statistics need to be passed on, servers just need to take in queries.
    • Just means it doesn't rely on cooperation,

Q: In which way is it possible for individual search engines to cheat GLOSS in order to route more traffic to themselves?

Q: What's the difference between cooperative and uncooperative environments for federated search?

Uncooperative tactic: Query-based sampling

resource descriptions are created by running queries and examining the documents that are returned Callan & Connell 2001:

A broker sends a set of queries to the servers in the federation to learn what the responses are like.

Now when the broker gets a query later, there's two option:

  • Return query samples if they are still in memory
  • Forward the query to one of the servers (e.g. Wikipedia) and then pass the result back to who queried.

Do samples resemble the full index?

We no longer explicitly build a full index over all documents, because of the federated setup. But experimental results show that when you take enough samples, the results approximate the full index.

Q: Do query-based samples resemble a full index?

TREC Federated Web Search task

TREC FedWeb: https://fedwebgh.intec.ugent.be/

Large-scale federated search evaluation that used the uncooperative framework:

  • Resource selection: based on incomplete evidence from a query, what's the best resource to use for answering the query?
  • Result merging: when there's multiple relevant resources, how do we merge them into a answer?
  • Vertical selection: group results together in meaningful categories so that they can be efficiently displayed

Contains more than 100 topics (queries), show resulting pages for 150 resources, do relevance judgments, detect duplicates, results and pages for sample queries.

Key insights:

  • There were some impressive results that only used snippets for determining the most relevant resource (so didn't download any document at all!)
  • Using of external resources is very useful

DB Size estimation with query-based sampling (uncooperative)

In an uncooperative environment we also don't know the size of the database the broker is querying. Can we also estimate the database size using query-based sampling?

1. Capture-Recapture / QueryPools

  1. Baseline 1: Broder et al.* : "Capture-Recapture" (a.k.a. QueryPools)

(Similar to population estimation in biology)

We start with a large set of queries that we divide into sets A and B.

$D_A$: documents founds by queries in A ("captured birds")

$D_B$: documents founds by queries in B ("re-captured birds")

We assume some "birds" in B will be re-captures from A. The more re-captures, the smaller the overall "population" likely is. That's why we divide by the intersection of A and B in our estimate. Size is the length of both multiplied divided by the length of their intersection.

$$Size = \frac{ |D_B| * |D_B|}{|D_A \cap D_B|}$$

So what if you send thousands of queries and never find a duplicate? We don't want to end up with division by zero.

So this doesn't work well with large search engines.

Q: Why does the "capture-recapture" database size estimation strategy of Broder et al. not work well for large search engines?

2. Sample-resample

  1. Baseline 2: Si & Callan: "Sample-resample"

We again have $D_A$ acquired with query-based sampling. (In the slides P(A) is used where A should be a set of documents; but they just used if for a set of queries and $D_A$ for the documents, so I'll stick to that). Or does A mean set of queries after all?

$$P(D_A) df_{sample}(q_i) / size_{sample}\ (sample)$$

Where $df_{sample}(q_i)$ is the document frequency of query term $q_i$ in our sample. This expresses the change that this query term occurs in a random document in the sample $D_A$.

We then assume the resource provides the real document frequency for that query term $q_i$. We can then write a similar expression but now defined not on the sample but on the whole database. We get :

$$P(D_B) df(q_i) / size\ (resample)$$

We have a missing parameter here, namely the database size. We can however solve for size by assuming that the occurrence of that query term q_i is the same in the sample and in the overall database. Solving for size:

$$size = \frac{ df(q_i)}{df_{sample}(q_i)} \times size_{sample}$$

Repeat this for many query terms and average the results.

N.B. the "resample" step also returns the number of results. So this arguably slightly breaks with the uncooperativeness assumption. Assuming we indeed have the number of actual results in the database, we require less samples than the capture-recapture method.

Q: Explain the sample-resample alternative to capture-recapture; to what extent does it work in an uncooperative environment?

Q: What's a clever trick to adjust sample-resample so that we do know the true document frequency for a query term without asking the resource?

A: If you focus on query terms that are very rare and that return very little documents, e.g. less than 10 and you only use those results, then you do know the true df. E.g. if a query only returns 8 documents, you know $df(q_i)=8$.

3. Sample-resample-resample Compare to reference corpus

Idea: instead use a reference corpus where we know the amount of documents.

Repeat the second step of procedure 2. We have: $$P(D_B) df(q_i) / size\ (resample)$$

And we wanted to estimate size. We can repeat the sample trick, but now compare to a corpus where we know the size.

$$P(D_C) df(q_i) / size_{Clueweb}\ (re-resample)$$

Now we can estimate size the same way as before, assuming $P(D_B)=P(D_C)$.

Comparison

QueryPools severely underestimates the size. Baseline 3 (resample-re-resample) provides the best results, but still underestimates.

Resource selection ReDDE (size-based static ranking)

Broker's can employ different strategies to select resources. Well known (again from Callen) strategy is ReDDE.

We want to score different collections given a query.

$$R(C,q) = \sum_{d \in C} P(R=1|d)P(d|C)|C|$$

Where for $P(R=1|d)$ we can use for example BM25. Notice that here we use the size of the collection again! Hiemstra emphasized how important it was.

$P(d|C)$ is based on the number of samples from C:

$$R(c,q) \approx \sum_{d \in S_C} P(R=1|d) \frac{ |C| }{ |S_C| }$$

One interesting detail is that ReDDE uses a constant term for $P(R=1|d)$.

$$P(R=1|d) = \alpha if r_{CCI}(d) < \beta \sum_i |c_i|$$

Q: What's the importance of collection size C in ReDDE?

Hiemstra shows they are better but doesn't really explain why; and I don't see it directly. Before it was clear because there was a fraction; but here it's multiplicative.

Slide 37 reports that ReDDE has a 0.595 correlation with the size of the collection!

Language Models for resource allocation

We can use the Query Likelihood model to estimate $P(q|C)$.

For resource allocation, we are interested in finding the best collection for a given query i.e. P(C|q), which is the posterior proportional to $P(q|C)P(C)$.

We can use the collection size to define the prior P(C)

$$P(C) = \frac{ |C| }{ \sum_{c'}|c'|}$$

The role of collection size is way more clear here than in ReDDE (for me at least).

Discussion

  • Insight slide 42: we can potentially do better by leaving out the big search engines like Google. (For k=5 higher precision for non-WSE)
  • 43: But general web engine needed for top relevant results (how does that compare to previous point?)