Summary 14 — Indexing, Part I (Inverted Indexes & Query Processing)

Source: 10_Indexing_Part-I.pdf

1. Table of Contents (Topics Covered)

Why efficiency matters; efficiency metrics
Semi-static collections & incremental indexing
Inverted indexes: vocabulary + occurrences
Term-document matrix vs. occurrence lists
Full inverted indexes (with positions); space costs (Heaps’ law)
Block addressing for space reduction
Query processing: single-word, multiple-word (conjunctive/disjunctive)
List intersection/merging algorithms
Phrase & proximity queries; prefix/range/regex; Boolean query evaluation (full vs. lazy)

Gist (2–3 paragraphs)

While effectiveness (relevance) gets attention, efficiency can’t be neglected — web engines index terabytes and serve thousands of queries per second. An index is a data structure built from text to speed searches, evaluated by indexing time/space, index storage, query latency, and query throughput. Since updating indexes on changing text is costly, real collections (including the Web) are treated as semi-static (updated at regular intervals) with incremental indexing for freshness.

The workhorse structure is the inverted index: a vocabulary (all distinct words) plus occurrences (for each word, the list of documents — and, in a full inverted index, the exact positions — where it appears). It replaces the wasteful sparse term-document matrix. By Heaps’ law the vocabulary grows sub-linearly (O(n^β)) and stays small (often fits in RAM), but the occurrences are large — roughly 40% of text size without stopwords, 80% with. Block addressing (pointing to text blocks rather than exact positions) reduces space and exploits locality of reference.

Query processing depends on query type. Single-word queries just fetch one occurrence list (vocabulary lookup via hashing/tries/B-trees in O(m)). Multi-word queries are conjunctive (AND → intersect lists) or disjunctive (OR → merge lists); intersection is the costliest operation, optimized via binary search when one list is much shorter, or Baeza-Yates’ double binary search. Phrase/proximity queries traverse lists to find words in sequence or nearby. Prefix/range queries become large disjunctions; regex requires sequentially scanning the (small) vocabulary. Boolean queries build a syntax tree, evaluated in full (compute all operands first) or lazy (deliver partial results on demand) form, in three phases: match → score → locate positions.

2. Key Terminologies — Meaning & Use Cases

Term	Meaning	Use Case
Index	Data structure to speed searches	Core of any IR engine
Query latency / throughput	Time per query / queries per second	Performance metrics
Semi-static collection	Updated at regular intervals	Web, document archives
Incremental indexing	Update index without full rebuild	Maintaining freshness
Inverted index	Vocabulary + per-word document lists	Fast keyword search
Vocabulary	Set of all distinct words	Lookup structure (in RAM)
Occurrences	Lists of docs/positions per word	The bulk of the index
Full inverted index	Occurrences include positions	Phrase/proximity queries
Heaps’ law	Vocabulary grows as O(n^β)	Predict index size
Block addressing	Point to text blocks, not positions	Space reduction
Conjunctive / disjunctive	AND (intersect) / OR (merge)	Multi-word queries
List intersection	Merge two occurrence lists	Costliest operation
Double binary search	Efficient intersection (Baeza-Yates)	Comparable-size lists
Boolean syntax tree	Tree of operators over operand sets	Boolean query evaluation
Full vs. lazy evaluation	Compute all vs. on-demand	Query tree processing

3. Process Workflow Diagram

flowchart TD
    A[Text Collection] --> B[Build Vocabulary]
    B --> C[Build Occurrence Lists
docs + positions]
    C --> D[Inverted Index
+ block addressing]
    E[User Query] --> F{Query type}
    F -->|Single word| G[Fetch one list]
    F -->|AND| H[Intersect lists]
    F -->|OR| I[Merge lists]
    F -->|Phrase/Proximity| J[Traverse + position check]
    F -->|Boolean| K[Syntax tree: full/lazy eval]
    D --> G
    D --> H
    D --> I
    D --> J
    D --> K
    G --> L[Results]
    H --> L
    I --> L
    J --> L
    K --> L

4. ELI5 — Complex Terms Explained Simply

Inverted index: The book index flipped around — for every word it lists all the pages it’s on, so you never read the whole book to find a word.
Vocabulary vs. occurrences: The vocabulary is the list of words (small, kept in memory); the occurrences are the long lists of where each word appears (big, kept on disk).
Full inverted index: Also remembers the exact position of each word, so you can find phrases like “New York” in order.
Heaps’ law: New words keep appearing as text grows, but slower and slower — so the word list stays manageable.
Block addressing: Instead of saying “word is at character 5,142,” just say “word is in chapter 3” — less precise, much smaller.
Conjunctive (AND) query: “cat AND dog” → find pages in both word lists (intersection).
Disjunctive (OR) query: “cat OR dog” → combine both lists (merge).
List intersection: Comparing two lists to find what they share — the slowest part, so it’s heavily optimized.
Lazy evaluation: Don’t compute everything up front — only work out a result when it’s actually needed.