Hashedcubes: 对于大数据的简洁,低存耗,实时的可视探索 (Hashedcubes: Simple, Low Memory, Real-Time Visual Exploration of Big Data)

交互式可视化系统的设计者现在正面对着大规模、多维度的数据的挑战。这一工作为以下问题提供了一个肯定的答案:是否存在一个简单的数据结构为一个更成熟的索引提供更丰富的性能,同时使空间消耗相对较低、执行方法较为简便?

为了理解这篇工作的内容,首先介绍一些基础的知识。第一,当我们改变一个数组的先后顺序时,这个数组的大小并不会改变,所以我们可以自由的选择数组的顺序。第二,假设一个数组A,所有元素A[i] (b <= i < e) 组成一个子数组S,将这个子数组表示为一个pivot: (b, e). 用这种方式代表一个分隔可以使我们快速的跳过数组中一些大的间隔,同时保持了简洁和紧凑。第三,我们可以把每个间隔代表的子数组当做一个数组,通过这样,我们可以将它进一步分隔为子数组。

让我们先对这篇工作提出的Hashedcubes有一个初步的印象。首先,Hashedcubes加速了交互式可视化探索的请求过程,例如热图、时序图、柱状图和散点图;并且支持空间、类别和时间这三个维度上的刷选和联接。Hashedcubes平衡了低空间消耗和快速处理时间和执行简洁程度这三方面因素。

如图一显示了3个以Hashedcubes为支撑的可视化例子。最左面的图显示了2011.11至2012.06之间美国tweets情况的概览;中间的图显示了2014.01至2015.06之间,NYC Green出租车的上车地点;最右的图可视化了450万个Brightkite登记信息的不同的方面。

图片1 以Hashedcubes为支撑的三个例子

 

现在从一个更正式的方面来介绍Hashedcubes,Hashedcubes是一个数据结构,它能够快速的帮助交互式可视化查询大规模、多维度、时空的数据集。Hashedcubes支持空间查询,类别查询和时间查询。

为了建立Hashedcubes,要求数据的一个维度顺序,例如首先是空间维度,然后是类别维度,最后是时间维度。对于数据的每个分隔都用pivot来导引,每个分隔对于不同的维度都有不同的解释。

对于建立数据结构的算法,一个输入数组全部属于一个相同的分隔,用一个pivot代表。第一个维度接收一个根pivot作为它的输入。每个分隔都会执行排序来组织元素。

图片2 建立Hashedcubes的算法示例

图2是一个建立Hashedcubes的算法示例。输入数据包含了10个点,运用[[Latitude, Longitude], [Device], [Time]]的模式。在图2(b)的第一步中,数组根据四叉树的第一层属性: 空间被重新排序,并分成3个分隔分别为0、2、3三个象限(包含点的象限)。建立了3个pivot([0-5], [6-7], [8-9]))来划分三个分隔。在第二步中,数组根据四叉树的第一层属性: 类别被重新排序,在这一步中,只有第一个象限被划分,因此只有[0-5]这个分隔被更新为两个新pivot[0-2]和[3-5]. 步骤3和步骤4和前面是相似的,只是分别使用类别和时间维度来进一步划分数据。

图2c的上方的图片比较了输入数组和最终获得的分隔排序后的数组。图2c的下方的图片展示了通过每一步创建出来的并通过Hashedcubes存储的pivot的列表。

与其他数据立方体不同的是,Hashedcubes不会跨越所有可能的维度集合提前计算。图3是一个对于计算的Nanocubes和Hashedcubes之间的对比。Nanocubes提前计算的大多数的集合,这样就导致了更少的查询时间但是更多的存储空间消耗。Hashedcubes相反消耗了更少的空间。

图片3 Nanocubes和Hashedcubes对比示例

 

  • 空间维度

空间维度被表示为一个四叉树的形式。地理空间的数据经常会用一个分等级的数据结构表示,并且空间会被递归的分为4个地区。每个四叉树节点为一个划分该象限中物体的pivot。每个四叉树有一个最小叶子尺寸,输出的大小直接取决于输入的大小。叶子的大小是一个与存储空间和Hashedcubes表现有关的重要因素。

考虑一个关于通话的数据集,包含了两个地理位置,一个是打电话的人所在的位置,一个是接收的人所在的位置。如图4所示,在四叉树的每一级,记录通过当前层级的空间属性被分割,通过属性交替的分隔数据。

图片4 通过成对地理位置交替分隔数据

  • 时间维度

如图5所示,Hashedcubes中每个pivot代表一个间隔,每个时间段被代表为一个时间戳pivot数组。每个黑色的圆代表一个被标记为特定间隔的记录。

图片5 时间维度的表示方法

 

对于这项工作,还有三个值得讨论的方面:

第一,交换使数据排序的维度的顺序会影响对于特定查询的空间消耗和执行时间。这种交易可以为数据管理者选择分布提供帮助。

第二,大型可视化系统例如imMens、Nanocubes和Hashedcubes使用的数据集合会丢失掉一些原始数据的信息。而Hashedcubes根本的概念允许结合外部的数据。

第三,叶子节点的尺寸与可视精度的平衡。空间维度采用最小四叉树叶子尺寸来平衡运行时间、空间消耗和可视精度。

图片6 基于Hashedcubes的热图可视化

图6显示了不同的基于Hashedcubes的热图可视化。叶子尺寸从32变化到8,影响了运行时间、空间消耗和可视精度。6(a)的pivot被表示为长方形,(b)和(c)用圆表示聚集地区的中心。

[1] Pahins C A L, Stephens S A, Scheidegger C, et al. Hashedcubes: Simple, low memory, real-time visual exploration of big data[J]. IEEE transactions on visualization and computer graphics, 2017, 23(1): 671-680.

评论关闭。