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
📐 Mathematical Definition
⚡ 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 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 prefix lookups.
(2) Posting List Structure:
For each term , its posting list records:
- doc_id: Monotonically increasing document identifiers, compressed via delta encoding (storing ) and variable-byte (VByte) or SIMD-PForDelta compression.
- Positions: Word offsets within the document, essential for exact phrase matching ( followed immediately by , i.e., ) 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 complexity.
- Disjunctive (OR) Query with WAND (Weak AND): Iterates candidate documents using dynamic upper bounds on BM25 scores. If (where is the current -th best score in a min-heap), the document is safely skipped without evaluating full scores, yielding 5x-20x acceleration.
(1) Term Dictionary:
The set of all unique vocabulary terms 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 prefix lookups.
(2) Posting List Structure:
For each term , its posting list records:
- doc_id: Monotonically increasing document identifiers, compressed via delta encoding (storing ) and variable-byte (VByte) or SIMD-PForDelta compression.
- Positions: Word offsets within the document, essential for exact phrase matching ( followed immediately by , i.e., ) 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 complexity.
- Disjunctive (OR) Query with WAND (Weak AND): Iterates candidate documents using dynamic upper bounds on BM25 scores. If (where is the current -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 posting lists with delta compression), explain how positions unlock phrase matching, and detail how WAND/BMW achieves sublinear top- 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.
📚