Delta Encoding
Delta encoding replaces each element of a sequence with its difference from the previous element, making slowly changing or monotonically increasing sequences more compact.
Purpose
It compresses integer sequences with temporal or spatial locality, such as timestamps, incrementing IDs, and audio PCM samples.
Mechanism
The first element is stored as-is and each subsequent element is stored as x[i] - x[i-1]; decoding accumulates the differences back into the original sequence. It is often chained with Varint/ZigZag to further compress the deltas.
Use cases
- Timestamp sequence compression
- Document ID gaps in inverted indexes
- Differential PCM audio