2024-06-03
上海期智研究院PI、清华大学助理教授张焕晨团队聚焦高效的数据压缩和索引技术研究，旨在消耗更少的内存和存储空间的同时，提高系统查询数据的性能，为AI和大数据应用提供坚实的数据存储底座。近期，团队首次在数据库中提出了Learned Compression (LeCo)数据压缩框架。LeCo框架最大的贡献在于其在实践中打通了数据压缩和数据挖掘之间的技术隔阂，使得数据挖掘中的各类模式识别算法可以直接用于数据序列的压缩，因而有望成为新一代数据压缩算法的开山之作。张焕晨团队本年度有5项研究成果收录于在数据库领域具有最高学术地位的国际性学术会议ACM SIGMOD 2024中（共接收213篇），扎实地推动了大数据存储技术的进步。
Innovation Highlights
提出了Learned Compression (LeCo)数据压缩框架。该框架创新地利用机器学习算法消除数据中的序列相关性冗余，不仅使数据列的压缩率显著提高，而且支持超低延迟的随机访问。在实践中打通了数据压缩和数据挖掘之间的技术隔阂，使得数据挖掘中的各类模式识别算法可以直接用于数据序列的压缩。
Achievements Summary
LeCo—基于机器学习的轻量级数据压缩
当今海量数据的产生与对查询极高的响应时间要求，让大数据压缩技术面临着全新的挑战。轻量级数据压缩是一项使列存储在分析查询中表现出优越的性能的关键技术。大量的已有工作都基于字典编码展开，而少有系统地利用列中的序列相关性进行压缩的工作。
相对于传统的消除数据重复的思路，张焕晨团队从一个全新的角度建模数据压缩问题，首次提出了Learned Compression（LeCo）数据压缩框架，一个利用机器学习自动消除相似性冗余以实现出色压缩比和解压性能的框架。LeCo将现有算法融入框架中，使得压缩率突破信息熵下界，同时加速解码过程以提升后续计算的效率。
图1. LeCo框架 - 各模块及其交互概述
LeCo框架的核心创新在于：
（1）使用机器学习来识别和利用数据中的序列相关性，这是之前研究中未被系统性利用的领域。
（2）提出了一种通用方法，将现有的算法如Frame-of-Reference (FOR)、Delta编码和Run-Length编码（RLE）作为特殊情况纳入其框架。
（3）通过形状编码技术，将序列划分和回归模型结合，以实现高效的压缩。
（4）包含一个超参数顾问，用于选择最佳的回归模型类型和压缩比。
图2. LeCo字符串压缩 - 包括算法和存储格式修改的示例
在实验测试的十二个数据集上，LeCo在压缩比和随机访问速度上比现有解决方案实现了Pareto改进。将LeCo集成到广泛使用的系统中时，在列式执行引擎Arrow+Parquet上有5.2倍的查询加速，而在RocksDB中的吞吐量增加了16%。
图3. 压缩微基准测试
针对现实系统中的混合事物分析场景，提出了系统性压缩的工具链。在列存的基础上，提出解决方案LeCo，用数据挖掘和模式识别技术将单列数据的分布信息凝缩在模型中，并存储错误修正码以实现无损压缩。在多个真实系统测试中，该压缩方案凭借突出的压缩率与轻量级解压操作提升查询速度、缓解内存瓶颈，在Parquet读取和Hash join算子中有着高至12倍和96倍的速度提升。
图4. 性能-空间的权衡
LeCo框架的应用价值体现在能够为现代数据分析系统提供更高的性能和存储效率，同时保持了良好的兼容性和易用性。LeCo在不同的工作负载和数据集上都展现出了卓越的性能，证明了其在实际应用中的潜力。本论文一作为上海期智研究院实习生、清华大学交叉信息学院博士生刘奕好。
更多信息请阅读论文：
1. GRF:A Global Range Filter for LSM-Trees with Shape Encoding, Hengrui Wang, Te Guo, Junzhao Yang, Huanchen Zhang*, SIGMOD 2024.
2. LeCo: Lightweight Compression Via Learning Serial Correlations, Yihao Liu, Xinyu Zeng, Huanchen Zhang*, SIGMOD 2024.
3. Making In-Memory Learned Indexes Efficient on Disk, Jiaoyi Zhang, Kai Su, Huanchen Zhang*, SIGMOD 2024.
4. SALI: A Scalable Adaptive Learned Index Framework based on Probability Models, Jiake Ge, Huanchen Zhang, Boyu Shi, Yuanhui Luo, Yunda Guo, Yunpeng Chai, Yuxing Chen, and Anqun Pan*, SIGMOD 2024.
5. PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware, Shuangyu Cai, Boyu Tian, Huanchen Zhang, and Mingyu Gao*, SIGMOD 2024.
