压缩算法的调研
因毕业论文第二个研究点是压缩算法，所以最近展开一些调研：
引言
目前监控业务中绝大多数数据仍旧是浮点，对于浮点数据而言，其实是可以接受些许的损失的，所以使用有损压缩算法可以极大的提高压缩比。所以对近些年来的有损压缩研究做一些调研，挑选了些最有可能进行工业落地的论文进行梳理。
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的错误精度更为优秀，但是一维压缩率是我担心的点。
Part4
这篇文章我大概过了一遍，我觉得这篇文章对于没有了解过SZ代码的人来说比较不友好，在参数预测阶段根本不知道什么意思。文章思路大体上分为三个步骤：
基于采样预测数据的压缩比率，但是具体方法在另外一篇文章中。文章提到 Accurately estimating the compression quality based on the sam-pled dataset is critical to selecting the best-fit parameter settings and predictors at runtime. 但是我不太明白这句话，为什么基于采样对于参数预测很重要？
离线的与在线的参数预测。离线就是用一堆参数组合，每一个参数算出一组优秀值，对于每个字段，首先确定最佳压缩比，然后收集压缩比大于95%×best_rato的参数设置。在为每个字段收集了相对较好的参数组合后，我们可以选择任何一个选定的参数组合，这可以实现至少95%的最高压缩率。然后统计每个个体参数的优秀候选值；在线预测是在优秀值中进行多次迭代选择最优的压缩率。
SECOND-ORDER DATA PREDICTION 没看
总体来看比较学术，具体效果还是实际测试一下吧。
参考：
《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》
《Significantly Improving Lossy Compression for HPC Datasetswith Second-Order Prediction and Parameter Optimization》