ConceptDBISAI-written · not yet proofread

Gap Encoding

Gap encoding stores a sorted list as its first element followed by the differences between consecutive elements, which are small numbers that a variable-length integer code compresses well.

Know these firstInverted Index

Properties#

Particularly effective for the sorted inverted lists (List Intersection needs them sorted): the more frequent a word, the denser its list and the smaller the gaps, so few bits per posting.
Lists must be decoded sequentially (prefix sums) to reach an element.

Example#

$1, 10, 11, 20, 21, 30, 31, 40$ becomes $1, 9, 1, 9, 1, 9, 1, 9$ (DBIS Exam WS1314 (not published), Task 1.1). For the entropy-optimal code of the gaps (two values with probability $\tfrac12$ each, lengths 1 bit) see Entropy-Optimal Code.

Sources#

DBIS Exam WS1314 (not published) Task 1
Not lectured in WS 25/26 (DBIS_VL13 > Work at the Chair announces compression for the advanced course).

Connections

Prerequisites know first1

Inverted Index

Mentioned in inline links2

Golomb Code
Tunable by $M$ : a larger $M$ shortens the unary part but lengthens the remainder. A good $M$ matches the typical size of the numbers, which is why Golomb codes suit gaps of inverted lists. §
Encodings and Compression
Gap Encoding — turns the sorted IDs of an inverted list into small numbers that the integer codes compress well §
Where the numbers come from. The sorted document IDs of an inverted list are large, but their differences are small, especially in the long lists of frequent words (Zipf’s law: a few words account for most occurrences). Gap Encoding turns… §

Search in these mentions →