The bargain at the back

Open a nonfiction book near its final pages. The index does not say:

page 12  fox, field, tracks
page 41  index, pages, words
page 73  evidence, search

That would merely repeat the book's forward direction: page first, words second. The actual index reverses the question:

evidence  73
field     12, 19
fox       12, 19
index     41, 88

Now a reader who starts with fox can jump directly to two pages. The book was not scanned more quickly. A different relation was prepared in advance.

Here is the corpus that will travel through the book. It is deliberately small enough to fit on one sheet of paper.

For the moment, lowercase body words separated by spaces are the terms. Titles will matter later, but not yet. Under that intentionally crude rule, the corpus contains 54 term occurrences.

Before reading on, predict the index entry for field.

The transpose

Write the collection as a binary relation

$$R \subseteq D \times T,$$

where $(d,t) \in R$ means that document $d$ contains term $t$. A forward view fixes a document and asks for its terms:

$$R(d) = \{t \in T : (d,t) \in R\}.$$

An inverted view fixes a term and asks for its documents:

$$R^{-1}(t) = \{d \in D : (d,t) \in R\}.$$

Nothing has been approximated. The same pairs are grouped by their other coordinate. In a matrix picture, documents are rows, terms are columns, and indexing transposes the useful access direction.

The physical index has two parts:

• the dictionary stores each distinct term and finds its list;
• a postings list stores the increasing document IDs for one term.

For part of the corpus, the result is:

The dictionary answers “does this term exist, and where is its list?” The list answers “which documents contain it?” Keeping those responsibilities separate will matter when the dictionary becomes an automaton and the postings become compressed integer sequences.

Build it once

The smallest construction algorithm emits one pair for every term occurrence, sorts the pairs, and groups equal terms. Let $T$ be the number of term occurrences in the collection.

BUILD-INVERTED-INDEX(D)
Input:  documents D[1:n], each represented by its analyzed terms
Output: dictionary mapping each term to its sorted postings list

pairs ← empty sequence
for each document d in D
    seen ← empty set
    for each analyzed term t in d
        if t is not in seen
            append (t, d.id) to pairs
            add t to seen
sort pairs by (term, document ID)
index ← empty dictionary
for each maximal run r in pairs with the same term
    index[r.term] ← document IDs from r
return index

The per-document seen set prevents repeated words from duplicating a document ID in this basic Boolean index. A later ranking chapter will retain frequency instead of discarding it.

The algorithm's dominant generic step is sorting at most $T$ pairs, for $O(T \log T)$ comparisons and $O(T)$ stored pairs. The final grouping pass is linear. This is a teaching construction, not the last word: large indexers use blocked sorting or single-pass in-memory indexing so the collection need not fit in memory. The relation and the correctness argument remain the same.

Why is each output list correct? Keep this invariant while scanning a sorted run for term $t$:

It is true before the first pair because both sets are empty. The next pair has the same term, its document ID is not duplicated because construction emitted at most one $(t,d)$ pair per document, and sorting makes it no smaller than the previous ID. Appending it preserves exact membership, uniqueness, and order. When the run ends, construction has emitted a pair for every document that contains $t$, so the list is exactly $R^{-1}(t)$.

This proof is modest, but it buys three later algorithms. Intersection can rely on increasing IDs. Gap encoding can rely on nonnegative differences. A query can rely on absence from the list meaning absence from the document under the same analysis rule.

Count before timing

Suppose a query asks for one exact term. A scan inspects all 54 term occurrences, even when only two documents can match. The inverted lookup reads the dictionary entry and then only that term's postings.

These are exact operation counts for this corpus, not wall-clock claims. A hash lookup, binary search, compressed decode, cache miss, and sequential text scan do not cost the same number of nanoseconds. The count establishes the source of the advantage: query work depends on the selected lists rather than the whole collection. Later chapters will time complete paths and report distributions.

For a single-term query $t$, write $N$ for all indexed term occurrences and $df(t)$ for the number of documents containing $t$. The simplified contrast is

Let $L(t)$ be the cost of locating $t$ in the dictionary. Then

$$S(t) = \Theta(N)$$

for the scan, while

$$I(t) = L(t) + \Theta(df(t))$$

for the indexed path.

If nearly every document contains $t$, the postings list is long and the gap narrows. If $t$ is rare, the index rejects most of the collection without touching it. This is why the distribution of language—not merely collection size—governs search cost.

Four attractive wrong turns

Where the simple index stops

Our handmade index has already smuggled in several decisions:

• Index in a title and index in a body are, under the rule stated above, different inputs because titles were ignored.
• search and searches are different terms.
• punctuation, accents, compounds, and languages other than English have no rule yet.
• repeated terms lose their frequency.
• word order disappears, so phrases cannot be verified.
• a document ID says nothing about whether the current reader may open it.

None is a cosmetic detail. Index construction and query processing must agree on what a term is, or a query can ask for a key the index could never have written. Authorization has an even harder boundary: inaccessible documents must be removed before ranking, snippets, counts, or timing can reveal them. Those concerns get their own chapters because hiding them inside “tokenize the text” makes a small demo look correct while the real system is not.

Lessons

• A forward collection maps each document to its terms; an inverted index groups the same relation by term and maps each term to its documents.
• The dictionary locates a term's postings list. The postings list records the increasing document IDs that contain the term.
• Pair-sort construction emits document–term pairs, sorts them, and groups equal terms. Its simple form costs $O(T \log T)$ comparisons for $T$ term occurrences.
• The grouping invariant proves exact membership, uniqueness, and increasing order—properties later query and compression algorithms rely on.
• Exact work counts explain the win before timing does: a query reaches selected postings rather than re-reading the whole collection.
• Scanning, a vocabulary alone, one global document order, and embeddings all answer nearby questions. None substitutes for naming and materializing the term-to-document relation.

Practice

The first machine was actually two

We pretended that spaces reveal terms and lowercase letters make them equal. Real text refuses both assumptions. The constructor might store search while the query produces searches; one side might preserve an accent while the other folds it; a language may not use spaces between words at all.

The next chapter splits the search engine into two machines—one that analyzes documents and one that analyzes queries—and gives them a law: equivalent input must become the same term on both sides. The index is only as truthful as that agreement.

References

1. Boswell. “The Life of Samuel Johnson, LL.D..” 1791. — primary public-domain source for the epigraph and its library context
2. Manning, Raghavan, Schütze. “Introduction to Information Retrieval.” Cambridge University Press, 2008. — chapters 1, 2, and 4 develop inverted indexes, postings, analysis, and scalable construction
3. Zobel and Moffat. “Inverted Files for Text Search Engines.” ACM Computing Surveys, 2006. — comprehensive account of core inverted-file representation, construction, query processing, and extensions