Information Retrieval · Cluster
Indexing
Inverted indexes and compression.
- 01 Postings Lists as Sorted DocID Arrays Why an inverted index keeps document identifiers in ascending order, how that ordering turns conjunction into a merge of cursors, and what the layout costs when lists grow long.
- 02 Term Dictionary Lookup Structures for Inverted Indexes How an index maps a query term to its postings offset, why the dictionary is kept in memory in a different layout from the postings, and what each structure trades for lookup speed.
- 03 Delta Encoding and Variable-Byte Postings How storing document identifier differences instead of absolute identifiers shrinks a postings list, when the vByte continuation-bit scheme wins over fixed-width storage, and where it stops paying.
- 04 Bit Packing and Frame-of-Reference Blocks How choosing a bit width per block of postings beats byte-aligned codes, what the block maximum costs in wasted bits, and why patched exceptions sometimes beat both.
- 05 Document-at-a-Time and Term-at-a-Time Evaluation Two ways to turn postings lists into ranked results: accumulate per document, or merge per term. What each order costs in memory, latency, and early termination.
- 06 Front Coding the Term Dictionary How sharing prefixes between adjacent sorted terms compresses the dictionary, what block size has to do with random access, and where the savings actually come from.
- 07 Positional Indexes and Phrase Verification Why phrase queries need positions and not just identifiers, how a positional postings list stores them compactly, and the cost of exact phrase matching.
- 08 Impact-Ordered Postings and Early Termination How reordering postings by score contribution instead of document identifier enables early termination, and what it does to merge semantics, memory, and result quality.
- 09 Elias-Fano Encoding for Monotone Sequences How splitting each integer into a high and low part stores a sorted sequence at near-optimal space while keeping random access, and what a select operation costs.
- 10 Golomb-Rice Coding for Postings Gaps How splitting a gap into a quotient and remainder against a tuned divisor makes an optimal code for geometric distributions, and how the divisor is chosen without knowing the data.