时间格：支持交互式可视分析大规模时间序列的数据结构（Time Lattice: A Data Structure for the ...

物联网设备的广泛使用生成了大量的时间序列数据，通常会有几十至几千的传感器同时生成时间序列。交互式的可视化框架在分析这些数据时非常重要。进行分析时需要复杂的查询，包括在不同时间分辨率下对时间序列数据的取值进行限制，进行聚集等。

使用可视化进行分析时需要考虑交互速度的问题：用户动态增加查询条件，系统需要提供低延迟的查询，使用户能流畅交互，以避免高延迟的查询会打断思路、导致用户难以进行观察和提出假设。

目前处理大规模时间序列数据的方法，主要包括使用时间序列数据库和数据立方体 (Datacube)。前者虽然内存占用小，也支持数据更新，但是难以在交互所允许的时间内完成查询。数据立方体处理查询的速度很快，但是一般占用内存比较大，一些对存储进行优化的数据立方体结构难以快速更新数据，使得它们不能应对大规模流式数据的场景。

数据立方体（Data Cube）

在联机分析处理（OLAP）中，用户的查询可以表示为：

Select data where constraints C     groupby dimemsions D， 其中C是每个维度上的限制的集合，D是进行聚集的集合。

数据立方体通过对高维数据的维度取值进行聚合，可以加速OLAP查询，例如对包含省份、季度的销售额表格数据，数据立方体中的聚合维度组合包括{省份，季度}，{省份}，{季度}，∅。当对省份和季度这2个维度进行聚合时，可以得到下图所示的2维立方体 (cuboids)：

对省份和季度进行聚合的2维立方体

在对时间序列数据的OLAP分析中，一般形式的查询语句为：

Select time series between t 1 and t 2     where constraints C     groupby resolutions G . 

这里， t1 和 t2 指定时间范围 ，C 是所有限制条件的集合， G 指定进行聚集的时间粒度集合。这里的时间粒度集合G等同于一般OLAP查询中的维度集合。

对包含月、天、小时的时间粒度集合D，数据立方体中的聚合维度组合和部分立方体如下图所示：

对月、天、小时，可能的聚合维度组合

时间格（Time Lattice）

与通常的OLAP查询不同的是，在时间序列OLAP查询中，聚合维度为时间粒度，存在内在的层次结构关系。利用这种关系，可以只物化部分立方体，在查询过程中，在线快速计算。根据这种想法，在[1]中，作者们提出了数据结构Time Lattice，以使得

• 查询速度满足交互的需求
• 快速更新新数据，满足实时交互
• 内存占用小

根据时间粒度内在的层次关系，在其上定义偏序关系：i ≺ j ⇔ j 可以划分 i. 例如，分钟 ≺ 小时。在偏序关系的哈斯图中，ij之间有有向边的充要条件是i ≺ j，并且不存在其它粒度k使得i ≺ k，k ≺ j。在时间序列OLAP查询中，常见的时间粒度包括秒，分钟，小时，周的第几天，月的第几天，周，月，年。它们的哈斯图如下所示：

哈斯图

在哈斯图中，寻找最长的路径，比如秒→分钟→小时→月中的天→月→年，那么需要物化的立方体的聚合维度组合为{{年，月，月中的天，小时，分钟，秒}, {年，月，月中的天，小时，分钟}, {年，月，月中的天，小时}, {年，月，月中的天}, {年，月}, {年}, ∅}。如果还存在没有被覆盖的时间粒度，则继续寻找最长路径，物化立方体。可以证明，每条最大路径上物化的立方体所需存储空间的大小与原始时间序列大小基本相同，由于一般只有2条最大路径，time lattice所需的额外存储空间较小。

存储Time Lattice时，每个时间粒度对应一个一维数组，按照时间顺序存放，数据空缺时使用默认值代替，因此也可以通过时间进行隐式索引。对于时间粒度i的数组中的一个单元，可以容易计算出更粗粒度i’下的单元位置，也可以计算出更细粒度i”下的单元范围。可以认为，不同时间粒度的数组按照哈斯图组成了层次结构，因为按照时间顺序存储，层次之间隐式连接。

Time Lattice存储

进行OLAP查询时，从最粗的粒度出发，定位到该粒度下的单元，如果用户的查询比当前粒度更细，则进入下一层更细的时间粒度，定位对应单元；否则返回当前单元的聚合值。

在流式数据的场景下（假设时间粒度为秒），进行更新的方法为：首先在秒的粒度上增加该数据；假设已经在时间粒度i上完成更新，在哈斯图上的下一个时间粒度j上的更新方法是，如果j上还没有对应的单元，则在数组尾部增加该单元，值与当前值相同；否则进行更新，在原有值基础上增加新数据的值。如果每k秒进行更新，且k远大于时间粒度数目d，则每次更新的平均时间复杂度为O(1)。

Time Lattice支持一些扩展：

对于时间序列不连续的情况，当不连续的情况少时，可以使用默认值填补空缺值，否则可以离散地存储该结构。

对于使用另一个时间序列的值作为限制条件进行联合查询的情况，可以在第一个时间序列的每个单元中存储第二个时间序列取值的直方图。

存储直方图应对联合查询。

此外，用户可以自定义时间粒度，以满足现实场景下对于时间范围的查询。

用户可以自定义时间粒度。

实验

在实验部分，作者们使用秒粒度的生成的时间序列进行测试。使用以下4种查询：

实验中的4个查询

最后实验结果显示，Time Lattice占用空间与原始时间序列近似相同，查询时间与时间步长短线性相关，平均更新时间约为常数。

Time Lattice与原始数据占用内存大小对比。

查询时间与数据量大小关系图

Time Lattice更新时间

与Nanocubes、原始的pandas实现以及3个先进的时间序列数据库的实验结果相比，该方法的内存占用最少。除了查询Q3以外的查询时间都最短。Nanocubes的Q3查询最快，因为这个查询的结果在Nanocubes已有物化的立方体。

Time Lattice与先进存储技术在空间占用和查询速度上的对比图

此外，作者们还在现实的噪声传感器数据集上验证了该数据结构的有效性。

总结

该论文作者提出了针对大规模时序数据的数据结构Time Lattice，只需占用较少的内存，可以提供快速的OLAP查询和流式数据场景下的实时更新。

参考文献

[1] Miranda, F., et al. “Time Lattice: A Data Structure for the Interactive Visual Analysis of Large Time Series”, Computer Graphics Forum, 2018, 37(3), 23-35.