面向空間在線分析的并行近似聚集查詢*

申金鑫，吳 燁，陳 犖，景 寧

國防科技大學(xué) 電子科學(xué)學(xué)院，長沙 410073

1 引言

信息化世界里，人人都是移動的數(shù)據(jù)“生產(chǎn)者”。隨著基于位置的服務(wù)普及以及各類移動定位設(shè)備的增長，空間數(shù)據(jù)呈現(xiàn)出“爆炸式”增長，例如，OpenStreetMap全球點(diǎn)矢量數(shù)據(jù)集已有超過27億條記錄。為從日趨海量化的數(shù)據(jù)中獲取有用信息，聚集查詢[1]方法呈現(xiàn)出越來越重要的作用。當(dāng)前很多空間在線應(yīng)用需要的是一個(gè)聚集結(jié)果，而不是單個(gè)對象信息的集合。例如，查詢北京市區(qū)某個(gè)立交橋區(qū)域在某一時(shí)刻的車流量，以便于檢測交通擁堵，并不需要查詢范圍里的所有車輛具體的信息。

聚集查詢具有數(shù)據(jù)密集和計(jì)算密集的特征，是一種耗時(shí)操作?？臻g索引是提升聚集查詢速度的有效手段。R樹是一種典型的二維空間索引，采用最小邊界矩形對空間進(jìn)行劃分[2-5]。Ra*樹在傳統(tǒng)R樹的基礎(chǔ)上增加聚集信息，是最早的多維聚集結(jié)構(gòu)，其目的在于有效處理窗口聚集查詢[6]。之后，聚集R樹（aggregation R-tree，aR樹）在R樹節(jié)點(diǎn)的最小外接矩形內(nèi)標(biāo)注了其所包含的所有對象的聚集值，在聚集計(jì)算時(shí)可直接引用該信息，不用對每個(gè)對象進(jìn)行聚集計(jì)算[7]。隨后，很多空間聚集索引技術(shù)不斷深入發(fā)展[8-10]。

在線聚集應(yīng)用中的需求可分為兩類：一類要獲取精確查詢結(jié)果；另一類只需近似結(jié)果。對于后一種需求，以犧牲結(jié)果精度為代價(jià)來減少等待時(shí)間，但是要保證查詢精度能夠隨著時(shí)間推移不斷提升，且隨用戶需求而停止。就現(xiàn)有研究成果而言，對第一種需求還沒有針對聚集索引的并行構(gòu)建方法。對后一種需求，基于數(shù)據(jù)采樣的近似聚集大多非針對空間數(shù)據(jù)；同時(shí)，返回近似結(jié)果時(shí)，也不能保證精確查詢結(jié)果的速度。

最近，大數(shù)據(jù)處理架構(gòu)飛速發(fā)展，為在線聚集查詢性能的提升帶來機(jī)遇和挑戰(zhàn)。機(jī)遇源于其高效可擴(kuò)展的特點(diǎn)；挑戰(zhàn)就空間聚集查詢而言，包括數(shù)據(jù)劃分和任務(wù)分解兩個(gè)普遍問題。在數(shù)據(jù)劃分時(shí)，如何保持?jǐn)?shù)據(jù)的空間鄰近聚集特征，處理常見的數(shù)據(jù)傾斜和邊界對象分配問題[11]。在任務(wù)分解時(shí)，如何分解數(shù)據(jù)分區(qū)，避免分區(qū)不均導(dǎo)致負(fù)載不均衡以及分區(qū)過多導(dǎo)致的大量初始化開銷。

本文將精確查詢和近似查詢兩種需求結(jié)合起來，在提升精確查詢效率的同時(shí)，又能在精確結(jié)果返回前快速反饋近似查詢結(jié)果。針對精確查詢需求提出了基于Hilbert空間填充曲線劃分的聚集網(wǎng)格R樹（Hilbert partition based aggregation grid-R tree，HAGR樹）。然后在此基礎(chǔ)上提出了一種多層級采樣聚集樹（multi-layer sampling aggregation R-tree，MSAR樹）。

本文的主要貢獻(xiàn)如下：

（1）對Hilbert-aR樹進(jìn)行并行優(yōu)化，在此基礎(chǔ)上實(shí)現(xiàn)了HAGR樹，通過Hilbert數(shù)據(jù)劃分提高了索引搜索效率，建立全局網(wǎng)格索引提升了并行查詢效率。

（2）基于金字塔和大數(shù)據(jù)隨機(jī)采樣思想，在并行HAGR樹的基礎(chǔ)上提出了MSAR樹，通過概率查詢的逐步求精方式進(jìn)一步提升了聚集計(jì)算效率，并且能夠?qū)崿F(xiàn)良好的交互。

（3）在10億規(guī)模真實(shí)數(shù)據(jù)集上，驗(yàn)證本文方法的有效性和正確性，能夠返回給定置信度下的置信區(qū)間，實(shí)現(xiàn)漸進(jìn)式聚集計(jì)算。

2 相關(guān)工作

當(dāng)前，近似聚集方法可以分為預(yù)計(jì)算和在線聚集兩類[12]。本文關(guān)注其中后一種方法。而在線聚集方法可進(jìn)一步分為非索引的在線聚集方法[13-15]和基于索引的在線聚集方法[16-17]。

在非索引的在線聚集方法方面，在線聚集（online aggregation，OA）是一種在線近似聚集方法，不斷從底層隨機(jī)獲取元組并統(tǒng)計(jì)，然后在3個(gè)準(zhǔn)則基礎(chǔ)上計(jì)算置信區(qū)間，直到結(jié)果滿足用戶的要求[13]。DBO數(shù)據(jù)庫原型系統(tǒng)能實(shí)現(xiàn)近似聚集查詢，很快返回一個(gè)推測結(jié)果，隨時(shí)間推移，各種關(guān)系操作從互相通信中獲取更多滿足條件的元組，因而推測結(jié)果的精度也隨之越來越高[14]?；诜謮K的近似聚集算法（partition-based approximate aggregation，PAA）是一種基于劃分的近似聚集方法，對數(shù)據(jù)預(yù)先構(gòu)建一個(gè)隨機(jī)樣本。在查詢時(shí)，首先在預(yù)構(gòu)建的樣本中查詢，如不能滿足要求，再從與查詢區(qū)域相交的各個(gè)分片集合中獲取更多元組[15]。

在基于索引的在線聚集方面。MRA樹是一種多粒度聚集樹，該樹的每個(gè)葉子節(jié)點(diǎn)與一個(gè)區(qū)域范圍相關(guān)聯(lián)，存儲其孩子節(jié)點(diǎn)的聚集信息。在查詢時(shí)，判斷節(jié)點(diǎn)空間范圍與查詢范圍的空間位置關(guān)系，以此來決定是否查詢該節(jié)點(diǎn)的子節(jié)點(diǎn)。將該思想與四叉樹（MRA四叉樹）和R樹（MRA-R樹）結(jié)合，提供漸進(jìn)的估計(jì)結(jié)果以及100%置信度的置信區(qū)間[16]。LS樹和RS樹這兩種索引方式是專門針對空間和時(shí)空在線分析提出的，在查詢過程中不斷獲取新的采樣樣本，采樣實(shí)現(xiàn)了一種面向在線空間或時(shí)空分析的逐步求精的查詢方式，能在任意置信度下反饋估計(jì)結(jié)果以及置信區(qū)間[17]。

以上方法往往在單機(jī)中進(jìn)行，為提升聚集計(jì)算效率，一系列并行改進(jìn)逐漸出現(xiàn)。基于MapReduce計(jì)算模型，能夠在查詢執(zhí)行期間以順序流傳輸數(shù)據(jù)，進(jìn)而不斷修正結(jié)果[18]?；跀?shù)據(jù)庫和大規(guī)模分布式節(jié)點(diǎn)方法，可以設(shè)計(jì)采樣創(chuàng)建和采樣選擇策略，以多層采樣方式實(shí)現(xiàn)對給定的誤差或是給定時(shí)間這兩種查詢模式[19]。這些方法都在大規(guī)模數(shù)據(jù)上取得了良好的效果，但是這些方法都不是專門針對空間數(shù)據(jù)而設(shè)計(jì)的。

在并行空間計(jì)算方面，基于MapReduce和Spark計(jì)算模型，已經(jīng)有Hadoop-GIS[11]、SpatialHadoop[20]，以及GeoSpark[21-22]、SpatialSpark[23]、LocationSpark[24]、Simba[25]等系統(tǒng)，提供了格網(wǎng)、四叉樹、R樹等空間索引支持來加速空間查詢等操作，其中大多系統(tǒng)支持R樹的并行構(gòu)建[11,20-21,24-25]，然而并不提供空間聚集索引的構(gòu)建。

基于以上分析，現(xiàn)有的概率聚集方法很少應(yīng)用于空間數(shù)據(jù)，且現(xiàn)有的空間分析系統(tǒng)并不支持聚集索引。因此，為了提升面向空間大規(guī)模數(shù)據(jù)的聚集分析，本文基于分布式內(nèi)存計(jì)算架構(gòu)Spark，針對在線聚集查詢應(yīng)用，提出了兩種索引方式，HAGR樹和MSAR樹。其中，HAGR樹支持快速時(shí)空精確聚集分析計(jì)算，MSAR樹結(jié)合概率聚集查詢，進(jìn)一步增強(qiáng)了在線時(shí)空聚集查詢的交互性。

3 問題描述

給定空間數(shù)據(jù)D，其中的元組可表示為K,V鍵值對的形式。其中K(K1,K2,…,Kd)表示元組的d維屬性信息，例如，空間矢量數(shù)據(jù)中d=2。V(V1,V2,…,Vv)表示元組的值屬性信息，對空間數(shù)據(jù)而言，V是包含各種空間屬性信息的集合，例如：(Oid,Geometry,…,Geometry Type)等。

聚集查詢可表示為F=fagg(op(V|Q?QR))。其中QR表示查詢區(qū)域；fagg表示聚集函數(shù)，包含SUM、AVG、COUNT、MIN以及MAX等常見聚集函數(shù)操作；op表示屬性操作，代表一般操作映射函數(shù)；Q是D的范圍，則Q?QR表示相交區(qū)域。

對于在線近似聚集，僅當(dāng)聚集結(jié)果來自隨機(jī)采樣中獲得的元組，得到的結(jié)果才是有統(tǒng)計(jì)意義的估計(jì)結(jié)果。這一要求可以通過Heap Scans、Index Scans、Sampling from Indices方法保證，避免元組的屬性值影響其檢索的順序[13]。滿足上述條件基礎(chǔ)上，近似聚集查詢還需要其他衡量指標(biāo)，包括置信區(qū)間CI，置信度p∈(0,1)，以及誤差范圍ε。誤差范圍即置信區(qū)間寬度，是對估計(jì)精度的度量。得到這些指標(biāo)后，即可通過公式CI=為用戶終止查詢提供判斷。

4 并行聚集查詢索引

本文對aR樹并行優(yōu)化，與Hilbert編碼的數(shù)據(jù)劃分方法結(jié)合。在HAGR樹構(gòu)建過程中考慮數(shù)據(jù)劃分和任務(wù)分解兩個(gè)優(yōu)化問題，處理了數(shù)據(jù)劃分過程中常見的數(shù)據(jù)傾斜和邊界對象問題，在查詢中提供了一種基于空間關(guān)系判斷的深度優(yōu)先搜索（depth first search，DFS）方法。

4.1 HAGR樹構(gòu)建

HAGR樹構(gòu)建首要考慮是并行環(huán)境中高效構(gòu)建，因而需要合理的數(shù)據(jù)劃分和任務(wù)分解作支撐。為展示數(shù)據(jù)構(gòu)成，因而又將D表示為D={di|i∈[1,N]}，d為單個(gè)元組，N為元組總數(shù)。

Hilbert編碼劃分方法。采用Hilbert編碼的劃分后，可以獲得幾乎近100%的空間利用率。因而，構(gòu)建的Hilbert-R樹的查詢性能優(yōu)于平方復(fù)雜度節(jié)點(diǎn)分裂的R樹、R*樹和Roussopoulos的批建立方法[26]。根據(jù)Faloutsos等[27]提出的Hilbert曲線編碼生成算法，目標(biāo)點(diǎn)的Hilbert編碼值計(jì)算復(fù)雜度為，其中nh是空間層次劃分次數(shù)，即該點(diǎn)所在網(wǎng)格行列中數(shù)較大值所對應(yīng)的二進(jìn)制位數(shù)。

并行計(jì)算中，網(wǎng)格索引能實(shí)現(xiàn)高效關(guān)系判定，以實(shí)現(xiàn)有效剪枝。因而，本文在結(jié)合網(wǎng)格和聚集R樹索引后得到一種兩級索引——HAGR樹。其構(gòu)建過程如圖1所示，主要分為數(shù)據(jù)劃分、數(shù)據(jù)排序、數(shù)據(jù)分解以及并行索引構(gòu)建等4個(gè)步驟。

（2）在此基礎(chǔ)上，按照Hc對數(shù)據(jù)集排序，實(shí)現(xiàn)空間聚集特性。

（4）以D1D2…Dk為基礎(chǔ)并行構(gòu)建Local Index，得到tree1tree2…treek。如圖1右下角，tree中A1區(qū)域的聚集結(jié)果直接由子節(jié)點(diǎn)a1+a2+a3獲得。之后，獲取各個(gè)數(shù)據(jù)塊的Mbb，更新Global Index，完成兩級索引構(gòu)建。

4.2 數(shù)據(jù)傾斜和邊界對象處理

并行計(jì)算數(shù)據(jù)劃分過程，數(shù)據(jù)傾斜和邊界對象這兩個(gè)問題不可避免。數(shù)據(jù)傾斜源于實(shí)際數(shù)據(jù)的空間維度分布不均，會影響計(jì)算效率。例如，同一個(gè)Hc可能對應(yīng)了多條元組，這些元組空間上無序，無法增加聚集特性，且在后續(xù)任務(wù)分解中容易造成分解不均。邊界對象源于網(wǎng)格劃分方式，若處理不好可能導(dǎo)致查詢結(jié)果錯(cuò)誤。

數(shù)據(jù)傾斜處理。在HAGR樹構(gòu)建的第（1）步中，添加處理算法。對輸入數(shù)據(jù)采樣，減少后續(xù)處理計(jì)算I/O；然后統(tǒng)計(jì)每個(gè)T包含的數(shù)據(jù)量TNH，定義閾值參數(shù)Cmax，如果存在TNH>Cmax，將Hilbert曲線編碼的劃分密度增加一倍；重復(fù)以上操作直至滿足要求。

邊界數(shù)據(jù)處理。對這類跨越邊界的數(shù)據(jù)，有指定網(wǎng)格和復(fù)制方法[11]?？紤]到實(shí)際點(diǎn)矢量數(shù)據(jù)跨越網(wǎng)格的情況并不多見，本文采用了指定網(wǎng)格法。

Fig.1 HAGR-tree construction圖1 HAGR樹構(gòu)建流程

4.3 查詢算法

索引構(gòu)建完成后，采取一種基于空間關(guān)系判斷的迭代式深度優(yōu)先查詢方式。空間關(guān)系判斷在兩層索引的查詢過程中都有涉及。

空間關(guān)系判斷。本文中，將空間關(guān)系主要分為4類：包含、相交、外包以及不相交。以Local index中給定QR的查詢LIQ（local index query），P為一個(gè)節(jié)點(diǎn)，Pi是一個(gè)指向根節(jié)點(diǎn)的指針，P.agg是節(jié)點(diǎn)對應(yīng)的聚集值，P.Mbb是節(jié)點(diǎn)對應(yīng)的外包框，P.child是子節(jié)點(diǎn)。則4種關(guān)系描述如下。

（1）包含，Mbb∈QR，可以直接從該節(jié)點(diǎn)獲取聚集值P.agg。

（2）相交，QR?Mbb≠ ? 且QR?Mbb≠Q(mào)R，需要繼續(xù)查詢P的所有孩子節(jié)點(diǎn)。

（3）外包，QR?Mbb=QR，同樣需要繼續(xù)查詢孩子節(jié)點(diǎn)。

（4）不相交，QR?Mbb=? ，該節(jié)點(diǎn)及其孩子節(jié)點(diǎn)直接出隊(duì)，不再查找。

綜合得到查詢過程如算法1所示。首先利用Global Index實(shí)現(xiàn)剪枝，然后利用LIQ進(jìn)行一種迭代式的DFS查詢，過程中判斷QR與該節(jié)點(diǎn)的Mbb的空間關(guān)系再繼續(xù)查找，直到獲得所有Local Index的結(jié)果，合并后輸出最終的Ra。

算法1HACR樹查詢算法

輸入：HAGR樹H-tree，聚集范圍查詢QR。

輸出：聚集查詢結(jié)果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樹索引，能夠并行反饋精確聚集查詢結(jié)果，但是在線應(yīng)用中，有時(shí)用戶并不愿為精確的查詢結(jié)果等待長時(shí)間。如果隨著時(shí)間推移，查詢結(jié)果的精度越來越高，且用戶能在任意時(shí)間結(jié)束該查詢，這將能大大提升在線查詢的交互性?；诖耍疚奶岢隽薓SAR樹，給出了近似分析的基本思想和理論支撐，介紹了構(gòu)建流程以及查詢方法。

5.1 隨機(jī)采樣和聚集

MSAR基于數(shù)據(jù)采樣、金字塔構(gòu)建以及逐層求精3種思想。此外，構(gòu)建的隨機(jī)樣本滿足獨(dú)立同分布，這樣后續(xù)的分析才有統(tǒng)計(jì)上的實(shí)際意義。

數(shù)據(jù)采樣。采樣是應(yīng)對大規(guī)模數(shù)據(jù)的一種有效手段，降低了后續(xù)處理的I/O。PAA[15]中維護(hù)固定大小為M∈[10，100]的RS（M單位為MB），在處理356 GB的數(shù)據(jù)時(shí)，M=25 MB，S=0.0686%，且RS緩存到內(nèi)存中，因而實(shí)現(xiàn)了很高的查詢效率。本文設(shè)定采樣率S(S∈(0,1))，并不固定樣本的大小，而是采用一種無放回的采樣方式構(gòu)建動態(tài)隨機(jī)樣本集DS（data of random sample）。

逐層查詢求精。數(shù)據(jù)量小的數(shù)據(jù)查詢速度較快，因而從最高層級Layerl開始查詢，根據(jù)用戶的反饋決定是否終止查詢。

以上思想需要隨機(jī)采樣理論作為支撐，而這方面已有很多相關(guān)研究[13,28-30]。Haas對范圍查詢的采樣方式使用了新的約束，樣本在查詢內(nèi)部和查詢之間必須是獨(dú)立的，這樣的方法很好地實(shí)現(xiàn)了理論上的完備性。但是在實(shí)際應(yīng)用中，尤其是面向超大規(guī)模的空間數(shù)據(jù)，耗費(fèi)比較多的時(shí)間[30]。在OA[13]研究中，使用中心極限定理來計(jì)算近似聚集查詢結(jié)果，這要求使用的數(shù)據(jù)必須是隨機(jī)獲得的。本文中，先獲取DS，采樣得到的數(shù)據(jù)即為隨機(jī)元組集合。然后，對DS基于索引聚集查詢。根據(jù)Index Scans，這是具有實(shí)際統(tǒng)計(jì)意義的結(jié)果。

近似分析時(shí)需要數(shù)據(jù)滿足獨(dú)立同分布，后續(xù)分析才有統(tǒng)計(jì)意義。本文認(rèn)為這樣得到的元組信息是滿足獨(dú)立同分布?；谝韵氯c(diǎn)認(rèn)識：

（1）對不同用戶而言，一般他們只會執(zhí)行相同的QR一次。即便進(jìn)行多次，只要等待（結(jié)束查詢）的時(shí)間不一樣，得到的Ra不同。

（2）索引更新代價(jià)并不高，對于實(shí)際中產(chǎn)生的數(shù)據(jù)采用實(shí)時(shí)采樣更新的方式添加，這樣更新前后的數(shù)據(jù)是有差異的。

（3）為了應(yīng)對上億規(guī)?；蚴歉蟮目臻g數(shù)據(jù)集D，相應(yīng)的預(yù)處理過程是很有必要的。

5.2 MSAR樹構(gòu)建

在時(shí)空數(shù)據(jù)采樣的基礎(chǔ)上，得到了金字塔多級數(shù)據(jù)，然后以此為基礎(chǔ)進(jìn)行索引構(gòu)建。LS樹采用類似的思想實(shí)現(xiàn)了多層級索引，在單機(jī)環(huán)境中實(shí)現(xiàn)[16]。為了在分布式環(huán)境中應(yīng)用，充分優(yōu)化提升索引效率，本文提出的MSAR樹還有以下特點(diǎn)。

自適應(yīng)數(shù)據(jù)分塊。數(shù)據(jù)金字塔中，各個(gè)層級Ni（i∈[1，l]）差異較大，因而須根據(jù)Ni進(jìn)行不同粒度的數(shù)據(jù)分解。當(dāng)層級低，Ni大的時(shí)候，分塊盡可能多，ki≥3c；當(dāng)層級高，Ni小的時(shí)候，分塊相應(yīng)減少，因?yàn)檫^多分塊會導(dǎo)致很多初始化開銷。

并發(fā)并行查詢。為了獲取近似結(jié)果的同時(shí)快速獲取精確結(jié)果，本文還可采取并發(fā)方式，對多層級索引同時(shí)查詢，為在線聚集查詢提供更佳體驗(yàn)。

MSAR樹的構(gòu)建過程如圖2所示，可分為隨機(jī)樣本獲取、劃分及分塊、索引構(gòu)建3個(gè)主要步驟。

Fig.2 MSAR-tree construction圖2 MSAR樹構(gòu)建流程

（1）隨機(jī)樣本獲取。設(shè)定S，構(gòu)建數(shù)據(jù)金字塔DS0DS1…DSl。

（2）劃分及分塊。在各個(gè)DS基礎(chǔ)上得到輸入數(shù)據(jù)Data，進(jìn)行數(shù)據(jù)劃分、數(shù)據(jù)排序；然后處理數(shù)據(jù)傾斜和邊界對象；最后自適應(yīng)數(shù)據(jù)分塊。

（3）索引構(gòu)建。在各個(gè)層級上建立Local Index和Global Index，并依據(jù)硬件條件動態(tài)緩存，得到MSAR樹。

5.3 查詢算法

在查詢時(shí)，基本方法如算法2描述所示，LIQ與算法1同，輸入為整個(gè)Local Index。具體查詢過程中，既可以按照高層級到低層級的方式進(jìn)行，還可以進(jìn)行并發(fā)查詢。算法中描述的是順序查詢方法。

算法2MSAR樹查詢算法

輸入：MSAR樹M-tree，聚集范圍查詢QR。

輸出：聚集查詢結(jié)果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 時(shí)空在線分析與估計(jì)

6.1 估計(jì)總體查詢結(jié)果

對MSAR樹，除底層數(shù)據(jù)外，其他層級的數(shù)據(jù)都是隨機(jī)采樣所得到的。范圍查詢QR數(shù)據(jù)分互斥的元組集合：滿足QR的集合，不滿足QR的集合。

結(jié)合OA方法，本文基于索引聚集查詢，得到的是具有實(shí)際統(tǒng)計(jì)意義的結(jié)果，因?yàn)橛糜跇?gòu)建索引V不同于用來聚集計(jì)算的V，避免了數(shù)據(jù)屬性值影響其檢索的順序。

6.2 置信區(qū)間計(jì)算

MSAR樹反饋的近似結(jié)果需要一個(gè)評價(jià)指標(biāo)，使得用戶能夠根據(jù)結(jié)果做出是否采納當(dāng)前結(jié)果的判斷。而且，在保證置信度水平不變的情況下，需要盡可能縮短CI的寬度，提高結(jié)果質(zhì)量。由于本文針對大規(guī)?？臻g數(shù)據(jù)進(jìn)行分析，可以由CCI（conservative CI）和LCI（large-sample CI）分析，但是選擇了后者作為衡量標(biāo)準(zhǔn)，因?yàn)長CI較CCI往往能提供更短的CI。

在對整體估計(jì)基礎(chǔ)上，根據(jù)Hoeffding不等式即可以計(jì)算出CCI，結(jié)果區(qū)間為[Yn-εn,Yn+εn]，能夠保證最終結(jié)果大于或等于p。

7 實(shí)驗(yàn)

7.1 實(shí)驗(yàn)設(shè)置

本節(jié)評價(jià)兩種索引方法的性能。程序利用Scala語言實(shí)現(xiàn)，Spark版本為1.6.1，Hadoop版本為2.6.3，Scala版本為2.10.4。具體機(jī)器配置如表1所示。

Table 1 Experiment environment表1 實(shí)驗(yàn)環(huán)境

本文使用OpenStreetMap線矢量數(shù)據(jù)中的節(jié)點(diǎn)作為點(diǎn)數(shù)據(jù)，如表2所示。其中，OSM_China（OP）表示中國區(qū)域的數(shù)據(jù)，OSM_Planet（OP）表示全球數(shù)據(jù)。實(shí)驗(yàn)中，選取GeoSpark[21]中的R樹索引（GR）和Simba[25]中的R樹索引（SR）與本文算法進(jìn)行比較。實(shí)驗(yàn)從索引構(gòu)建時(shí)間、查詢效率、誤差和置信區(qū)間四方面評價(jià)不同算法。

Table 2 Experimental datasets表2 實(shí)驗(yàn)使用的數(shù)據(jù)集

7.2 索引構(gòu)建時(shí)間比較

本實(shí)驗(yàn)首先評價(jià)HAGR樹和MSAR樹在單機(jī)、集群環(huán)境下的構(gòu)建效率。

Fig.3 Performance comparison on index construction圖3 索引構(gòu)建性能比較

單機(jī)構(gòu)建時(shí)間比較。如圖3（a）所示，GR樹的構(gòu)建速度最快，因?yàn)槠溽槍臻g數(shù)據(jù)結(jié)構(gòu)在每個(gè)分區(qū)內(nèi)構(gòu)建局部索引，以一種自適應(yīng)方式根據(jù)數(shù)據(jù)塊大小決定是否構(gòu)建索引。HAGR樹構(gòu)建速度較SR樹稍快，差別并不大，但兩者較GR樹的構(gòu)建時(shí)間慢一個(gè)數(shù)量級，且這一趨勢隨著數(shù)據(jù)量增加愈發(fā)明顯。由于數(shù)據(jù)采樣、多層級索引構(gòu)建及緩存等，MSAR樹構(gòu)建最耗時(shí)，大致為HAGR樹的兩倍。

集群構(gòu)建時(shí)間比較。結(jié)果如圖3（b）所示，應(yīng)對16.9億條數(shù)據(jù)時(shí)，GR樹構(gòu)建時(shí)間為80.3 s；MSAR樹構(gòu)建時(shí)間是465.5 s，都能較快完成。（a）（b）中的數(shù)據(jù)不同，OP是整個(gè)地球的數(shù)據(jù)集，其范圍較OC廣得多，構(gòu)建更復(fù)雜。即便如此，兩者同樣規(guī)模的數(shù)據(jù)對比依舊具有一定分析意義。在N為5000萬時(shí)，HAGR、MSAR和SR比單機(jī)快，因?yàn)楹侠淼臄?shù)據(jù)劃分和并行構(gòu)建。而GR提升效果不明顯，尤其是當(dāng)數(shù)據(jù)量小的時(shí)候，這正是由于其特定數(shù)據(jù)劃分以及自適應(yīng)構(gòu)建方式導(dǎo)致的?？傮w而言，本文方法在集群具有較好可擴(kuò)展性。

7.3 查詢時(shí)間比較

本實(shí)驗(yàn)比較在查詢過程數(shù)據(jù)大小N變化、固定查詢框的比例QR/Q，以及查詢框的比例QR/Q變化、固定數(shù)據(jù)集N這兩種情況下，查詢時(shí)間的變化。MSAR樹反饋的是最高層級（l=10，S=50%）的查詢結(jié)果。將l10層級采樣數(shù)據(jù)量視作PAA[15]中的RS，并行進(jìn)行順序元組查詢方法即可視作并行PAA方法中階段一的查詢，這一階段查詢僅僅利用預(yù)構(gòu)建樣本查詢，以P-PAA（parallel PAA）表示。P-PAA僅僅應(yīng)用在QR/Q變化，固定N的實(shí)驗(yàn)中，因?yàn)樵摲绞较鹿潭〝?shù)據(jù)集大小，更接近原文中階段1的查詢方法。

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

Fig.4 Performance comparison on index query圖4 索引查詢性能比較

單機(jī)實(shí)驗(yàn)。結(jié)果如圖4（a）所示，由于3種優(yōu)化措施，MSAR樹查詢性能最優(yōu)。在N為5000萬時(shí)，MSAR相較于HAGR、SR以及GR分別實(shí)現(xiàn)了2.8、17.5、199.9倍的性能提升。HAGR樹的查詢性能相較于SR樹大致提升一個(gè)數(shù)量級，且隨N增加而更加明顯。這是因?yàn)槿志W(wǎng)格索引實(shí)現(xiàn)有效剪枝，當(dāng)N增加時(shí)元組密度增加，單個(gè)D的Mbb會減小，因而相同的范圍中包含了更多的完整數(shù)據(jù)塊，這些數(shù)據(jù)塊的聚集結(jié)果可以直接在全局索引中獲取。然而，構(gòu)建速度最快的GR樹查詢效果卻最慢，這是由于GR樹僅僅構(gòu)建了局部索引，其中自適應(yīng)的方式?jīng)]對較小的數(shù)據(jù)塊構(gòu)建索引。

集群實(shí)驗(yàn)。如圖4（b），集群環(huán)境中進(jìn)行同樣的實(shí)驗(yàn)得到了基本類似的結(jié)果，4種方法都能夠應(yīng)對16.9億規(guī)模數(shù)據(jù)。MSAR樹實(shí)現(xiàn)了更高的穩(wěn)定性。但是應(yīng)對同等N的數(shù)據(jù)集時(shí)，MSAR、HAGR和SR都并未表現(xiàn)出提升，這是由于數(shù)據(jù)的空間范圍大大增加，提升了查詢復(fù)雜度。GR的提升是由于該數(shù)據(jù)集上更合理的劃分方法。

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

對于特定數(shù)據(jù)集，當(dāng)查詢框的面積變化時(shí)查詢性能的變化。在該實(shí)驗(yàn)中，添加了兩種比較方法，RR（range report）和P-PAA。RR是并行遍歷方法，對非采樣數(shù)據(jù)進(jìn)行查找。

單機(jī)并行環(huán)境。如圖4（c）所示，即便并行進(jìn)行，RR的查詢效率依舊較低。這種遍歷式的方法對資源消耗較大，不適用于在線交互。P-PAA并行遍歷RS后，僅僅耗時(shí)635.8 ms就能得到計(jì)算結(jié)果，耗時(shí)較GR短。MSAR樹、HAGR樹以及GR樹的查詢效率在QR增加時(shí)均呈現(xiàn)下降趨勢，這是由于前兩種方法在QR增加時(shí)可能覆蓋很多完整D的Mbb，因而不需要搜索Local Index便能得到聚集結(jié)果。類似的是，GR樹雖然沒有全局索引，但每個(gè)D包含整個(gè)數(shù)據(jù)塊的聚集信息，因而也會出現(xiàn)先上升后下降的趨勢。SR樹呈現(xiàn)上升趨勢，因?yàn)閱蝹€(gè)局部索引中不包含任何D的聚集信息，需要進(jìn)一步查詢得到聚集結(jié)果。

集群并行環(huán)境。如圖4（d），實(shí)驗(yàn)結(jié)果基本類似，HAGR樹和MSAR樹的查詢性能保持穩(wěn)定。P-PAA的優(yōu)勢更加明顯，平均僅需1112.8 ms就能得到計(jì)算結(jié)果。但是，GR樹的查詢時(shí)間隨QR先下降后上升，因?yàn)楫?dāng)數(shù)據(jù)量增加后，I/O和整體計(jì)算量依舊增加。

7.4 估計(jì)精確查詢結(jié)果

本實(shí)驗(yàn)利用MSAR樹在OC上驗(yàn)證，在單機(jī)并行環(huán)境中進(jìn)行，采取由高層級到低層級的順序逐層反饋方式。

實(shí)際查詢結(jié)果如表3所示，其中Time為累計(jì)時(shí)間，Count為該層級的聚集結(jié)果，Error為相較于完整數(shù)據(jù)查詢結(jié)果得到的誤差。查詢時(shí)，按照從Layer10到Layer1的順序。當(dāng)由Layer4查詢到Layer3時(shí)，Time迅速增加，這正是由動態(tài)緩存方式所導(dǎo)致的，Layer10到Layer4的數(shù)據(jù)都緩存在內(nèi)存中，而剩余部分的數(shù)據(jù)都是緩存在磁盤中，因而查詢需要耗費(fèi)更多時(shí)間。當(dāng)查詢到Layer3時(shí)，查詢誤差已經(jīng)下降到0.31%，達(dá)到了較高的精度。且從總體看來，誤差呈現(xiàn)下降趨勢。

Table 3 Result estimation and error analysis表3 結(jié)果估計(jì)及誤差分析

7.5 置信區(qū)間分析

本實(shí)驗(yàn)估計(jì)近似查詢的效果。在面向在線分析的應(yīng)用中，對用戶提交的查詢QR，及其設(shè)置的置信度p，為反饋的結(jié)果添加CI。

如圖5所示，利用與7.4節(jié)相同的實(shí)驗(yàn)環(huán)境，設(shè)定p=95%，得到CI結(jié)果，由于估計(jì)結(jié)果兩邊的ε相同，因而未列出估計(jì)結(jié)果值。由圖可知，區(qū)間寬度逐漸收窄，即在同樣的置信度下精度不斷提升，估計(jì)效果越來越好。

8 結(jié)束語

Fig.5 Confidence intervals calculation圖5 計(jì)算置信區(qū)間

本文針對空間在線分析，從并行索引構(gòu)建與查詢出發(fā)提出了HAGR樹和MSAR樹這兩種索引方式。前者能快速反饋精確聚集查詢結(jié)果，后者適用于漸進(jìn)式近似聚集查詢，為解決空間大數(shù)據(jù)分析提供了兩種互為輔助的可行方案。通過10億級數(shù)據(jù)的實(shí)驗(yàn)驗(yàn)證了本文方法是可行、高效、可擴(kuò)展的。