1 基本思想
将原始时序数据转为频域数据,只保留部分能量较大的频域分量,以实现有损编码。
2 存储结构
- N:数据长度
- M:保留的频域分量个数
- 2^β:value的量化级别(离散粒度)
- id[i]:保留的频域分量索引
- s[i]:保留的频域分量值的符号
- v[i]:保留的频域分量值的绝对值
- v[i]':|v[i]|-min{|v|}
3 编码方案
3.1 离散余弦变换:
根据预先设定的blockSize,将原始时序数据顺序划分为若干个block(最后一个block的长度可能小于blockSize)。
对每一个block都进行离散余弦变换DCT,得到一系列频域分量,每一个频域分量可以表示为索引和值两部分。在后续保留分量时,按照能量(值的平方)从高到低。
3.2 自适应量化:
由于频域分量的值是一个实数,在存储时需要量化(离散)为整数进行存储。因此,整个编码过程存在两种误差:
- 系统误差:由于舍弃低能量频域分量导致的误差;
- 量化误差:由于量化和舍入导致的误差。
根据预先指定的信噪比,总体误差是固定的。显然,如果量化等级(离散粒度)很小,每一个值量化的结果都会很大,会导致较大的空间占用;如果量化等级很大,那么在总体误差固定的情况下,会保留更多的频域分量以减小系统误差,也会导致较大的空间占用。随着量化等级的增大,总体的空间占用先减少,后增加,需要自适应的寻找合适的量化等级。
实践中,量化等级固定为2^β,β是一个步长为1的整数。先将β设置为一个较小的值,再逐步增大,直到空间占用不再下降。
3.3 索引编码:
索引序列采用分组编码的方式。每8个一组,先记录它们的最大有效位宽作为编码位宽,再将这些索引都按照同样的位宽编码。
3.4 值编码:
值序列在忽略符号的情况下,是严格降序排列的。因此,可以将前一个值的有效位宽作为后一个值的编码位宽。
4 解码方案
4.1 索引解码:
4.2 值解码:
4.3 离散余弦逆变换:
从索引序列和值序列中恢复部分频域分量,剩余分量填充为0,进行离散余弦逆变换IDCT,转为时域数据。
5 实验评估
对一组长度为170,000的真实气温数据,使用不同的方式进行编码压缩,结果如下:
编码压缩方式 | 写入开销(s) | 查询开销(s) | 空间占用(byte) | 精度损失(RMSE) |
---|---|---|---|---|
PLAIN+UNCOMPRESSED | 2.6 | 0.11 | 1,398,024 | 0 |
TS_2DIFF+GZIP | 1.9 | 0.18 | 144,099 | 0 |
TS_2DIFF+GZIP+SDT(COMPDEV=0.25) | 2.0 | 0.036 | 36,225 | 0.219 |
FREQ(SNR=40,BLOCKSIZE=1024)+UNCOMPRESSED | 2.2 | 0.11 | 50,303 | 0.206 |
FREQ(SNR=40,BLOCKSIZE=1024)+GZIP | 2.1 | 0.11 | 25,663 | 0.206 |
- TS_2DIFF+GZIP是压缩比最大的无损编码压缩方式,它的空间占用远远低于PLAIN+UNCOMPRESSED,但有损编码压缩可以进一步大幅减少空间;
- 在TS_2DIFF+GZIP的基础上,可以继续应用有损的SDT压缩方法。由于该方法直接删除了大量数据点,而在查询时又没有通过插值进行恢复,因此查询开销远低于其余方法;
- FREQ+GZIP可以取得最佳的空间压缩效果,在精度损失与SDT方法相当的情况下,可以节约30%的空间占用。