VIREL: Route-Local Lattice Residual Compression for Exact and Error-Bounded Floating-Point Time Series

Abstract

Time-series databases store floating-point columns in independent pages that are written at ingest, rewritten at compaction, and decoded on every scan. Some columns must return the stored IEEE 754 word; others accept a pointwise bound $\epsilon$. Codecs for both contracts turn each value into an integer on a lattice, but a real page mixes decimal resolutions. Keeping one scale per block charges every coarse step for the finest value: one scale-6 reading in a 1,024-value page cuts Falcon's compression ratio by 36%. We present VIREL, route-local lattice residual compression. A value enters a lattice only after the encoder has replayed the decoder's arithmetic on it. VIREL-Exact replays the decoder's division at each value's least decimal scale, which we prove always succeeds below $2^{51}$, gives every resolution its own lane and history, and places averages on a rational lattice; the same finer value costs it 0.6%. VIREL-EB replays a fused multiply-add on an error lattice, so every admitted value decodes within $\epsilon$. One integer coder serves both contracts. On 14 canonical streams, VIREL-Exact emits 27.6% fewer bytes than Falcon. Fast beats ALP on ratio and both speeds at once: 7.01$\times$ against 4.19$\times$, 476 against 120 MB/s, and 5.0 against 4.5 GB/s on one core. Upper is the smallest output on all 48 larger streams. Ingest with Fast and compaction with Upper store those streams in Apache TsFile at 48.7% of ALP's bytes. VIREL-EB beats Machete on ratio and both speeds in all 90 dataset-bound cells.