TopicDBISAI-written · not yet proofread

Inverted Index and Ranking

Keyword search with an inverted index whose postings carry scores (tf, tf.idf, BM25) that are summed while merging the lists, plus Zipf's law for word frequencies.

Concepts#

Inverted Indexword → sorted list of postings (doc ID, score); the data structure start here
Zipf's Lawword frequencies follow $F_n = C \cdot n^{-\alpha}$ ; few very long lists, many short ones
Term Frequencynumber of occurrences of a word in a document; the naive posting score
TF-IDFtf weighted by $\log_2(N/\mathrm{df})$ so that common words count little
BM25tf.idf with saturating, length-normalized tf; the standard score

How it fits together#

Pipeline. Tokenize, build the inverted lists in one linear pass (IDs arrive increasing, so lists are sorted), then compute a score per posting. A query merges the lists of its words (intersection for AND, merge with score summation for OR, see List Intersection), sorts by summed score and returns the top $k$ (partial sort, $\Theta(n + k \log k)$ ).

Scores, step by step. Each step fixes a defect of the previous one:

Score	Posting score	Defect fixed	Remaining defect
tf	$\mathrm{tf}$	none	frequent words (of) dominate
tf.idf	$\mathrm{tf} \cdot \log_2(N/\mathrm{df})$	common words weigh little	tf grows linearly and with document length
BM25	$\mathrm{tf}^* \cdot \log_2(N/\mathrm{df})$	tf saturates at $k+1$ , normalized by $\mathrm{DL}/\mathrm{AVDL}$	parameters $k, b$ must be tuned (on a training set)

BM25 contains the others as special cases: $k = 0$ gives binary scores times idf, $k \to \infty$ with $b = 0$ gives tf.idf. The idf factor is the same throughout, and $\mathrm{df}_w$ is just the length of the inverted list of $w$ .

Zipf’s law connects the pieces: it predicts the skewed list lengths (order lists by length before intersecting) and motivates idf (the most frequent words carry the least information).

Vector space view. The scored inverted index is the row-major sparse term-document matrix $A$ ; the score sum for a 0/1 query vector $q$ is $q^T A$ (DBIS_VL11 > Retrieval as a matrix-vector product). With BM25 entries this gives exactly the inverted-index ranking.

Pitfall. Requiring all query words to match (pure AND) misses relevant documents; boost them instead of filtering (DBIS_VL02 > Further refinements and other methods).

Key Formulas#

$\mathrm{idf}_w = \log_2 \frac{N}{\mathrm{df}_w}$ , $\ \text{tf.idf} = \mathrm{tf} \cdot \mathrm{idf}_w$ — TF-IDF
$\mathrm{tf}^* = \frac{\mathrm{tf}\,(k+1)}{k\,\alpha + \mathrm{tf}}$ , $\ \alpha = 1 - b + b\,\frac{\mathrm{DL}}{\mathrm{AVDL}}$ — BM25
$F_n = C \cdot n^{-\alpha} \iff \log F_n = -\alpha \log n + \log C$ — Zipf’s Law

Exercises & Exam Questions#

WS 23/24, Task 1.1 (6 points)#

QuestionConsider the following four documents:

Document	Words
D1	b c a c d c
D2	b c a c d c b c
D3	a d a c c b
D4	c a a c c

Write the inverted index with tf (term frequency) scores. For which values of $C$ and $\alpha$ does Zipf’s Law $F_n = C \cdot n^{-\alpha}$ hold exactly?

SuccessSolution

Inverted index (word: list of (document, tf) pairs):

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

Word frequencies (summed across all documents):

c: $3 + 4 + 2 + 3 = 12$
a: $1 + 1 + 2 + 2 = 6$
b: $1 + 2 + 1 = 4$
d: $1 + 1 + 1 = 3$

Sorted: $F_1 = 12,\ F_2 = 6,\ F_3 = 4,\ F_4 = 3$ .

From $F_1 = C = 12$ and $F_2 = 12 \cdot 2^{-\alpha} = 6 \Rightarrow \alpha = 1$ .

Verification: $F_3 = 12/3 = 4$ and $F_4 = 12/4 = 3$ . Both match.

\boxed{C = 12, \quad \alpha = 1}

WS 23/24, Task 1.3 (4 points)#

SuccessSolution

Result list: $[6, 7, 2, 4, 5]$ . Relevant set: $\{1, 2, 3, 4\}$ , so $R = 4$ .

Relevance of result positions: $[0, 0, 1, 1, 0]$ (IDs 2 and 4 are relevant).

$P@2$ : Among the first 2 results $(6, 7)$ , none are relevant.

P@2 = \frac{0}{2} = 0

$P@R = P@4$ : Among the first 4 results $(6, 7, 2, 4)$ , two are relevant (2 and 4).

P@R = P@4 = \frac{2}{4} = \frac{1}{2}

AP: Sum $P@k$ at each relevant position, divided by $R = 4$ .

Position 3 (ID 2, relevant): $P@3 = 1/3$
Position 4 (ID 4, relevant): $P@4 = 2/4 = 1/2$

AP = \frac{1}{4}\left(\frac{1}{3} + \frac{1}{2}\right) = \frac{1}{4} \cdot \frac{5}{6} = \frac{5}{24}

DCG@3: Given $\text{rel}_1 = 0$ , $\text{rel}_2 = 0$ , $\text{rel}_3 = 4$ :

DCG@3 = \frac{0}{\log_2 2} + \frac{0}{\log_2 3} + \frac{4}{\log_2 4} = 0 + 0 + \frac{4}{2} = 2

WS 17/18, Task 1.1–1.2 (10 points)#

Question

Consider a query with four grades of relevance: 0 (not relevant), 1 (slightly relevant), 2 (somewhat relevant), 3 (very relevant). Consider the following result list:

Result	Relevance
#1	0
#2	3
#3	0
#4	2
#5	1

(1.1) Using binary relevance where grades 0,1 are “not relevant” and grades 2,3 are “relevant”, with 3 relevant results overall, compute P@2, P@R, and AP.

(1.2) Using graded relevance, compute DCG@2, iDCG@2, and nDCG@2.

SuccessSolution

1.1 – Binary relevance: Relevant results in the list: #2 (grade 3) and #4 (grade 2). $R = 3$ total relevant.

$P@2 = 1/2$ (one relevant in top 2)
$P@R = P@3 = 1/3$ (one relevant in top 3)
$AP = \frac{1}{3}(P@2 + P@4) = \frac{1}{3}(1/2 + 2/4) = \frac{1}{3} \cdot 1 = 1/3$

1.2 – Graded relevance:

DCG@2 = \frac{0}{\log_2 2} + \frac{3}{\log_2 3} = 0 + \frac{3}{\log_2 3} \approx 1.893

For iDCG@2, sort relevances descending: $[3, 2, 1, 0, 0]$ , so:

iDCG@2 = \frac{3}{\log_2 2} + \frac{2}{\log_2 3} = 3 + \frac{2}{\log_2 3} \approx 4.262

nDCG@2 = \frac{DCG@2}{iDCG@2} = \frac{3/\log_2 3}{3 + 2/\log_2 3} = \frac{3}{3 \log_2 3 + 2} \approx 0.444

Occurrences#

Semester	Task	Points	Subtopics
DBIS Exam WS1516 (not published)	Task 1	20pts	dot-product similarity, AP, rank decomposition
DBIS Exam WS1617 (not published)	Task 1	20pts	tf.idf matrix, tf-to-tf.idf function, P@2, AP
DBIS Exam WS1718 (not published)	Task 1	20pts	P@2, P@R, AP, DCG, nDCG, dcg/ndcg functions
DBIS Exam WS1920 (not published)	Task 1	25pts	Zipf’s law, nDCG function, exponential search
DBIS Exam WS2122 (not published)	Task 1	25pts	tf.idf matrix, dot-product, P@k, galloping search
DBIS Exam WS2223 (not published)	Task 3	20pts	term-document matrix, hyperplane, F1 score
DBIS Exam WS2324 (not published)	Task 1	20pts	tf scores, merge function, P@2/P@R/AP/DCG

Lectures#

DBIS_VL01 — keyword search, inverted index, construction, Zipf’s law
DBIS_VL02 — scored postings, tf, idf, tf.idf, BM25
DBIS_VL11 — term-document matrix; sparse row-major matrix = inverted index; BM25 entries
DBIS_VL13 — example exam task on ranking and precision

Evaluation — measures how good the produced ranking is (P@k, AP, nDCG, bpref)
List Intersection and Search — algorithms for intersecting and merging the inverted lists
Fuzzy Search and Q-Grams — a q-gram index has the same structure as an inverted index (q-grams → word IDs instead of words → document IDs), and candidate filtering reuses the same intersection and merge algorithms
Word Embeddings and Language Models — vector space model and cosine similarity generalize the dot-product ranking

Concepts#

How it fits together#

Key Formulas#

Exercises & Exam Questions#

WS 23/24, Task 1.1 (6 points)#

WS 23/24, Task 1.3 (4 points)#

WS 17/18, Task 1.1–1.2 (10 points)#

Occurrences#

Lectures#

Related Topics#