引言

目前监控业务中绝大多数数据仍旧是浮点，且更让人关心的其实是大盘的趋势而不是精确的秒级数据，虽然Continuous Queries，预降采样可以以极低的成本满足部分查询的需求，但是源数据本身的存储也是必不可少的；分层存储已经可以使得冷数据可以降低到COS这样的低成本介质中，但是存储带宽也是一个不可忽略的因素，所以对于时序数据来说数据量本身是需要仔细斟酌的点。

工作以来没法像在学校一样用大段的时间去完成一篇博客，基本上是利用碎片时间完成寥寥几百的文字，但是又不想博客就这样搁置，就这样梳理梳理后作罢吧。

Part1

IPDPS16的论文《Fast Error-bounded Lossy HPC Data Compression with SZ》阐述了一种新的可限定误差边界的浮点有损压缩算法，和VLDB2015《A time-series compression technique and its application to the smart grid》中提出的基于贪心的分片多项式近似法基本类似，都是基于临近几个点去在目标错误限定范围内找到合适的曲线测定模型。

对于在限定误差边界以内的点称为 Predictable Data（可预测点），进而用两个比特结合前面几个点的预测值来描述这个点，因为这个描述曲线模型的结构重复较高，可以继续使用LZ77压缩以达到更优秀的压缩比。
对于超过限定误差边界的点称为 Unpredictable Data（不可预测点），以IEEE 754标准浮点存储格式存储在另外一个分离的结构中，利用Binary Representation Analysis执行进一步压缩。1）把所有的值映射到一个贴近零且更小的范围之内，即让所有的值减去范围内中值（med=(mini (ρ[i]) + maxi (ρ[i]))/2)），因为越接近零，为了满足规定精度所需要的mantissa就更少。 2）基于1+Exp(vi)+RQ MBits在规定错误区间（含义参考第三段第三节）截断mantissa。3）In particular, we perform the XOR operation for the consecutive normalized values and compress each by using a leading zero count followed by the remaining significant bits.

这一系列trick使得SZ在浮点有损压缩时错误范围限定在10^-4时压缩比可以达到5.4，解压不会超过制定错误范围，且解压较快O(N)。当然这是16年的数据，sz compressor是开源的，在我们内部集群上的压缩率还需要测试。缺点是因为经过多轮压缩，CPU消耗较大。

值得一提的是TDengine 2.4.0.10 及之后都支持其内部优化的SZ版本，公开数据来看在开启SZ压缩时写入性能降低20%左右。

Part2

VLDB2015的论文《A time-series compression technique and its application to the smart grid》描述了一种分片回归的技术（Piecewise regression techniques），其将时间序列划分为固定长度或可变长度的区间，并使用回归函数描述它们。
这种算法采用三种回归函数，分别为：

constant functions (polynomials of degree zero)：PMR-Midrange《Capturing sensor-generated time series
with quality guarantees》
straight line functions (polynomials of first degree)：《 Approximations of one-dimensional dig ital signals under the l∞ norm》
polynomials of degree higher or equal than two：《Small-dimensional linear programming and convex hulls made easy》
以贪心的思路从零阶多项式开始尝试压缩多个点，直到不满足指定精度约束的时候执行下一阶多项式尝试压缩多个点，当达到最⾼次数的多项式并且它不能再以请求的精度逼近时，然后选择实现最⾼压缩⽐的多项式。通过保存其开始和结束位置以及多项式的系数来压缩相应的段，然后从下⼀段开始重新开始。

这乍上去和SZ算法非常像，因为SZ也是使用三种曲线测定函数，但是三种测定函数的输入参数是固定的，即1，2，3个参数，对于不满足可误差边界的点集，放入存储不可预测点的结构，在其中在规定误差边界内截断IEEE 754的mantissa，并对结果继续执行压缩。

这两篇论文其实光从理论很难分辨出谁优谁劣，因为两者都无法做到理论最优，所以论文中给出的压缩比作用并不是很大，主要能不能上生产还是看实现，这篇文章中虽然声称自己在HANA中实现了这种压缩算法，但却没有开源，我也没有搜到相关资料，而SZ已经是非常成熟的开源库了，所以仅仅看两者我肯定是选择SZ的。

Part3

ICDE21的论文《Optimizing Error-Bounded Lossy Compression for Scientific Data by Dynamic Spline Interpolation》描述了一种用于SZ预测阶段基于Spline Interpolation的预测器，也是SZ3的最大功能亮点。其最主要解决的问题是在SZ2.X中对于高维度数据进行压缩时，如果指定了较高的误差界限，虽然压缩率提高，但是精度下降非常明显，导致图像失真；其次当误差边界降低时，压缩数据时系数开销会显著提升；这两点主要是因为线性回归下使用相邻的点来预测已经足够“精确”。

所以这篇文章解决的问题可以用一句话概述：The fundamental idea is to develop a dynamic multidimensional spline interpolation-based predictor to replace the linearregression-based predictor such that the coefficient overhead can be completely eliminated while still keeping a fairly high prediction accuracy.

spline法和线性回归有本质的不同；spline是根据已知的数据点重建新的数据点，试图建立一条穿过所有已知数据点的曲线；而后者是根据特定的数学公式寻求一条最接近已知数据点的曲线。 Spline interpolation是一种特殊的多项式Spline，试图通过找到尽可能低的多项式且找到穿过所有点。文章还提到在相对不光滑的数据集中Spline interpolation的准确性不如 Lorenzo predictor，所以采用均匀抽样3%的方法选择使用哪一个预测器。

文章在推导的时候举了一个一维Spline的例子，其中需要保留所有偶数的点，我不清楚这对于压缩率是否会有影响。这篇文章对于压缩数据时系数开销的优化我并不关心，我主要看到的是在指定错误区间内SZ3的错误精度更为优秀，但是一维压缩率是我担心的点。

Part other

SZAuto的文章后续补充

总结

科学家和工程师，我大抵只能，也乐于成为后者。

参考：

Fast Error-bounded Lossy HPC Data Compression with SZ
A time-series compression technique and its application to the smart grid
Optimizing Error-Bounded Lossy Compression for Scientific Data by Dynamic Spline Interpolation