面向空间在线分析的并行近似聚集查询*

2018-10-12申金鑫

计算机与生活 2018年10期

申金鑫，吴烨，陈荦，景宁

国防科技大学电子科学学院，长沙 410073

1 引言

信息化世界里，人人都是移动的数据“生产者”。随着基于位置的服务普及以及各类移动定位设备的增长，空间数据呈现出“爆炸式”增长，例如，OpenStreetMap全球点矢量数据集已有超过27亿条记录。为从日趋海量化的数据中获取有用信息，聚集查询[1]方法呈现出越来越重要的作用。当前很多空间在线应用需要的是一个聚集结果，而不是单个对象信息的集合。例如，查询北京市区某个立交桥区域在某一时刻的车流量，以便于检测交通拥堵，并不需要查询范围里的所有车辆具体的信息。

聚集查询具有数据密集和计算密集的特征，是一种耗时操作。空间索引是提升聚集查询速度的有效手段。R树是一种典型的二维空间索引，采用最小边界矩形对空间进行划分[2-5]。Ra*树在传统R树的基础上增加聚集信息，是最早的多维聚集结构，其目的在于有效处理窗口聚集查询[6]。之后，聚集R树（aggregation R-tree，aR树）在R树节点的最小外接矩形内标注了其所包含的所有对象的聚集值，在聚集计算时可直接引用该信息，不用对每个对象进行聚集计算[7]。随后，很多空间聚集索引技术不断深入发展[8-10]。

在线聚集应用中的需求可分为两类：一类要获取精确查询结果；另一类只需近似结果。对于后一种需求，以牺牲结果精度为代价来减少等待时间，但是要保证查询精度能够随着时间推移不断提升，且随用户需求而停止。就现有研究成果而言，对第一种需求还没有针对聚集索引的并行构建方法。对后一种需求，基于数据采样的近似聚集大多非针对空间数据；同时，返回近似结果时，也不能保证精确查询结果的速度。

最近，大数据处理架构飞速发展，为在线聚集查询性能的提升带来机遇和挑战。机遇源于其高效可扩展的特点；挑战就空间聚集查询而言，包括数据划分和任务分解两个普遍问题。在数据划分时，如何保持数据的空间邻近聚集特征，处理常见的数据倾斜和边界对象分配问题[11]。在任务分解时，如何分解数据分区，避免分区不均导致负载不均衡以及分区过多导致的大量初始化开销。

本文将精确查询和近似查询两种需求结合起来，在提升精确查询效率的同时，又能在精确结果返回前快速反馈近似查询结果。针对精确查询需求提出了基于Hilbert空间填充曲线划分的聚集网格R树（Hilbert partition based aggregation grid-R tree，HAGR树）。然后在此基础上提出了一种多层级采样聚集树（multi-layer sampling aggregation R-tree，MSAR树）。

本文的主要贡献如下：

（1）对Hilbert-aR树进行并行优化，在此基础上实现了HAGR树，通过Hilbert数据划分提高了索引搜索效率，建立全局网格索引提升了并行查询效率。

（2）基于金字塔和大数据随机采样思想，在并行HAGR树的基础上提出了MSAR树，通过概率查询的逐步求精方式进一步提升了聚集计算效率，并且能够实现良好的交互。

（3）在10亿规模真实数据集上，验证本文方法的有效性和正确性，能够返回给定置信度下的置信区间，实现渐进式聚集计算。

2 相关工作

当前，近似聚集方法可以分为预计算和在线聚集两类[12]。本文关注其中后一种方法。而在线聚集方法可进一步分为非索引的在线聚集方法[13-15]和基于索引的在线聚集方法[16-17]。

在非索引的在线聚集方法方面，在线聚集（online aggregation，OA）是一种在线近似聚集方法，不断从底层随机获取元组并统计，然后在3个准则基础上计算置信区间，直到结果满足用户的要求[13]。DBO数据库原型系统能实现近似聚集查询，很快返回一个推测结果，随时间推移，各种关系操作从互相通信中获取更多满足条件的元组，因而推测结果的精度也随之越来越高[14]。基于分块的近似聚集算法（partition-based approximate aggregation，PAA）是一种基于划分的近似聚集方法，对数据预先构建一个随机样本。在查询时，首先在预构建的样本中查询，如不能满足要求，再从与查询区域相交的各个分片集合中获取更多元组[15]。

在基于索引的在线聚集方面。MRA树是一种多粒度聚集树，该树的每个叶子节点与一个区域范围相关联，存储其孩子节点的聚集信息。在查询时，判断节点空间范围与查询范围的空间位置关系，以此来决定是否查询该节点的子节点。将该思想与四叉树（MRA四叉树）和R树（MRA-R树）结合，提供渐进的估计结果以及100%置信度的置信区间[16]。LS树和RS树这两种索引方式是专门针对空间和时空在线分析提出的，在查询过程中不断获取新的采样样本，采样实现了一种面向在线空间或时空分析的逐步求精的查询方式，能在任意置信度下反馈估计结果以及置信区间[17]。

以上方法往往在单机中进行，为提升聚集计算效率，一系列并行改进逐渐出现。基于MapReduce计算模型，能够在查询执行期间以顺序流传输数据，进而不断修正结果[18]。基于数据库和大规模分布式节点方法，可以设计采样创建和采样选择策略，以多层采样方式实现对给定的误差或是给定时间这两种查询模式[19]。这些方法都在大规模数据上取得了良好的效果，但是这些方法都不是专门针对空间数据而设计的。

在并行空间计算方面，基于MapReduce和Spark计算模型，已经有Hadoop-GIS[11]、SpatialHadoop[20]，以及GeoSpark[21-22]、SpatialSpark[23]、LocationSpark[24]、Simba[25]等系统，提供了格网、四叉树、R树等空间索引支持来加速空间查询等操作，其中大多系统支持R树的并行构建[11,20-21,24-25]，然而并不提供空间聚集索引的构建。

基于以上分析，现有的概率聚集方法很少应用于空间数据，且现有的空间分析系统并不支持聚集索引。因此，为了提升面向空间大规模数据的聚集分析，本文基于分布式内存计算架构Spark，针对在线聚集查询应用，提出了两种索引方式，HAGR树和MSAR树。其中，HAGR树支持快速时空精确聚集分析计算，MSAR树结合概率聚集查询，进一步增强了在线时空聚集查询的交互性。

3 问题描述

给定空间数据D，其中的元组可表示为K,V键值对的形式。其中K(K1,K2,…,Kd)表示元组的d维属性信息，例如，空间矢量数据中d=2。V(V1,V2,…,Vv)表示元组的值属性信息，对空间数据而言，V是包含各种空间属性信息的集合，例如：(Oid,Geometry,…,Geometry Type)等。

聚集查询可表示为F=fagg(op(V|Q⋂QR))。其中QR表示查询区域；fagg表示聚集函数，包含SUM、AVG、COUNT、MIN以及MAX等常见聚集函数操作；op表示属性操作，代表一般操作映射函数；Q是D的范围，则Q⋂QR表示相交区域。

对于在线近似聚集，仅当聚集结果来自随机采样中获得的元组，得到的结果才是有统计意义的估计结果。这一要求可以通过Heap Scans、Index Scans、Sampling from Indices方法保证，避免元组的属性值影响其检索的顺序[13]。满足上述条件基础上，近似聚集查询还需要其他衡量指标，包括置信区间CI，置信度p∈(0,1)，以及误差范围ε。误差范围即置信区间宽度，是对估计精度的度量。得到这些指标后，即可通过公式CI=为用户终止查询提供判断。

4 并行聚集查询索引

本文对aR树并行优化，与Hilbert编码的数据划分方法结合。在HAGR树构建过程中考虑数据划分和任务分解两个优化问题，处理了数据划分过程中常见的数据倾斜和边界对象问题，在查询中提供了一种基于空间关系判断的深度优先搜索（depth first search，DFS）方法。

4.1 HAGR树构建

HAGR树构建首要考虑是并行环境中高效构建，因而需要合理的数据划分和任务分解作支撑。为展示数据构成，因而又将D表示为D={di|i∈[1,N]}，d为单个元组，N为元组总数。

Hilbert编码划分方法。采用Hilbert编码的划分后，可以获得几乎近100%的空间利用率。因而，构建的Hilbert-R树的查询性能优于平方复杂度节点分裂的R树、R*树和Roussopoulos的批建立方法[26]。根据Faloutsos等[27]提出的Hilbert曲线编码生成算法，目标点的Hilbert编码值计算复杂度为，其中nh是空间层次划分次数，即该点所在网格行列中数较大值所对应的二进制位数。

并行计算中，网格索引能实现高效关系判定，以实现有效剪枝。因而，本文在结合网格和聚集R树索引后得到一种两级索引——HAGR树。其构建过程如图1所示，主要分为数据划分、数据排序、数据分解以及并行索引构建等4个步骤。

（2）在此基础上，按照Hc对数据集排序，实现空间聚集特性。

（4）以D1D2…Dk为基础并行构建Local Index，得到tree1tree2…treek。如图1右下角，tree中A1区域的聚集结果直接由子节点a1+a2+a3获得。之后，获取各个数据块的Mbb，更新Global Index，完成两级索引构建。

4.2 数据倾斜和边界对象处理

并行计算数据划分过程，数据倾斜和边界对象这两个问题不可避免。数据倾斜源于实际数据的空间维度分布不均，会影响计算效率。例如，同一个Hc可能对应了多条元组，这些元组空间上无序，无法增加聚集特性，且在后续任务分解中容易造成分解不均。边界对象源于网格划分方式，若处理不好可能导致查询结果错误。

数据倾斜处理。在HAGR树构建的第（1）步中，添加处理算法。对输入数据采样，减少后续处理计算I/O；然后统计每个T包含的数据量TNH，定义阈值参数Cmax，如果存在TNH>Cmax，将Hilbert曲线编码的划分密度增加一倍；重复以上操作直至满足要求。

边界数据处理。对这类跨越边界的数据，有指定网格和复制方法[11]。考虑到实际点矢量数据跨越网格的情况并不多见，本文采用了指定网格法。

Fig.1 HAGR-tree construction图1 HAGR树构建流程

4.3 查询算法

索引构建完成后，采取一种基于空间关系判断的迭代式深度优先查询方式。空间关系判断在两层索引的查询过程中都有涉及。

空间关系判断。本文中，将空间关系主要分为4类：包含、相交、外包以及不相交。以Local index中给定QR的查询LIQ（local index query），P为一个节点，Pi是一个指向根节点的指针，P.agg是节点对应的聚集值，P.Mbb是节点对应的外包框，P.child是子节点。则4种关系描述如下。

（1）包含，Mbb∈QR，可以直接从该节点获取聚集值P.agg。

（2）相交，QR⋂Mbb≠ ∅ 且QR⋂Mbb≠QR，需要继续查询P的所有孩子节点。

（3）外包，QR⋂Mbb=QR，同样需要继续查询孩子节点。

（4）不相交，QR⋂Mbb=∅ ，该节点及其孩子节点直接出队，不再查找。

综合得到查询过程如算法1所示。首先利用Global Index实现剪枝，然后利用LIQ进行一种迭代式的DFS查询，过程中判断QR与该节点的Mbb的空间关系再继续查找，直到获得所有Local Index的结果，合并后输出最终的Ra。

算法1HACR树查询算法

输入：HAGR树H-tree，聚集范围查询QR。

输出：聚集查询结果Ra。

1.search inGlobal Index,find everyMbb⋂QR≠ ∅ ；

2.for each qualifiedMbbdoLIQ(Pi,QR)；

3.collect the answer,print the finalRa.

4.FunctionLIQ(Pi,QR){

5.for each branchP∈Pi

6.ifQRcontainsP.Mbb{Ra+=P.agg;}

7. else ifQRintersectsP.Mbb

8. caseP.childis branch

9. for eachP.childdoLIQ(P.child,QR);

10.caseP.childis leaf

11. for everyP.child

12. ifQRcontainsP.child{Ra+=1;}

13. end for

14.end if

15.end for}

5 面向在线交互的索引方法

基于HAGR树索引，能够并行反馈精确聚集查询结果，但是在线应用中，有时用户并不愿为精确的查询结果等待长时间。如果随着时间推移，查询结果的精度越来越高，且用户能在任意时间结束该查询，这将能大大提升在线查询的交互性。基于此，本文提出了MSAR树，给出了近似分析的基本思想和理论支撑，介绍了构建流程以及查询方法。

5.1 随机采样和聚集

MSAR基于数据采样、金字塔构建以及逐层求精3种思想。此外，构建的随机样本满足独立同分布，这样后续的分析才有统计上的实际意义。

数据采样。采样是应对大规模数据的一种有效手段，降低了后续处理的I/O。PAA[15]中维护固定大小为M∈[10，100]的RS（M单位为MB），在处理356 GB的数据时，M=25 MB，S=0.0686%，且RS缓存到内存中，因而实现了很高的查询效率。本文设定采样率S(S∈(0,1))，并不固定样本的大小，而是采用一种无放回的采样方式构建动态随机样本集DS（data of random sample）。

逐层查询求精。数据量小的数据查询速度较快，因而从最高层级Layerl开始查询，根据用户的反馈决定是否终止查询。

以上思想需要随机采样理论作为支撑，而这方面已有很多相关研究[13,28-30]。Haas对范围查询的采样方式使用了新的约束，样本在查询内部和查询之间必须是独立的，这样的方法很好地实现了理论上的完备性。但是在实际应用中，尤其是面向超大规模的空间数据，耗费比较多的时间[30]。在OA[13]研究中，使用中心极限定理来计算近似聚集查询结果，这要求使用的数据必须是随机获得的。本文中，先获取DS，采样得到的数据即为随机元组集合。然后，对DS基于索引聚集查询。根据Index Scans，这是具有实际统计意义的结果。

近似分析时需要数据满足独立同分布，后续分析才有统计意义。本文认为这样得到的元组信息是满足独立同分布。基于以下三点认识：

（1）对不同用户而言，一般他们只会执行相同的QR一次。即便进行多次，只要等待（结束查询）的时间不一样，得到的Ra不同。

（2）索引更新代价并不高，对于实际中产生的数据采用实时采样更新的方式添加，这样更新前后的数据是有差异的。

（3）为了应对上亿规模或是更大的空间数据集D，相应的预处理过程是很有必要的。

5.2 MSAR树构建

在时空数据采样的基础上，得到了金字塔多级数据，然后以此为基础进行索引构建。LS树采用类似的思想实现了多层级索引，在单机环境中实现[16]。为了在分布式环境中应用，充分优化提升索引效率，本文提出的MSAR树还有以下特点。

自适应数据分块。数据金字塔中，各个层级Ni（i∈[1，l]）差异较大，因而须根据Ni进行不同粒度的数据分解。当层级低，Ni大的时候，分块尽可能多，ki≥3c；当层级高，Ni小的时候，分块相应减少，因为过多分块会导致很多初始化开销。

并发并行查询。为了获取近似结果的同时快速获取精确结果，本文还可采取并发方式，对多层级索引同时查询，为在线聚集查询提供更佳体验。

MSAR树的构建过程如图2所示，可分为随机样本获取、划分及分块、索引构建3个主要步骤。

Fig.2 MSAR-tree construction图2 MSAR树构建流程

（1）随机样本获取。设定S，构建数据金字塔DS0DS1…DSl。

（2）划分及分块。在各个DS基础上得到输入数据Data，进行数据划分、数据排序；然后处理数据倾斜和边界对象；最后自适应数据分块。

（3）索引构建。在各个层级上建立Local Index和Global Index，并依据硬件条件动态缓存，得到MSAR树。

5.3 查询算法

在查询时，基本方法如算法2描述所示，LIQ与算法1同，输入为整个Local Index。具体查询过程中，既可以按照高层级到低层级的方式进行，还可以进行并发查询。算法中描述的是顺序查询方法。

算法2MSAR树查询算法

输入：MSAR树M-tree，聚集范围查询QR。

输出：聚集查询结果Ra。

1.whileLayer>0,do{

2.search inGlobal Index,find everyMbb⋂Q≠∅ ;

3.for every qualifiedMbbdo

4.LIQ(Local Index,QR);

5.returnRaandCI

6.ifRais qualified

7.exit query

8.else

9.Layer=Layer-1

10.end if}

6 时空在线分析与估计

6.1 估计总体查询结果

对MSAR树，除底层数据外，其他层级的数据都是随机采样所得到的。范围查询QR数据分互斥的元组集合：满足QR的集合，不满足QR的集合。

结合OA方法，本文基于索引聚集查询，得到的是具有实际统计意义的结果，因为用于构建索引V不同于用来聚集计算的V，避免了数据属性值影响其检索的顺序。

6.2 置信区间计算

MSAR树反馈的近似结果需要一个评价指标，使得用户能够根据结果做出是否采纳当前结果的判断。而且，在保证置信度水平不变的情况下，需要尽可能缩短CI的宽度，提高结果质量。由于本文针对大规模空间数据进行分析，可以由CCI（conservative CI）和LCI（large-sample CI）分析，但是选择了后者作为衡量标准，因为LCI较CCI往往能提供更短的CI。

在对整体估计基础上，根据Hoeffding不等式即可以计算出CCI，结果区间为[Yn-εn,Yn+εn]，能够保证最终结果大于或等于p。

7 实验

7.1 实验设置

本节评价两种索引方法的性能。程序利用Scala语言实现，Spark版本为1.6.1，Hadoop版本为2.6.3，Scala版本为2.10.4。具体机器配置如表1所示。

Table 1 Experiment environment表1 实验环境

本文使用OpenStreetMap线矢量数据中的节点作为点数据，如表2所示。其中，OSM_China（OP）表示中国区域的数据，OSM_Planet（OP）表示全球数据。实验中，选取GeoSpark[21]中的R树索引（GR）和Simba[25]中的R树索引（SR）与本文算法进行比较。实验从索引构建时间、查询效率、误差和置信区间四方面评价不同算法。

Table 2 Experimental datasets表2 实验使用的数据集

7.2 索引构建时间比较

本实验首先评价HAGR树和MSAR树在单机、集群环境下的构建效率。

Fig.3 Performance comparison on index construction图3 索引构建性能比较

单机构建时间比较。如图3（a）所示，GR树的构建速度最快，因为其针对空间数据结构在每个分区内构建局部索引，以一种自适应方式根据数据块大小决定是否构建索引。HAGR树构建速度较SR树稍快，差别并不大，但两者较GR树的构建时间慢一个数量级，且这一趋势随着数据量增加愈发明显。由于数据采样、多层级索引构建及缓存等，MSAR树构建最耗时，大致为HAGR树的两倍。

集群构建时间比较。结果如图3（b）所示，应对16.9亿条数据时，GR树构建时间为80.3 s；MSAR树构建时间是465.5 s，都能较快完成。（a）（b）中的数据不同，OP是整个地球的数据集，其范围较OC广得多，构建更复杂。即便如此，两者同样规模的数据对比依旧具有一定分析意义。在N为5000万时，HAGR、MSAR和SR比单机快，因为合理的数据划分和并行构建。而GR提升效果不明显，尤其是当数据量小的时候，这正是由于其特定数据划分以及自适应构建方式导致的。总体而言，本文方法在集群具有较好可扩展性。

7.3 查询时间比较

本实验比较在查询过程数据大小N变化、固定查询框的比例QR/Q，以及查询框的比例QR/Q变化、固定数据集N这两种情况下，查询时间的变化。MSAR树反馈的是最高层级（l=10，S=50%）的查询结果。将l10层级采样数据量视作PAA[15]中的RS，并行进行顺序元组查询方法即可视作并行PAA方法中阶段一的查询，这一阶段查询仅仅利用预构建样本查询，以P-PAA（parallel PAA）表示。P-PAA仅仅应用在QR/Q变化，固定N的实验中，因为该方式下固定数据集大小，更接近原文中阶段1的查询方法。

（1）N变化，固定QR/Q

Fig.4 Performance comparison on index query图4 索引查询性能比较

单机实验。结果如图4（a）所示，由于3种优化措施，MSAR树查询性能最优。在N为5000万时，MSAR相较于HAGR、SR以及GR分别实现了2.8、17.5、199.9倍的性能提升。HAGR树的查询性能相较于SR树大致提升一个数量级，且随N增加而更加明显。这是因为全局网格索引实现有效剪枝，当N增加时元组密度增加，单个D的Mbb会减小，因而相同的范围中包含了更多的完整数据块，这些数据块的聚集结果可以直接在全局索引中获取。然而，构建速度最快的GR树查询效果却最慢，这是由于GR树仅仅构建了局部索引，其中自适应的方式没对较小的数据块构建索引。

集群实验。如图4（b），集群环境中进行同样的实验得到了基本类似的结果，4种方法都能够应对16.9亿规模数据。MSAR树实现了更高的稳定性。但是应对同等N的数据集时，MSAR、HAGR和SR都并未表现出提升，这是由于数据的空间范围大大增加，提升了查询复杂度。GR的提升是由于该数据集上更合理的划分方法。

（2）QR/Q变化，固定N

对于特定数据集，当查询框的面积变化时查询性能的变化。在该实验中，添加了两种比较方法，RR（range report）和P-PAA。RR是并行遍历方法，对非采样数据进行查找。

单机并行环境。如图4（c）所示，即便并行进行，RR的查询效率依旧较低。这种遍历式的方法对资源消耗较大，不适用于在线交互。P-PAA并行遍历RS后，仅仅耗时635.8 ms就能得到计算结果，耗时较GR短。MSAR树、HAGR树以及GR树的查询效率在QR增加时均呈现下降趋势，这是由于前两种方法在QR增加时可能覆盖很多完整D的Mbb，因而不需要搜索Local Index便能得到聚集结果。类似的是，GR树虽然没有全局索引，但每个D包含整个数据块的聚集信息，因而也会出现先上升后下降的趋势。SR树呈现上升趋势，因为单个局部索引中不包含任何D的聚集信息，需要进一步查询得到聚集结果。

集群并行环境。如图4（d），实验结果基本类似，HAGR树和MSAR树的查询性能保持稳定。P-PAA的优势更加明显，平均仅需1112.8 ms就能得到计算结果。但是，GR树的查询时间随QR先下降后上升，因为当数据量增加后，I/O和整体计算量依旧增加。

7.4 估计精确查询结果

本实验利用MSAR树在OC上验证，在单机并行环境中进行，采取由高层级到低层级的顺序逐层反馈方式。

实际查询结果如表3所示，其中Time为累计时间，Count为该层级的聚集结果，Error为相较于完整数据查询结果得到的误差。查询时，按照从Layer10到Layer1的顺序。当由Layer4查询到Layer3时，Time迅速增加，这正是由动态缓存方式所导致的，Layer10到Layer4的数据都缓存在内存中，而剩余部分的数据都是缓存在磁盘中，因而查询需要耗费更多时间。当查询到Layer3时，查询误差已经下降到0.31%，达到了较高的精度。且从总体看来，误差呈现下降趋势。