TOPKUBE: 一种支持实时时空数据探索的序敏感数据立方体 (TOPKUBE: A Rank-Aware Data Cube for Real-Time Exploration of Spatiotemporal Data)

针对时空数据的查询中一类关于前k相关客体的查询,该论文[1]提出了能达到交互性要求的数据结构及相应算法,解决了相关工作没有关注此类查询或者没有关注可交互性的问题。

背景

排序是人们日常生活中认识世界的重要方式。随着网络上用户自创内容的普遍,通过对这些网络内容进行排序,可以有效地认识不同时空下的趋势和热点。同时,随着GPS设备的普及,网络内容中往往会包含地理信息,如何处理时空数据的排序问题变得重要。

同时,由于交互式探索要求系统具有低时延,这对于处理网络上大规模的数据提出了挑战。最近的一些工作,关注提升已有方法的效率,但是这些方法并没有关注查询前k个最相关的结果,而该论文针对这一问题,提出了解决方案。

数据立方体

实际场景的查询中,往往需要按照在若干维度上的一定取值下,所包含的数据项的聚合值来进行排序。数据立方体则是应对这一场景的常用数据结构。

数据立方体的概念首先在数据库领域中被提出,随后被引入到可视化领域中。它是指,对于若干维度,每个维度各取一个值,对各个维度的值都与指定的值相同的数据项组成了一个集合,返回关于集合中数据记录的聚合值,比如,和、数量、最大值、最小值、平均值等。数据立方体预先计算并存储所有可能的维度值组合的聚合值。

Nanocubes

Nanocubes[2]是针对一类具有时空属性和一些类别型属性的数据,对数据立方体进行的表示或物化。同时,Nanocubes还针对交互性,对速度进行了优化。

Nanocubes是一种稀疏的基于指针的数据结构,如图所示,是Nanocubes的一个样例。

Nanocubes示意图

Nanocubes可以视为对树结构,使用指针合并具有相同叶节点的路径。Nanocubes按照维度进行分层,每个维度可以有内部的层次结构。如上图,黑色连线代表维度内部不同层次的连接,而蓝色连线代表跨越维度的连接。每一个内部节点对应于维度的一个取值,称为(bin)。从根到叶节点的路径视为在经过的维度选取了一组箱,这些不同维度选取的箱的组合称为箱乘积(product-bin)。叶节点存储箱乘积对应的数据集合的聚合值。

Nanocubes通过牺牲一定的灵活性(预先定义可以支持的查询),来换取可交互性(较短的反应时间)。

尽管随着维度数的增加,使用内存内数据立方体的空间需求会指数增加,但是存在一些实际场景,这种方法可以驱动交互的探索,否则将会需要难以承受的大量空间和时间,因此内存内数据立方体依然有使用价值。本文提出的TOPKUBE就是对Nanocubes的一种扩展。

TOPKUBE

TOPKUBE中定义进行排序的维度为特殊维度,称为(key)。键对应的是用户希望排序的客体,比如球员姓名、文章名、标签等。实际场景中存在键数量大的情形,有时需要扫描上百万的记录才能确定前k个键,造成交互时的较大延迟,阻碍流畅的交互式探索,而TOPKUBE就是针对这一类查询的一种解决方案,它高效地返回键在任意箱乘积选择下的前k个结果。一个TOPKUBE结构只支持同一个键的选择,不同的键需要构建新的TOPKUBE。

TOPKUBE示意图

TOPKUBE的数据结构类似Nanocubes,主要的不同是TOPKUBE编码了键的排序信息。具体地,在Nanocubes的叶节点(对应一个或多个箱乘积)中,附加了3个数组:q、v、σ,长度与该箱乘积中包含的不同键的数量相等,以及一个聚合值:Σv。

  • q按照键本身的顺序存储键,例如对字符串,可采取字典序进行排序;
  • v是q中对应下标处键的测量值;
  • σ是按照测量值从大到小排序的键;
  • Σv是原有Nanocubes中存储的测量值,是数组v的元素之和,以支持Nanocubes原本支持的聚合值的查询。

实际的查询可能导致需要对多个箱乘积中的键的测量值之和进行排序,箱乘积的数量可以从数十到数千不等,因此这个问题并不同只有一个箱乘积时那么容易。

该论文作者称这一问题为从一些排序的数组中选取和前k大的元素 (Top-k from Ranked Lists, TKR)。即,给定一组数组,数组的键对应客体,值对应一种满足可加性的测量值,要求返回前k个键,也即前k个客体,要求这些键在所有数组中的值之和最大。

针对这一问题,该论文提出三种算法。

为讨论时间复杂度,假设

  • m是箱乘积的个数
  • N是m个箱乘积中所有键的个数
  • n是m个箱乘积中不同键的个数
  • k对应所要求的前k相关键

算法1:扫描算法 (Sweep Algorithm)

这一算法没有考虑排序信息,因此对于Nanocubes也适用。

算法要求维护2个最小堆。第一个堆存储每一个箱乘积中的当前最小键和对应的值。第二个堆维护前k相关的键,维护该堆的时间复杂度为O(nlogk)。以下主要介绍算法如何维护和使用第一个堆。

初始化第一个最小堆,由于数组q按照键顺序进行排序,扫描每个箱乘积,取对应q数组的第一个元素(即是该箱乘积中的最小键)及其值以及该元素在数组中的下标,插入堆中。堆按照键本身的顺序排序,时间复杂度O(mlogm)。

初始化和sum为0,当前键为空。每次取出该堆的首元素(键、值、数组q中的下标),若该元素的键与当前键相同,则对应的值与当前sum相加;否则向第二个最小堆插入当前键与sum,设置当前键为该元素的键、sum为该元素的值。若该元素所在数组q中存在下一个元素,则向第一个堆中插入下一个元素,由于记录了在数组q中的下标,因此访问下一个元素只需要O(1)的时间。

这样的算法使得,第一个堆的大小最大为m,且从第一个堆中取出的元素,完全按照键的顺序,从小到大进行排列,因此对每一个键的值进行求和得以简化。这样时间复杂度是O(Nlogm)。故算法总时间复杂度为O(nlogk+mlogm+Nlogm)。

与之对比的是,如果对每一个元素,在m个数组中以二分法找到相同键的元素从而计算键的值之和,需要O(n*m*logn+nlogk)。

算法2:阈值算法 (Threshold Algorithm)

算法2是计算机领域的常见算法,使用σ数组中按照值进行排序的信息,希望能首先找值最可能前k大的元素,减少查找元素的次数。

具体地,维护一个队列和一个大小为k的最小堆,同算法1,堆处理的时间为O(nlogk)。

队列的操作如下,队列的第i个元素对应第i个箱乘积中,当前最小值对应的元素。由σ数组,使得获取的复杂度为O(1)。

循环地进行对队列的遍历,直到每个箱乘积中的所有元素已经访问或者队列内元素的和大于最小堆的最小值且堆中已有k个元素时,退出循环。

访问队列的某一个元素时,如果该元素的键尚未计算和,则访问m个箱乘积,查找该键对应的值,求和,复杂度O(mlogn)。将和插入堆中,标记此键已被求和,否则不做计算。将箱乘积中按照值大小排序的下一个元素插入队列的该位置。重新计算队列元素之和,只需减去取出的键的值,加上新增键的值,为O(1)复杂度。

算法2的总时间复杂度为O(n*m*logn + nlogk)。

算法3:混合算法 (Hybrid Algorithm)

算法2在m个箱乘积包含相同的键时具有理论最优性,但是作者们发现在他们应用的实际场景中,这种假设不成立。箱乘积中的键往往稀疏,使得TA算法大部分情况下需要二分查找一个不存在的键,使得TA算法并未达到实际最优。作者们提出混合二者的算法,既能利用排序信息,提前退出遍历,又能减少浪费的查找。混合算法的想法是提高箱乘积中键的密度。

具体来说,混合算法将箱乘积按照键数从大到小排序,数量最多的箱乘积假设有n个键。

从键多到键少,遍历每个箱乘积,当估计密度值低于某一预设阈值θ时停止。长度较短的未被访问过的箱乘积,使用算法1,将k取为无穷大,聚合为一个箱乘积,与超过阈值的箱乘积作为算法2的输入,得到最终结果。

算法中的阈值θ控制TA算法的输入的list的密度层级。估计密度值是密度层级的上限,使得计算密度只需使用已经遍历的箱乘积的信息,以简化计算,同时又能与实际密度相关。

实验结果

该论文中使用了4个数据集:

  1. Wikipedia文章编辑历史数据集,大小112M,键是文章,数量3.0M;
  2. Flickr数据集,大小84M,键是标签,数量1.6M;
  3. GitHub项目数据集,大小58M,键是项目,数量1.5M;
  4. Microblogs的数据集,大小40M,键是主题标签,数量4.7M。

Wikipedia数据集的记录数最多,Microblogs数据集拥有最多的不同的关键词。

初步实验

该论文作者首先对四个数据集进行初步的实验,结果如图所示:

初步实验结果:左上角为Flickr数据集结果,左下角为Github数据集结果,右上角为Wikipedia数据集结果,右下角为Microblogs数据集结果。

该论文作者们选取Microblogs数据集的100条时空查询,查询前32相关的键,将三个算法以及PostGIS进行对比。PostGIS是处理此类问题的最热门的开源地理信息系统软件包,实验中以它的结果为基准,首先确认了作者们所提算法的正确性,并进行时间效率上的比较。比较结果如图所示:

Microblogs上100条包含时空信息的对前32相关的键的查询的时间效率的经验累计分布图。

从实验结果图中可以看出,该论文提出的三种算法的时间效率均优于PostGIS,并且θ=0.25的混合算法时间花费最小。

TOPKUBE基准

作者们进行了系统的测试,并公开了TOPKUBE基准,以供后续更多研究者使用,网址为github.com/laurolins/topkube_benchmark

具体地,论文对4种数据集,各提出了250个查询,共1000个查询。这些查询在键的数量、排序list的数量、记录数量和密度上各有不同。

作者们将混合算法的阈值选取为,从0.05到0.95,每0.05的间隔设置一个阈值。同时测试了阈值算法(相当于θ=0)和扫描算法(相当于θ=1),因此共有21个算法。对于k值,取k=5,10,20,40,80,160,320共7个值。

实验发现,阈值θ影响算法运行时间。当θ=0.20时,θ位于0.15与0.45之间时,算法运行时间较少。70%的问题的查询时间低于100ms而扫描算法则只有40%查询时间低于100ms。

TOPKUBE基准中的各算法延迟分布

作者们还测试了算法相对于扫描算法的加速比、k的大小、键的数量排序数组的数量对加速比的影响,发现:

(1)当θ=0.25时,k≤100会使得算法依然能在交互性要求的时间内返回查询结果,当超过100时,则适合使用扫描算法。

阈值算法和混合算法相对于扫描算法的加速比分布图,蓝色代表加速比大于1,红色代表加速比小于1。

(2)键数量越多,则θ=0.25的混合算法加速比越高,这符合作者的预期:查询越困难,则混合算法的加速比越高。

阈值为0.25,加速比相对于键的累积分布图

(3)与键的数量相反,排序数组的数量越多,则加速比越小。该论文的作者们认为更多的排序数组使得混合算法中进行扫描算法的数组增多,导致运行时间增加。

阈值为0.25,加速比相对于排序数组的累积分布图

总结

针对时空数据查询中的一类问题,前k相关客体的查询,现有方法不能很好满足交互性的要求。该论文通过扩展Nanocubes[2],提升了这一任务的效率,使得交互式查询成为可能。

同时该论文作者指出了可能的改进之处:

  1. 不同条件下,达到最优的θ值不同,如何进行自适应的θ选取是接下来可以进行改进之处。
  2. 该论文主要关注时间效率的提升,因此对于空间存储,没有进行特别的优化,但是作者们指出,一些优化可以使得算法的空间效率有所提升。

参考文献

[1] F. Miranda, L. Lins, J. T. Klosowski, and C. T. Silva, “TOPKUBE: A Rank-Aware Data Cube for Real-Time Exploration of Spatiotemporal Data,” IEEE Trans. Vis. Comput. Graphics, Feb 2017.

[2] L. Lins, J. T. Klosowski, and C. Scheidegger, “Nanocubes for real-time exploration of spatiotemporal datasets,” IEEE Trans. Vis. Comput. Graphics, vol. 19, no. 12, pp. 2456–2465, Dec 2013.

评论关闭。