M7-002M7: Retrieval, Ranking & RecSysSparse Retrieval (BM25 / TF-IDF)Easy
⚡Flashcard Drill➔Mastery:

Explain the Structure and Query Processing Pipeline of an Inverted Index

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M7-003 →
📐 Mathematical Definition
inverted index: t→[(d1,f1,pos), (d2,f2,pos),… ]\text{inverted index}:\ t\to[(d_1,f_1,\text{pos}),\ (d_2,f_2,\text{pos}),\dots]
⚡ One-Sentence Core Answer
An inverted index maps vocabulary terms to posting lists containing document IDs, term frequencies, and positions; query processing intersects or unions posting lists before ranking documents via scoring algorithms.

📌 Key Takeaways

  • •
    Dual-component architecture: Term dictionary (lexicographically ordered vocabulary) plus posting lists (inverted index entries per term).
  • •
    Posting list contents: Contains sorted document IDs, term frequencies, and positional offsets (enabling exact phrase and proximity search).
  • •
    Query execution: Retrieves posting lists for query terms, executes set intersection (AND) or union (OR) via two-pointer merges or skip lists, and scores candidates.

📐 Mathematical Derivations

Mathematical & Algorithmic Formulation: Architecture of an Inverted Index.

(1) Term Dictionary:
The set of all unique vocabulary terms V={t1,t2,…,t∣V∣}V = \{t_1, t_2, \dots, t_{|V|}\} sorted lexicographically. In production engines (e.g., Lucene), dictionaries are compressed using Finite State Transducers (FST) or prefix trees, keeping memory footprints minimal while supporting O(len(query))O(\text{len}(\text{query})) prefix lookups.

(2) Posting List Structure:
For each term tt, its posting list records:
P(t)=[(doc_id1,tf1,[pos1,pos2,… ]),(doc_id2,tf2,[… ]),…]P(t) = \big[ (\text{doc\_id}_1, \text{tf}_1, [\text{pos}_1, \text{pos}_2, \dots]), (\text{doc\_id}_2, \text{tf}_2, [\dots]), \dots \big]
- doc_id: Monotonically increasing document identifiers, compressed via delta encoding (storing Δ=doc_idi−doc_idi−1\Delta = \text{doc\_id}_{i} - \text{doc\_id}_{i-1}) and variable-byte (VByte) or SIMD-PForDelta compression.
- Positions: Word offsets within the document, essential for exact phrase matching (t1t_1 followed immediately by t2t_2, i.e., pos(t2)−pos(t1)=1\text{pos}(t_2) - \text{pos}(t_1) = 1) and proximity scoring.

(3) Query Processing Pipeline:
- Conjunctive (AND) Query: Multi-way intersection of posting lists. By sorting posting lists by length, engines iterate through the shortest list and probe longer lists using skip pointers / skip lists, achieving sublinear O(∣Pmin∣log⁡∣Pmax∣)O(|P_{\text{min}}| \log |P_{\text{max}}|) complexity.
- Disjunctive (OR) Query with WAND (Weak AND): Iterates candidate documents using dynamic upper bounds on BM25 scores. If ∑tUt(d)<θ\sum_{t} U_t(d) < \theta (where θ\theta is the current KK-th best score in a min-heap), the document is safely skipped without evaluating full scores, yielding 5x-20x acceleration.

🏭 Production Trade-offs

In-Depth Analysis & Engineering Trade-offs: ① Strict monotonic ordering by doc_id is the prerequisite for linear merge acceleration—it allows two-pointer merges, Galloping search, and skip-list probing. ② Positional payload overhead—storing exact token positions inflates index size by 2x to 4x compared to doc-only indices; engines frequently maintain dual indices (a lightweight doc-only index for boolean filtering and a positional index for phrase ranking). ③ WAND and Block-Max WAND (BMW) optimizations—production engines rely on precomputed block-level upper-bound scores to prune 90%+ of candidate evaluations; this is standard in industrial search. ④ FST compression of term dictionaries—Lucene encodes terms in FSTs in RAM to achieve zero-disk overhead for dictionary scans. ⑤ AND vs. OR precision-recall trade-off—strict AND guarantees high precision but suffers recall drop on multi-token long queries; production search uses 'Match Query with minimum_should_match' or soft disjunction. ⑥ Interview takeaway—clarify the structural hierarchy (FST dictionary →\to posting lists with delta compression), explain how positions unlock phrase matching, and detail how WAND/BMW achieves sublinear top-kk ranking.
⚠️ Common Interview Pitfalls
  • ✕
    Omitting token positional offsets in system designs, rendering phrase queries ('machine learning') and proximity boosts impossible.
  • ✕
    Sorting the entire corpus during disjunctive OR queries instead of maintaining a min-heap bounded by WAND/BMW pruning.
  • ✕
    Storing absolute document IDs directly, leading to massive memory bloat instead of utilizing delta encoding (PForDelta/VByte).
🎯 Interviewer Follow-up Inquiries
  • ?
    How do skip pointers reduce posting list intersection time from linear to sublinear?
  • ?
    How does Block-Max WAND (BMW) leverage chunk-level maximum scores to accelerate top-k retrieval?
  • ?
    How do search engines handle real-time index updates without locking read queries?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM7-001: Write the BM25 Formula and Explain the Roles of Hyperparameters k1 and b📋 Back to BankNext →M7-003: Explain the Motivation Behind TF-IDF and Its Two Constituent Components