LeCo: Lightweight Compression via Learning Serial Correlations
Authors:
- Yihao LiuYLYihao Liu
- Xinyu ZengXZXinyu Zeng
- Huanchen ZhangHZHuanchen Zhang
Preprint
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 simultaneously. LeCo presents a general approach to this end, making existing (ad-hoc) 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 six 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 3.9x speed up in filter-scanning a Parquet file and a 16% increase in Rocksdb's throughput.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Piecewise linear approximation of streaming time series data with max-error guarantees2015
- Survey on Anomaly Detection using Data Mining TechniquesProcedia Computer Science, 2015
- 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
- A new rank correlation measureStatistical Papers, 2011
- A Difference Fitting Residuals algorithm for lossless data compression in wireless sensor nodes2011
- On data mining, compression, and Kolmogorov complexityData Mining and Knowledge Discovery, 2007
- Data compression and database performance2002
- The minimum description length principle in coding and modelingIEEE Transactions on Information Theory, 1998