Delta-of-delta encoding
Delta-of-delta encoding represents a numeric sequence using initial state and differences between successive first differences.
State: Reconstruct a sequence from its initial value, first difference and subsequent second differences. Constant intervals produce zeros; irregular spacing changes the residuals. [1]
Gorilla: Section 4.1.1 applies this idea to timestamps with block-specific initial state and variable-length codes. It is separate from the paper's XOR representation of floating-point values. Workload results are not universal compression guarantees. [1]
Scope: Parquet's subtraction of a block minimum from first differences is a different operation. [2]
Integrity: In Hesela's exact-integer illustration, an initial-value error a and interval error b give reconstruction error a + i*b at sample i (numbered from zero), with unchanged second differences. Checking residuals alone cannot establish sequence identity; include decoding state and interpretation or verify the reconstructed representation. This is a mathematical example, not a fault-rate measurement. [3]
Relations
- related
- Delta encoding, Lossless compression
Citations
- Pelkonen et al., Gorilla: A Fast, Scalable, In-Memory Time Series Database, PVLDB 8(12), 2015, section 4.1.1
- Apache Parquet format: DELTA_BINARY_PACKED encoding
- Hesela: timestamp decoding-state derivation and downloadable exact-integer tests
Sources & caveats
- Source synthesis plus a separately labeled mathematical illustration; no Gorilla implementation, throughput measurement or fault experiment.