SmartCube: 时空数据实时可视化的自适应数据管理框架

实时性对可视化系统探索过程至关重要,一定时间的延迟会对用户的理解产生较大的影响【2】。而随着计算能力的上升,现实生活中的数据规模也在极速膨胀。如,社交媒体产生的信息数以亿计。传统的方法已经难以支持如此巨大规模数据的实时查询。对原始数据重新组织是支持低延迟的交互查询的必要条件。北京大学可视化与可视分析实验室针对大规模时空数据自适应组织方式的文章 “SmartCube: An Adaptive Data Management Architecture for the Real-Time Visualization of Spatiotemporal Datasets” 【1】已被可视化领域顶级会议 IEEE VIS 2019 接收,并被领域顶级期刊 IEEE Transactions on Visualization and Computer Graphics (IEEE TVCG) 收录。

时空数据在数据分析中占据重要的地位。无论是交通数据、还是社交媒体数据,都涉及到对时间维度和空间维度的管理。针对一个时空数据的某一区域、某一时间阶段的聚集值 (包括单个值、数组、或者时间序列) 的查询可以支持通用的时空数据可视化,如地图上的刷选操作,绘制热力图、时序图等。这些查询的基本单元是 聚集值 ,聚集值是原始数据中一个子集按照某个聚集函数得到的数值,如求和、平均、计数、等。

针对聚集值的数据结构中,预先计算并存储是常见的方式。其中,数据方块(Data Cube)是一种有效的解决方式【3】。数据立方体计算了在所有维度组合下的聚集值。在一种维度组合下的所有的聚集值的集合被称为 数据立方体 (Cuboid),如图 1 所示,中间部分是一个具有country,phone,和 year 三个维度的数据方块,其中共有2的3次方个数据立方体。左右两侧分别是两个数据立方体实际存储的内容,他们分别表示了各自的维度组合中的所有可能的组合。数据方块可以直接返回查询的结果。然而,数据立方体将会占用巨大的内存。部分算法在数据立方体之上做出了改进。一种方式是只存储部分的数据立方体,如时间方格(TimeLattice)【4】只存储了在时间上具有时序关系的部分数据立方体。另一种方式是考虑在数据立方体之间共享内存。最经典的是Nanocube【5】,他在一个树状结构中尽最大程度共享内存。但是这些方法还是有一些局限性,如Nanocube仍然会因为维度数目过多而导致内存占用过多。而time lattice 节省数据立方体的方式也没有在时间以外的维度的普适性。

图1 数据方块(data cube)和数据立方体(cuboid)

SmartCube 是一种自适应地变更其中的数据立方体。这一想法的基本由来是,用户或者可视化系统对整个数据方块的访问是不均匀的。有些数据立方体是被频繁访问的,而有些数据立方体甚至从不会被访问。但是在建立数据结构的时候,哪些数据立方体会被查询是未知的。SmartCube可以针对用户的查询的情况,动态地选择那些数据立方体被实现、哪些数据立方体被删除。同时,在一些情况下,相对应的数据立方体没有被实现,SmartCube有相应的算法给定查询去向下钻取(Drill down)到更细的数据立方体并向上求和。SmartCube 构建了以数据立方体为单位可以动态更新(增加/删除数据立方体)的算法,如图 2 所示。

图2 SmartCube 的动态结构

有了计算数据立方体的更新算法。在查询到来之时,SmartCube会记录下查询,并用以评估需要增加的“有用的”数据立方体或者需要删除的“无用的”数据立方体。这些查询被当作将来一段时间内的查询。而新的数据立方体在加入之后,如果查询可以节省更多的时间,那么这个数据立方体就会被加入。反之亦然。

同时,SmartCube 也构建了在数据立方体结构动态变化的过程中始终能够以正确、最快速的方式返回查询结果的算法。图3 以空间维度为示例来展示数据结构中不同的数据立方体对查询的影响。在(b)中,存在一个数据立方体({S1, S2}),o2和o3需要被向下钻取再聚集起来,在(c) 中,由于存储了更多的数据立方体({S1, S2}, {S1, all}),可以直接从{S1, all}获得o2和o3的聚集值。该查询算法会提前预估需要最少的向下钻取的数据立方体。

图3 不同的动态结构和相应的查询

SmartCube 在不同的数据集中测试了相关性能,在大规模数据集,如具有五千万记录的微博数据和在五百万数据的BrightKite 地点打卡数据中,该算法可以很快稳定在低延时、低内存占用的内存。在这方面的内存占用若干倍小于Nanocube,并且取得了相匹配的时间复杂度。在只有时间序列的查询中,SmartCube也相较于Timelattice,Nanocube 取得了无论是时间还是空间上的优势。更多细节请关注论文原文【1】。

参考文献

【1】Can Liu, Cong Wu, Hanning Shao, and Xiaoru Yuan. “SmartCube: An Adaptive Data Management Architecture for the Real-Time Visualization of Spatiotemporal Datasets.” IEEE Transactions on Visualization and Computer Graphics (InfoVis ’19), Accepted .

【2】Zhicheng Liu and Jeffrey Heer. “The effects of interactive latency on exploratory visual analysis.” IEEE Transactions on Visualization and Computer Graphics 20.12 (2014): 2122-2131.

【3】Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, and Hamid Pirahesh. “Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals.” Data mining and knowledge discovery 1.1 (1997): 29-53.

【4】F. Miranda, M. Lage, H. Doraiswamy, C. Mydlarz, J. Salamon, Y. Lockerman, J. Freire, and C. T. Silva. Time lattice: A data structure for the interactive visual analysis of large time series. Computer Graphics Forum, 37(3):23–35, 2018.

【5】L. Lins, J. T. Klosowski, and C. Scheidegger. Nanocubes for real-time exploration of spatiotemporal datasets. IEEE Transactions on Visualization and Computer Graphics, 19(12):2456–2465, 2013.

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章