Index Compression

What are the primary advantages of index compression in IR?

Saves memory/disk space, speeds up query processing by reducing disk I/O, and improves data transfer speed across networks or buses.

Which two main components of an inverted index are compressed?

The Dictionary/Vocabulary (kept in main memory) and the Postings Lists (reduces disk reads and storage).

What is the difference between Lossy and Lossless compression in indexing?

Lossless compression preserves all original text data during decoding, while Lossy compression discards non-critical text variations prior to indexing (e.g., lowercasing, stemming, stop words).

What does Heaps' Law predict?

The growth of vocabulary size (M) relative to the total number of tokens (T) in a document collection.

What is the mathematical formula for Heaps' Law?

M = k * T^b, where M is vocabulary size, T is token count, 30 <= k <= 100, and b ≈ 0.5.

What does Zipf's Law describe?

The relative frequency of terms in a collection, stating that term frequency is inversely proportional to its rank.

What is the mathematical formula for Zipf's Law?

cf_i = K / i, where cf_i is the collection frequency of the i-th most frequent term and K is a normalizing factor.

Why is a fixed-width term array wasteful for dictionary storage?

It allocates a fixed byte length (e.g., 20 bytes) for every term, wasting space on short words when the average word length is only ~8 characters.

How does the Dictionary-as-a-String method work?

It concatenates all terms into a continuous character string and uses pointers to mark term boundaries, saving up to 60% of space.

How does Blocking compress the dictionary string?

It stores pointers for only every k-th term (e.g., k=4) and adds a 1-byte term length indicator, reducing space down to ~7 bytes/term.

What is Front Coding?

A compression technique that removes common prefixes from sorted consecutive dictionary words and encodes only the suffix differences.

Why are postings lists stored as gaps instead of absolute docIDs?

Postings are sorted by docID, so storing incremental differences (gaps) yields much smaller integers that require far fewer bits/bytes to encode.

How does Variable Byte (VB) encoding work?

It encodes gap sizes using dynamic byte blocks where 7 bits store binary data and 1 bit (continuation bit) indicates if more bytes follow for that integer.

How is an integer n represented in Unary code?

As n ones followed by a terminal zero (e.g., 4 is represented as 11110).

What are the two components of an Elias Gamma (γ) code?

Length (the length of the offset represented in Unary) and Offset (the binary value of the gap with the leading 1 removed).

What is the size formula for a gap G encoded with Elias Gamma code?

2 * floor(log2(G)) + 1 bits.

How does PForDelta (Patched Frame-of-Reference) compression work?

It packs a fixed block of postings using a bit-width that fits a selected high percentile (e.g., 90%) of gaps, storing larger outlier values separately as chained exceptions.

How does Simple9 packing work?

It fits multiple small gap integers into a single 32-bit word boundary using 4 control bits to choose 1 of 9 possible bit-packing schemes.