Summary 15 — Indexing, Part II (Searching, Construction & Structural Queries)

Source: 10_Indexing_Part-II.pdf

1. Table of Contents (Topics Covered)

Ranking with weight-sorted inverted lists; top-k retrieval (Persin’s algorithm)
Index construction — internal (in-memory) algorithms
External algorithms for large collections (partial indexes + merging)
Index maintenance strategies: rebuild, incremental, intermittent merge
Structural queries over tagged text

Gist (2–3 paragraphs)

This part covers searching with ranking, building the index, and structural queries. For ranking, a single-word query is trivial (the list is already sorted by weight), but multi-word queries require merging lists to find the top-k documents. A practical heuristic (a variant of Persin’s algorithm) processes query terms in IDF order (shortest lists first) and each term in TF order, maintaining a priority queue of candidate documents and a per-term threshold below which it’s not worth adding partial similarities — letting the search skip the rest of a list early.

Index construction in internal memory is straightforward: scan the text, look up each word in a dynamic vocabulary structure (B-tree/hash), insert new words, and append occurrences (allocating memory in blocks rather than per-element to avoid waste). When memory runs out, external algorithms kick in: write the partial index to disk, clear memory, and later merge partial indexes hierarchically (binary fashion). Index maintenance has three strategies: rebuild (simplest, for small texts), incremental updates (amortize cost during searches, modifying lists only when needed), and intermittent merge (index new documents into a partial index, then merge with the main one — generally the best solution).

Structural queries (over documents with markup tags) are handled elegantly by treating tags as if they were words in the inverted index. Then a query like “select elements of type A that contain a structure of type B” becomes “find <A> followed by <B> without </A> in between,” resolved using the positions in the full-text index. Many structural queries reduce to searching for tags plus validating the sequence of their occurrences — efficient and easy to integrate into an existing text database.

2. Key Terminologies — Meaning & Use Cases

Term	Meaning	Use Case
Top-k retrieval	Find the k highest-ranked documents	Returning best results
Weight-sorted lists	Occurrence lists ordered by term weight	Efficient ranking
Persin’s algorithm	Threshold-based top-k with priority queue	Skip low-value list tails
IDF/TF processing order	Shortest lists first, then by frequency	Ranking heuristic
Internal (in-memory) construction	Build index in RAM	Small collections
External algorithms	Partial indexes written to disk + merged	Large collections
Partial index	Index segment built before memory fills	Scalable construction
Hierarchical merge	Merge partial indexes in binary fashion	Combining segments
Rebuild / incremental / intermittent merge	Three maintenance strategies	Keeping index current
Structural query	Query over tagged document structure	XML/HTML element search
Tags-as-words	Index markup tags like terms	Answering structural queries

3. Process Workflow Diagram

flowchart TD
    subgraph Construct[Index Construction]
        A[Scan text word by word] --> B[Lookup in vocabulary
B-tree / hash]
        B --> C{New word?}
        C -- Yes --> D[Insert into vocabulary]
        C -- No --> E[Append occurrence]
        D --> E
        E --> F{Memory full?}
        F -- Yes --> G[Write partial index to disk]
        G --> H[Hierarchical merge]
        F -- No --> A
    end
    subgraph Search[Ranked Search]
        I[Multi-word query] --> J[Process terms in IDF order]
        J --> K[Priority queue + threshold
Persin's algorithm]
        K --> L[Top-k documents]
    end
    subgraph Maintain[Maintenance]
        M[Rebuild] 
        N[Incremental updates]
        O[Intermittent merge - best]
    end

4. ELI5 — Complex Terms Explained Simply

Top-k retrieval: You only want the best 10 answers, not all 10,000 — so the engine stops early once it’s sure it has the winners.
Persin’s algorithm / threshold: Like skimming a leaderboard — once scores drop below a cutoff, you stop reading because no one below can crack the top 10.
IDF order (shortest first): Start with the rarest word — its list is short, so you have fewer documents to check.
Internal vs. external construction: Build the index in fast memory until it’s full, then spill the overflow to disk and stitch pieces together later.
Partial index + merge: Build the index in chunks (because it’s too big for memory at once), then combine the chunks like merging sorted piles of cards.
Maintenance strategies: Rebuild = start over (fine if small); incremental = patch as you go; intermittent merge = build a small new index and fold it into the big one (usually best).
Structural queries (tags-as-words): Treat <title> and </title> like ordinary words in the index, so you can search where in the structure something appears, not just the words.