Search is not a WHERE clause: relevance, TF-IDF and the inverted index

A query that answers "how well"

Number the eight titles in the slide's order (p. 557); T1 is the book the customer likes.

Ask a relational database for the books about data and you write a predicate:

-- T1, T3 and T4: a set, in no order
SELECT title FROM books WHERE LOWER(title) LIKE '%data%';

Each row satisfies the WHERE clause or not, so T1, T3 and T4 come back as a set: none is "more about data" than the others, and a title that says the same in other words is left out. Right for an invoice; wrong for "books like this one".

The lecture starts from this gap. After recalling the four NoSQL families of the course — document, graph, key-value, wide-column (p. 551) — its roadmap slide (p. 552) lists the "New ingredients" that search adds to database access: intent, similarity, relevance, ranking and, in brackets, efficiency.

Intent: what the user really wants

A query is a few words; behind it there is a need. The slide defines intent as "the underlying goal, purpose, need, or desire a user has when interacting with a system (e.g., entering a search query or a message to a chatbot)" and names four kinds (p. 553):

Matching, similarity, relevance, ranking

Matching is "the technical process of linking the user's input (query, utterance) to predefined intents or data within the DB" (p. 554), and the slide's title, "Matching (→ Similarity?)", hints at how: by computing how similar the input is to each item. Similarity is a number the system computes.

Relevance is not. The same slide calls it "the qualitative measure of how well the search results align with the user's actual needs and expectations, ultimately satisfying their intent", and gives a test: "A result is relevant if the user finds what they were looking for quickly and easily". Ranking sorts the results by similarity, best first; efficiency keeps it all fast (section 5).

Similarity is computed by the system; relevance is judged by the user. A ranking is the system's bet that the first predicts the second.

What is compared: attributes or text

To compute a similarity you need the content of an item (p. 555): explicit attributes — for a film, "Action / adventure", "Feature Bruce Willis", "Year 1995" — which compare like columns, or textual content, "title, description, table of content, etc.", for which "Several techniques exist to compute the distance between two textual documents". The rest of the lecture builds one of them.

The slide files the book example under information filtering (p. 557) — keeping and ordering the items that match one user's interest — and calls it "An (unrealistic) example", matching "based only on their title": small enough to compute by hand.

Turning a title into numbers

How does a program compare two texts? Page 556 answers in two lines: "A textual document is scanned and parsed" and "Word occurrences are counted (may be stemmed)".

Figure 2 runs T2 through it.

Do it for all eight titles and you get the "Word count" table of p. 558: one row per term, one column per title, 29 terms in all. Six of its rows, plus a column you will need soon — the number of titles containing the term, its document frequency df:

Notice what the table did without a word of explanation. It lower-cased everything, so "Data" and "data" are one term. It dropped the punctuation. It stemmed three plurals — applications, relationships and technologies became application, relationship and technology — which is why relationship counts 2 in T2. And it kept every short word: a, and, for, of, the, to and your all have rows of their own.

Then comes the "Problem: importance of words" (p. 556). In raw counts "the" weighs as much as "mining", a word three titles share as much as a word only one title has, and a long title overlaps with anything by sheer bulk. Three questions, three fixes: how loud is the term in this document (TF), how rare in the collection (IDF), how long is the document (normalisation).

Loud here, rare elsewhere: TF × IDF

Page 559 gives the plan: "Each document is transformed into a normed TFIDF vector, size N" — one coordinate per term of the vocabulary, N = 29 here, most of them 0. Each non-zero coordinate is the product of two factors.

TF: how loud the term is in this document

Term frequency is local, one document at a time. Page 560 defines it as a fraction:

The "Actual formula" of p. 562 uses a different one:

Both are standard. The fraction makes an occurrence count less in a longer document; the logarithm damps repetition — a term seen twice is not twice as telling: \(\log 3 = 1.099\) against \(\log 2 = 0.693\). Natural logarithms throughout; another base multiplies every weight by one constant, which the normalisation below removes.

IDF: how rare the term is in the collection

Inverse document frequency is global. Page 561 calls it a measure of "how common a term is across the collection of documents, the lower the less important that term is": the more documents contain the term, the lower its IDF.

The "Actual formula" of p. 562 differs again, slightly:

The +1 matters at the edge: a term in all eight titles gets \(\log(8/8) = 0\) from p. 561 but \(\log(9/8) = 0.118\) from p. 562 — still the weakest, never exactly zero, so no document becomes a vector of zeros that cannot be normalised. Here df is 1, 2 or 3, so IDF takes three values:

Rarity is measured in this collection, not in English: "a" and "the" occur in one title each, so they get the top IDF, 2.197, like "website". The weight of a term is the product of the two factors — loud here times rare elsewhere (p. 561):

Page 560 says what the product is for: it "Measures the relevance of a term inside a document" and "Penalizes the words that appear too often across different documents". Relevance in a loose sense here: the weight of a term, not the user's judgement of p. 554.

Normalisation: every document gets length 1

The last fix is length. The formula of p. 559, boxed in red on p. 562, divides every weight of a document by the length of its whole vector:

This normalisation makes every document a vector of length 1. Long titles lose their bulk advantage, and the same raw weight ends up lighter in a long title, which shares the unit length among more terms — why p. 563 circles two different numbers for one word (Figure 3).

Now compute T4's column by hand, then T1's, the query book's.

1. Count. T4, "Data Mining Your Website", has four terms, each once, so all get the same TF:

   \[ TF = \log(1 + 1) = 0.693 \]

2. Look up df: data and mining are in T1, T3 and T4, your and website only in T4. With #docs = 8:

   \[ IDF_{\text{data}} = \log \tfrac{9}{3} = \log 3 = 1.099 \] \[ IDF_{\text{website}} = \log \tfrac{9}{1} = \log 9 = 2.197 \]

3. Multiply, for data and mining, then for your and website — with unrounded logarithms (0.693 × 1.099 would give 0.7616):

   \[ \log 2 \times \log 3 = 0.7615 \] \[ \log 2 \times \log 9 = 1.523 \]

4. The length of T4's vector is the square root of the sum of the squared weights:

   \[ \sqrt{2 \times 0.7615^2 + 2 \times 1.523^2} \] \[ = \sqrt{5.799} = 2.408 \]

5. Divide every weight by the length — the cells printed on p. 563:

   \[ \text{data:}\quad 0.7615 / 2.408 = 0.316 \] \[ \text{website:}\quad 1.523 / 2.408 = 0.632 \]

6. Same recipe for T1: the unique terms building, application and for weigh 1.523 each, data and mining 0.7615, and crm, in two titles, gets \(\log 2 \times \log 4.5 = 1.043\). The length:

   \[ \sqrt{3 \times 1.523^2 + 2 \times 0.7615^2 + 1.043^2} \] \[ = \sqrt{9.206} = 3.034 \]

7. Divide: data and mining 0.251, crm 0.344, the unique words 0.502 — again the printed cells.

   \[ 0.7615 / 3.034 = 0.251 \] \[ 1.043 / 3.034 = 0.344 \]

From vectors to a ranking

The third line of p. 559 says "The distance between any pair of vectors is computed". Which distance? For unit vectors the Euclidean distance and the cosine similarity give the same ranking — four short steps show why.

1. Write the squared distance between the query \(\vb{q}\) and a document \(\vb{d}\) as a dot product:

   \[ \lVert \vb{q} - \vb{d} \rVert^2 = (\vb{q} - \vb{d}) \cdot (\vb{q} - \vb{d}) \]

2. Expand it as you would \((a - b)^2\):

   \[ = \vb{q} \cdot \vb{q} - 2\, \vb{q} \cdot \vb{d} + \vb{d} \cdot \vb{d} \]

3. Both vectors are normed, so \(\vb{q} \cdot \vb{q} = \vb{d} \cdot \vb{d} = 1\); and for unit vectors the dot product is the cosine of the angle between them:

   \[ \lVert \vb{q} - \vb{d} \rVert^2 = 2 - 2 \cos\theta \]

4. The distance falls exactly when the cosine rises. Ranking by the smallest distance or by the largest cosine gives the same order, and the one number to compute is \(\vb{q} \cdot \vb{d}\).

So the score is the dot product, and for sparse vectors it is short: only terms both documents contain survive, every other product has a 0 in it. T1 and T4 share data and mining, each contributing \(0.251 \times 0.316\):

Repeat it for the other six titles and you get the ranking of p. 564:

The computed scores reproduce the printed order exactly. Now take the computation apart yourself.

Back to the puzzle

Both questions of the opening now have answers. The same two words count for more in T4 because normalisation spreads each title's unit length over its terms, four in T4 and eleven in T3: 0.316 against 0.187 per word, 0.159 against 0.094 in total.

And CRM stays invisible because the system compares tokens, not meanings: "crm" and "customer relationship management" are different strings. T3's three spelled-out words earn it nothing, and T8's score is a sum over an empty set, exactly 0. Type the expansion into the lab and the picture turns over — T8 rises to #1 with 0.503, and the book that says "CRM" drops to 0 (Figure 5).

Seeing that two strings mean the same thing needs a representation of meaning: embeddings, which place related texts close together whatever their spelling (lesson 27). If you have met word embeddings in deep learning, this is where they come back — compared with the same cosine.

A lexical score is a sum over the shared terms: no shared token, no score — whatever the meaning.

What a real engine computes

Page 560 opens by saying where TF-IDF is used: in the scoring function of Lucene, the search library inside Elasticsearch. The idea is right; the name is out of date.

In Elasticsearch you never compute these weights yourself: a match query (lesson 26) returns the titles that share a term with the query, sorted by BM25 score — T8 would not even be listed.

Under the hood: an index turned inside out

So far you looked at every title. "On the internet, time affects attention", p. 565 warns: "attention is money", and "search engines need to respond in tenths of a second". Reading every document at query time is out of the question; the answer must be prepared before the query arrives.

The preparation is the inverted index, "the building blocks of search engines", "made of mappings: TermIDs => DocumentIDs" (p. 566). It is the index at the back of a textbook: you do not read four hundred pages to find "mitochondria", you look the word up and get a list of pages.

Page 568 builds one from "The quick brown fox jumped over the lazy dog" and "Quick brown foxes leap over lazy dogs in summer". The index "Lists every unique word from every document and identifies which documents a word appears in": "quick" -> D1,D2, "fox" -> D1, "summer" -> D2… Two entries reveal what the slide does not say. "quick" -> D1,D2, though D2 writes Quick: the index lower-cased. "fox" -> D1 only, though D2 has foxes: no stemming, so foxes is another term. An index finds exactly the token it stored, so the query must be cut the same way — what Elasticsearch calls analysis (lesson 25).

A query is a join of posting lists

"Computing retrieval function involves: finding all documents containing set of terms, i.e. computing a join over the posting lists" (p. 567). For "quick fox" the engine intersects two short lists, D1, D2 and D1: the answer is D1 — in SQL terms, a join on the document id. With both lists sorted by document id, one pass over each suffices, and no document is opened (background, not on the slide). OR takes the union; only its documents get scored.

Small enough to stay in memory

The lists must be small and quick to read. Page 566: they are "compressed with integer compression algorithms that allow for fast decompression, take statistics of text into account, are in blocks to allow for easy reading" — and "why compressed? to reduce the amount of space in memory". An index that fits in RAM is read at memory speed, and decompressing a block costs less than fetching it from disk.

One common trick (background, not on the slide) shows what "statistics of text" can mean: store a sorted id list as the gaps between ids. A frequent term's ids lie close together, so the gaps are small numbers needing few bits (Figure 6, left).

Stopping early

Page 567 adds a second speed-up: "Entries in the posting list are sorted from most important documents (with highest term counts) to least", which "allows for early termination". The engine computes "bounds on scores" — the best score an unread document could still reach — and when that bound cannot beat the results found, it skips the rest: "lower ranked documents dropped as early as possible". The last bullet adds index pruning techniques, which "get rid of documents that would never be retrieved for a certain query": their entries are never read at all. The top 10 of a billion cost a small fraction of the billion.

The inverted index answers from term lists, never from the documents: the lists are joined, compressed to stay in memory, and ordered so that the engine can stop early.