Measured trade offs of random access in compressed data formats
The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms
Summary
Compressed data is usually stored in a way that makes jumping to any small piece tricky and costly. This paper measures exactly how much extra space you need to make random access possible in four popular compression formats. The authors show that the cost is surprisingly small for some formats, which means data can be split into independently accessible chunks without much penalty. They also prove some new properties about how the compression works internally and share a tool to reproduce their measurements.
What this means in practice
- •For software developers: Create compressed archives that allow instant access to small data chunks without large size increases.
- •For gpu programmers: Use a single compressed file read by both CPU and GPU decoders efficiently thanks to small random access overhead.
Authors
Yakiv Shavidze
Abstract
Random access into compressed data is normally bought with density. We measure the exchange rate. Across four formats and nine axes on a common corpus, the cost of cutting a 254 MB archive into independently addressable 16 KiB units is 1.632% of the archive for an absolute-offset format against 6.57% for seekable zstd, and the gap widens as the unit shrinks: at 4 KiB, 5.33% against 10.06%. Because the cost is small, several properties follow that are usually unavailable: splitting an archive is free and occasionally profitable (-0.28% on tiled input), append needs no format change, seek latency does not depend on position, and one archive is read by both a CPU and a GPU decoder. We give three structural results with proofs and bit-perfect verification - that the repeat-distance chain of an LZ77 parse forms a substitution monoid and is therefore prefix-scannable without touching the bitstream, that self-overlapping matches are periodic rather than chained, and that dependency depth admits an encoder-enforced bound - and we report each measured limit together with the mechanism that sets it. Seventeen rejected directions are listed with their numbers, including one that improved density by 26% and was declined. Every claim carries a level: reproducible by command, measured with a stated reason, or estimated. The measurement tool is released separately (DOI 10.5281/zenodo.22713364) with 435 provenanced records.