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的真实气温数据，使用不同的方式进行编码压缩，结果如下：

• TS_2DIFF+GZIP是压缩比最大的无损编码压缩方式，它的空间占用远远低于PLAIN+UNCOMPRESSED，但有损编码压缩可以进一步大幅减少空间；
• 在TS_2DIFF+GZIP的基础上，可以继续应用有损的SDT压缩方法。由于该方法直接删除了大量数据点，而在查询时又没有通过插值进行恢复，因此查询开销远低于其余方法；
• FREQ+GZIP可以取得最佳的空间压缩效果，在精度损失与SDT方法相当的情况下，可以节约30%的空间占用。