ConceptDBISAI-written · proofread

Inverted Index

An inverted index maps each word to its inverted list, the sorted list of IDs of the documents containing it, optionally with a score per posting such as tf or BM25.

Definition#

An inverted index is a data structure that maps each distinct term $t$ to a sorted list of documents containing $t$ , called an inverted list (or postings list). Each entry in the list pairs the document identifier with a score (commonly tf or tf.idf).

\text{Inverted Index} = \{ t \mapsto [(D_{i_1}, s_1),\ (D_{i_2}, s_2),\ \ldots] \mid t \in \text{vocabulary} \}

where scores $s_j$ are sorted in descending order (or documents by ID).

Construction#

For each document $D$ in the corpus:

Tokenize $D$ into terms.
For each term $t$ $t$
1. compute its score $s$ (e.g., $\text{tf}(t, D)$ ).
2. Append $(D, s)$ to the inverted list of $t$ .

Query Processing#

Semantics	Operation	Algorithm
AND (all terms required)	Intersection of inverted lists	List Intersection and Search
OR (any term sufficient)	Union of inverted lists	Merge

For multi-keyword queries, retrieve the inverted list for each query term, then intersect or merge the lists and aggregate scores.

Example#

Documents:

$D_1$ : “b c a c d c”
$D_2$ : “b c a c d c b c”

Inverted index with tf scores:

Term	Postings
a	$(D_1, 1),\ (D_2, 1)$
b	$(D_1, 1),\ (D_2, 2)$
c	$(D_1, 3),\ (D_2, 4)$
d	$(D_1, 1),\ (D_2, 1)$

Properties#

Space: $O(\sum_{t} \text{df}(t))$ where $\text{df}(t)$ is the number of documents containing $t$ .
In practice, most entries are zero (sparse), so the inverted index is far more compact than a full term-document matrix.
Inverted lists are typically stored sorted by document ID to enable efficient intersection.

TodoSuggested by Claude

The body does not follow spec §5.3 yet: a > [!definition] callout instead of ## Definition, and a ## Sources section, e.g. Slides 01, p. 16, Slides 01, p. 21, Slides 02, p. 8, DBIS_VL01 > Inverted Index, DBIS_VL01 > Construction of an Inverted Index, DBIS_VL02 > Ranking: Basic Idea, DBIS_VL11 > Sparse matrices.
Definition: “scores $s_j$ are sorted in descending order (or documents by ID)” — in the lecture the lists are always sorted by document ID (construction visits IDs in increasing order); the zipper intersection/merge needs this. Sorting by score only happens after merging (top- $k$ ).
Query Processing links the topic List Intersection and Search; the concept is List Intersection.
Missing facts from the lectures: an entry of an inverted list is a posting (doc ID, score, optionally positions); $\mathrm{df}_w$ is the length of the inverted list of $w$ (used for idf); the construction is linear only if an ID is appended at most once per list by comparing with the last element (VL01 warning); the sparse row-major term-document matrix is exactly an inverted index with scores (DBIS_VL11 > Sparse matrices).
The example table has an empty last row.

Connections

Mentioned in inline links16

Gap Encoding
Particularly effective for the sorted inverted lists (List Intersection needs them sorted): the more frequent a word, the denser its list and the smaller the gaps, so few bits per posting. §
Join $T_1 \bowtie T_2$
This is the same algorithm as the intersection of sorted lists used for inverted index queries in Lecture 1 (Slides 05, p. 13). The one difference: whenever a value of $X$ matches a value of $Y$ , output the pairs with all rows of $Y$ that… §
List Intersection
Given two sorted lists $L_1, L_2$ (e.g. the inverted lists of two query words in an Inverted Index), list intersection computes the sorted list $L_1 \cap L_2$ of the elements contained in both. For keyword search it implements AND-semantic… §
Q-Gram Index
A q-gram index is an Inverted Index with different objects: a document index maps each word to document ids, a q-gram index maps each q-gram to word ids. The construction code from Lecture 1 carries over almost unchanged. §
Sparse Matrix
In row-major order, the entries of row $i$ (term $i$ ) are consecutive and their column indices are the ids of the documents that contain term $i$ , with the score as payload. This is exactly an Inverted Index with scores (row $i$ = the post… §
TF-IDF
$\mathrm{df}_w$ : number of documents containing $w$ . In an Inverted Index this is simply the length of the inverted list of $w$ . §
Term Frequency
For a word (term) $w$ and a document $D$ , the term frequency $\mathrm{tf}(w, D)$ (short $\mathrm{tf}$ ) is the number of times $w$ occurs in $D$ . In an Inverted Index with tf scores, the inverted list of $w$ holds the pairs… §
Zipf's Law
Consequences for the Inverted Index: a few words (the, of) have very long inverted lists, most words very short ones. Hence ordering the lists by length before intersecting pays off, and frequent words need a low weight in ranking, which t… §
VL01 – Introduction, Inverted Index, Zipf's Law
The lecture outlines the course (indexing, ranking, databases, knowledge graphs, error-tolerant search, web apps, embeddings, vector databases and RAG) and its organisation. Its technical part solves keyword search: instead of scanning all… §
Inverted Index — central data structure: word → sorted list of record IDs, built in one linear pass §
VL02 – Ranking and Evaluation
In the inverted lists, store with each doc ID a score that captures how much the document is “about” that word. §
Inverted Index — extended with scored postings; merging aggregates scores §
VL08 – Fuzzy Search, Prefix Edit Distance, Q-Gram Index
A q-gram index is an Inverted Index with different objects than a document index: §
Inverted Index — the q-gram index is an inverted index over q-grams instead of words §
VL11 – Vector Space Model, Word Embeddings
This is exactly an Inverted Index with scores. Column-major order gives, per document, its term vector. §
Inverted Index — equivalent to the sparse row-major term-document matrix §
Encodings and Compression
Where the numbers come from. The sorted document IDs of an inverted list are large, but their differences are small, especially in the long lists of frequent words (Zipf’s law: a few words account for most occurrences). Gap Encoding turns… §
Inverted Index and Ranking
Keyword search is answered by an Inverted Index: each word maps to the sorted list of documents containing it, and multi-keyword queries intersect (AND) or merge (OR) these lists. To rank the hits, each posting carries a score for how much… §
Inverted Index — word → sorted list of postings (doc ID, score); the data structure §
List Intersection and Search
Keyword queries on an Inverted Index reduce to operations on sorted lists of IDs: AND-queries intersect them, OR-queries merge them. The central question is how to do this as fast as possible. The zipper algorithm needs linear time… §
Word Embeddings and Language Models
| dot product | BM25 | handled by BM25’s length normalization | exactly the BM25 ranking of the Inverted Index (Lecture 2) | ES11, Ex. 1 | §
$A$ is mostly zeros, so it is kept as a sparse matrix of (value, row, column) triples. Row-major order groups the entries per term, which is literally an Inverted Index with scores; column-major order groups them per document. So “VSM with… §

Search in these mentions →