arXiv preprint ·
The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Distributed & Parallel Computing
Adaptive Bayesian Partner Selection for Federated Clinical Centers
ASPIRE: Asynchronous Batched Self-Speculative Decoding for Long-Context LLM Inference
High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models
Large Language Model based air quality monitoring and localized alert generation
vidax: A Unified JAX Framework for Video Generative Models on Accelerator Meshes
Get the few papers worth your time in Distributed & Parallel Computing every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.