Chimp: Efficient Lossless Floating Point Compression for Time Series Databases
作者： Panagiotis Liakos, Katia Papakonstantinopoulou, Yannis Kotidis
出处： VLDB（CCF A）
年份： 2022
链接：
简介：
- 目前广泛运用在时间序列管理系统中有效的压缩算法是当前值与前一个值之间按位异或运算，由于相邻数据点之间不会产生巨大的变化，因而异或的结果中会存在大量的零。
- Goriila算法即是以此为基础，但这类算法相比传统算法而言压缩空间有限。
- Chimp的方法侧重于XOR结果中尾随零数量有限，相反存在大量的前导零。
- Chimp对比前导零与尾随零的存储成本调整前导零与尾随零的存储，不仅与前一个值进行比较，还与前置其他位数据进行比较，以此节省存储空间中有效位存储的成本。
关键算法：
- 分为四种情况区别时间序列，Chimp使用按位XOR运算利用测量之间的相似性，使用映射函数代表前导零的长度，在XOR结果编码一个零位弥补奇数映射的误差。初始值写入，设定尾随零数量的阈值，如果大于6，写入0位，如果xor值位0，写入0，否则写入1，写入前导零的数量，写入有意义位的数量和有意义的部分。如果小于或者等于这个阈值，写入1位，如果前置零等于先前的前置零，写入0位，然后写入异或值，去掉前导零。否则写入1位，写入lead的数量，写入整个XOR值。
- Chimp128的是考虑了先前的128个值，利用环形缓冲区与前128个值里的最佳值进行XOR按位运算，并于普通的存储方式比较，选取存储位数更少的。
存在的问题/后续方向：
代码复现链接：