Aarhus University Seal

A Randomly Accessible Lossless Compression Scheme for Time-Series Data

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


  • master

    Accepted manuscript, 613 KB, PDF document


We detail a practical compression scheme for lossless compression of time-series data, based on the emerging concept of generalized deduplication. As data is no longer stored for just archival purposes, but needs to be continuously accessed in many applications, the scheme is designed for low-cost random access to its compressed data, avoiding decompression. With this method, an arbitrary bit of the original data can be read by accessing only a few hundred bits in the worst case, several orders of magnitude fewer than state-of-the-art compression schemes. Subsequent retrieval of bits requires visiting at most a few tens of bits. A comprehensive evaluation of the compressor on eight real-life data sets from various domains is provided. The cost of this random access capability is a loss in compression ratio compared with the state-of-the-art compression schemes BZIP2 and 7z, which can be as low as 5% depending on the data set. Compared to GZIP, the proposed scheme has a better compression ratio for most of the data sets. Our method has massive potential for applications requiring frequent random accesses, as the only existing approach with comparable random access cost is to store the data without compression.
Original languageEnglish
Title of host publicationIEEE INFOCOM 2020
Publication year2020
Publication statusPublished - 2020
EventIEEE Conference on Computer Communications - Toronto , Canada
Duration: 6 Jul 20209 Jul 2020


ConferenceIEEE Conference on Computer Communications

See relations at Aarhus University Citationformats


Download statistics

No data available

ID: 196556774