LeCo: Lightweight Compression via Learning Serial Correlations
Open Access
- 12 March 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (1) , 1-28
Abstract
Lightweight data compression is a key technique that allows column stores to exhibit superior performance for analytical queries. Despite a comprehensive study on dictionary-based encodings to approach Shannon's entropy, few prior works have systematically exploited the serial correlation in a column for compression. In this paper, we propose LeCo (i.e., Learned Compression), a framework that uses machine learning to remove the serial redundancy in a value sequence automatically to achieve an outstanding compression ratio and decompression performance. LeCo presents a general approach to this end, making existing algorithms such as Frame-of-Reference (FOR), Delta Encoding, and Run-Length Encoding (RLE) special cases under our framework. Our microbenchmark with three synthetic and eight real-world data sets shows that a prototype of LeCo achieves a Pareto improvement on both compression ratio and random access speed over the existing solutions. When integrating LeCo into widely-used applications, we observe up to 5.2× speed up in a data analytical query in the Arrow columnar execution engine, and a 16% increase in RocksDB's throughput.Keywords
All Related Versions
This publication has 75 references indexed in Scilit:
- A time-series compression technique and its application to the smart gridThe VLDB Journal, 2014
- Maximum error-bounded Piecewise Linear Representation for online stream approximationThe VLDB Journal, 2014
- Decoding billions of integers per second through vectorizationSoftware: Practice and Experience, 2013
- SAP HANA databaseACM SIGMOD Record, 2012
- A new rank correlation measureStatistical Papers, 2011
- Compressing Integers for Fast File AccessThe Computer Journal, 1999
- Small-dimensional linear programming and convex hulls made easyDiscrete & Computational Geometry, 1991
- A universal algorithm for sequential data compressionIEEE Transactions on Information Theory, 1977
- Program design for retrospective searches on large data basesInformation Storage and Retrieval, 1972
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952