基于不均勻空間劃分和R樹的時空索引

趙馨逸 黃向東,2 喬嘉林 康 榮 李 娜 王建民,2

1(清華大學軟件學院 北京 100084)2 (工業(yè)大數(shù)據(jù)系統(tǒng)與應(yīng)用北京市重點實驗室 北京 100084) (stefanie_xin@163.com)

時空數(shù)據(jù)是指包含時間和空間經(jīng)緯度信息的時空對象[1].它的特點是數(shù)據(jù)量大、更新頻率快、數(shù)據(jù)分布不均勻、在時間和空間維度具有自己的時空特性(在時間維度具有連續(xù)性和單調(diào)遞增性，在空間維度具有區(qū)域臨近性).

隨著時空數(shù)據(jù)體量的急劇增加，對其進行有效的存儲、查詢、分析等操作的需求愈發(fā)明顯.時空索引便是解決時空數(shù)據(jù)存儲與查詢的有效手段.解決此問題時，時空索引需要面臨3個核心問題：1)如何在利用時空數(shù)據(jù)特性的同時快速構(gòu)建索引；2)如何進行快速的時空對象查詢；3)如何使其支持更為多樣的查詢種類(如切片查詢、軌跡查詢等).在數(shù)據(jù)量巨大、數(shù)據(jù)分布不均衡的情況下如何構(gòu)造一種合適的索引使得其解決上文提出的問題，是目前面臨的挑戰(zhàn).

從20世紀80年代至今，時空索引已有了長足的發(fā)展和進步.普度大學計算機科學系Mokbel教授在2010年對時空索引的方法進行了詳細的調(diào)查[2]并根據(jù)查詢時間范圍將時空索引技術(shù)分為3類：

1) 歷史數(shù)據(jù)索引TB-Tree(trajectory-bundle Tree)[3]，3D R-Tree[4]，HR-Tree(historical R-Tree)[5]等.

2) 實時數(shù)據(jù)索引2-3TR-Tree(2-3 trajectory R-Tree)[6]等.

3) 未來數(shù)據(jù)索引TPR-Tree[7]等.

本文主要研究歷史數(shù)據(jù)的時空索引，尚不支持對于實時數(shù)據(jù)和未來數(shù)據(jù)的索引.

現(xiàn)有的時空數(shù)據(jù)管理系統(tǒng)和索引存在3方面的問題：

1) 沒有充分利用時空數(shù)據(jù)的特性，如Spatial-Hadoop[8]，PostGIS，Geospark[9]不能同時索引帶有空間和時間維度的數(shù)據(jù)；TB-Tree[10]，3DR-Tree[4]不能保持時空數(shù)據(jù)在空間上或時間上的鄰近性.

2) 無法隨數(shù)據(jù)的密集程度動態(tài)調(diào)整，在數(shù)據(jù)不均勻的情況下導(dǎo)致時間開銷增大，如SETI[11].

3) 無法提供多種類型的查詢處理，輔助使用者進行數(shù)據(jù)的分析，如CloST[12].

為了解決以上諸多問題，本文提出了一種新型2層時空索引GRIST(Geohash and R-Tree based index for spatio-temporal data).它在空間上采用Geohash編碼進行空間劃分，在時間上采用R-Tree索引.為了適應(yīng)不均勻的數(shù)據(jù)分布，GRIST在空間上改進了原有Geohash的編碼及映射算法，設(shè)計了根據(jù)數(shù)據(jù)分布自適應(yīng)分裂的方法；在時間上GRIST改進了一維R-Tree，增加節(jié)點合并策略，以減少R-Tree的規(guī)模、提升查詢效率.同時，GRIST還針對自身的索引結(jié)構(gòu)設(shè)計了時空數(shù)據(jù)查詢方法，提供多種類型的查詢，較好地解決了上文提到的現(xiàn)有系統(tǒng)的3個問題.除此之外，本文還基于Cassandra底層存儲實現(xiàn)了索引構(gòu)建和查詢算法，使用Spark實現(xiàn)分布式查詢，解決大規(guī)模數(shù)據(jù)的存儲與查詢問題.

1 相關(guān)工作

1.1 空間索引方法

R-Tree[13]是高度平衡的多叉樹，通常它會被用來索引高維空間數(shù)據(jù)且不需要預(yù)知數(shù)據(jù)的整體分布，因為它會隨著數(shù)據(jù)更新動態(tài)地調(diào)整數(shù)據(jù)組織的方式.

Quad-Tree[14]按照空間劃分數(shù)據(jù)，可以使用有序的線性表實現(xiàn).它的優(yōu)點是內(nèi)存開銷小、查詢效率高、維護簡單.但它需要預(yù)知數(shù)據(jù)的分布，靈活性比較差.

Geohash是在2008年被提出的，它的思想是把二維經(jīng)緯度編碼為一維的字符串.這種編碼可以保證空間的鄰近性，編碼相同前綴位數(shù)越多，空間距離越近.目前，Geohash已被廣泛應(yīng)用于需要使用一維索引處理空間數(shù)據(jù)的情況，如HBase[15]等.

1.2 時空索引方法

常見的索引歷史數(shù)據(jù)的時空索引方法主要分為3類：

1) 構(gòu)建包含時間維度的三維R-Tree.該類方法時空共用1棵R-Tree，將時間信息作為一個新的維度加入到R-Tree的創(chuàng)建過程中.代表索引有3DR-Tree[4]等.它的優(yōu)點是應(yīng)答基于坐標的查詢效率較高；缺點是作為樹結(jié)構(gòu)，引入過多多余空間且基于軌跡的查詢效率不高.

2) 為每個時間戳構(gòu)建一個二維R-Tree.常見的有HR-Tree[5]，MV3R-Tree(multiversion 3D R-Trees)[16]等.它的優(yōu)點是對時間點查詢十分有效；缺點是時間段查詢效率非常低.

3) 面向軌跡的索引.該類方法主要供軌跡查詢，代表有TB-TreSe[3]，SEB-Tree(start/end time stamp B-Tree)[17]等.它的優(yōu)點是維持了“軌跡”的概念，同一個軌跡的節(jié)點被鏈接在一起；缺點是破壞了空間鄰近性，不利于空間近鄰查詢.

1.3 現(xiàn)有時空系統(tǒng)

GeoMesa基于空間填充曲線技術(shù)(z-order-curve)降維，然后將一維空間進行Geohash編碼，將空間編碼和時間區(qū)間進行交叉組合對數(shù)據(jù)進行分區(qū)存儲[18].該系統(tǒng)支持空間、時間、屬性過濾查詢.但是由于空間劃分和時間劃分粒度大小固定，它不能適應(yīng)數(shù)據(jù)分布和查詢條件的變化.

PostGIS是關(guān)系型數(shù)據(jù)庫PostgreSQL的擴展系統(tǒng)，主要用于處理空間數(shù)據(jù).它采用R-Tree的空間索引結(jié)構(gòu)，支持快速查詢的空間索引.PostGIS提供了強大的空間數(shù)據(jù)分析方法，可以支持海量數(shù)據(jù)的存儲與管理，但是對時間維度的處理較為欠缺.

TrajStore[19]是一個自適應(yīng)存儲軌跡數(shù)據(jù)的系統(tǒng)，采用Quad-Tree的空間索引結(jié)構(gòu).它提出了空間網(wǎng)格的分裂和合并等動態(tài)操作，以適應(yīng)數(shù)據(jù)的增加或查詢框大小的變化.但是，該系統(tǒng)不是分布式的，難以應(yīng)對GB級甚至TB級的數(shù)據(jù).

2 問題定義

2.1 時空數(shù)據(jù)定義

時空數(shù)據(jù)由多個時空數(shù)據(jù)點構(gòu)成.時空數(shù)據(jù)點為一個四元組(Stringdeviceid，longtimestamp，floatlon，floatlat).其中deviceid為時空數(shù)據(jù)所屬設(shè)備的唯一標識(設(shè)備號)，timestamp為時空數(shù)據(jù)產(chǎn)生時刻的時間戳，lon和lat分別為數(shù)據(jù)空間信息的地理經(jīng)緯度.

2.2 時空數(shù)據(jù)類型定義

按照時空數(shù)據(jù)的查詢需求，時空數(shù)據(jù)可以分為二維空間點、二維空間區(qū)域(矩形空間區(qū)域與圓形空間區(qū)域)、軌跡點、軌跡5種主要類型，定義如下：

1) GPSData，二維空間點.由經(jīng)度值與緯度值構(gòu)成，表示為(lon,lat).

2) GEOCircle，二維圓形空間區(qū)域.在二維空間中的圓形區(qū)域，由一個GPSData類型的圓心和一個浮點型半徑組成，表示為(GPSDatacenter,floatradius).

3) GEORect，二維矩形空間區(qū)域.在二維空間中的矩形區(qū)域，由2個GPSData類型的點組成(分別代表矩形左下角與矩形右上角的點)，表示為(GPSDatabl,GPSDatatr).

4) TrajPoint，軌跡點.帶有時間信息的GPSData點，由一個GPSData類型的點與時間戳組成，表示為(GPSDatalocation,longtimestamp).

5) Traj，軌跡.一系列相同deviceid的軌跡點集合.由一組按時間升序排列的TrajPoint組成，一組擁有N個TrajPoint的軌跡表示為[TrajPointtji]N(i=1,2,…,N).

2.3 查詢模式定義

時空數(shù)據(jù)的查詢需求種類繁多，本文算法主要討論面向時空的查詢，涉及的查詢種類有3種：

1) GEORectregion,longt→[GPSDatap]n.根據(jù)空間范圍與時間點，查詢所有的相關(guān)數(shù)據(jù)點(個數(shù)為n).

2) GEORectregion,[longt1,longt2]→[GPSDatap]n.根據(jù)空間范圍與時間段，查詢所有的相關(guān)數(shù)據(jù)點(個數(shù)為n).

3) GEORectregion,[longt1,longt2]→[TrajPointtp]n.根據(jù)空間范圍與時間段，查詢所有的相關(guān)數(shù)據(jù)點(個數(shù)為n).

其中，region表示空間范圍，t表示時間點，[t1,t2]表示時間范圍，p表示空間點，tp表示軌跡點，[]n表示元素個數(shù)為n的集合.

2.4 本文涉及的相關(guān)參數(shù)

本文GRIST索引涉及的相關(guān)參數(shù)如下：

1) 數(shù)據(jù)包包含的數(shù)據(jù)個數(shù)(packageSize).每個包中二位空間點的個數(shù)，由用戶指定.

2) 最大編碼長度(Lmax).空間索引的最大編碼長度，由用戶指定.

3) 最小編碼長度(Lmin).空間索引的最小編碼長度，由用戶指定.

4) 時間和空間分裂閾值(maxRTreeSize).R-Tree分裂為4個子樹時所需達到的數(shù)據(jù)量，由用戶指定.

3 GRIST索引的構(gòu)建

本節(jié)主要介紹GRIST索引的結(jié)構(gòu)與構(gòu)建過程.GRIST索引結(jié)構(gòu)為2層時空索引：第1層為空間索引；第2層為時間索引.在構(gòu)建時，GRIST會首先根據(jù)用戶設(shè)置對數(shù)據(jù)進行打包，并建立數(shù)據(jù)包的摘要，隨后以數(shù)據(jù)包為單位進行索引的構(gòu)建.

3.1 數(shù)據(jù)包與數(shù)據(jù)摘要

數(shù)據(jù)包是GRIST時空索引所處理的基本單元，在索引構(gòu)建時會將同設(shè)備號、一定數(shù)目(packageSize)的GPSData類型的數(shù)據(jù)按照時間升序排列構(gòu)成數(shù)據(jù)包，這樣的設(shè)計可以減少索引構(gòu)建時由于數(shù)據(jù)插入所帶來的索引更新次數(shù).

為了減小索引體積，GRIST中僅存儲數(shù)據(jù)包的摘要而非數(shù)據(jù)包中的原始數(shù)據(jù).摘要是數(shù)據(jù)包中所有點構(gòu)成的矩形，它的表示形式為GEORect (GPSDatabl,GPSDatatr)，其中bl為數(shù)據(jù)包中空間位置位于左下角的點，tr為右上角的點.摘要結(jié)構(gòu)如圖1所示，其中黑色點代表一個GPSData，矩形框表示摘要.

Fig. 1 Digest of packet圖1 摘要結(jié)構(gòu)示意圖

3.2 GRIST時空索引概述

GRIST為2層時空索引.第1層為空間索引，它將空間劃分為沒有交疊且可根據(jù)網(wǎng)格里的數(shù)據(jù)量自適應(yīng)調(diào)整的網(wǎng)格.每個網(wǎng)格使用本文提出的不均勻Geohash映射算法計算得到.第2層為時間索引，利用一維R-Tree進行構(gòu)建，不同R-Tree索引第1層空間的不同網(wǎng)格中的數(shù)據(jù)，其中MBR為一維時間段，葉子節(jié)點為存儲設(shè)備的deviceid.在使用中，本文對R-Tree進行了一些改進，當同一個設(shè)備的2個MBR時間段連續(xù)時，將會對其進行合并.同時，為了自動適應(yīng)時空數(shù)據(jù)的不均勻分布，當某一個區(qū)域的數(shù)據(jù)點個數(shù)達到某個閾值(maxRTreeSize)時，GRIST會分別在時間和空間層索引上進行分裂.下面詳細介紹2層索引的具體內(nèi)容和分裂策略.

2層索引的組合方式如圖2所示，第1層索引的每一個空間網(wǎng)格都會有一個第2層索引的R-Tree與之對應(yīng)，為了更清晰地表達，圖2中僅給出1種空間網(wǎng)格與R-Tree的對應(yīng)關(guān)系.

Fig. 2 Correspondence between spatial grid and R-Tree圖2 空間網(wǎng)格與R-Tree的對應(yīng)關(guān)系

選擇先空間索引后時間索引的原因，一方面是由于空間是固定不變的而時間是無限增長的，因而空間對數(shù)據(jù)的劃分較于時間更為明顯；另一方面則是因為這樣的劃分可以同時保障數(shù)據(jù)在空間上的鄰近性以及在一定空間內(nèi)時間上的連續(xù)性和鄰近性.

3.3 第1層空間索引

由于Geohash編碼可以將二維坐標數(shù)據(jù)映射成一維空間并保證空間的臨近性，GRIST的第1層空間索引選取了Geohash作為編碼算法的基礎(chǔ).但是，傳統(tǒng)的Geohash編碼是將整個空間均勻劃分，會產(chǎn)生某個區(qū)域的數(shù)據(jù)過度密集的情況.一方面，當新的數(shù)據(jù)到來的時候，更新這個區(qū)域的索引會帶來很大的I/O負擔；另一方面，查詢的時候也會增加I/O成本和查詢候選集的大小，降低查詢效率.因此，GRIST的空間索引在Geohash均勻編碼的基礎(chǔ)上根據(jù)區(qū)域內(nèi)的數(shù)據(jù)量多少自動進行空間分裂，以達到平衡每個區(qū)域中數(shù)據(jù)量的目的.

3.3.1 空間索引的分裂策略

GRIST的空間分裂策略是當1個區(qū)域內(nèi)的數(shù)量達到分裂閾值后，該區(qū)域自動分裂為4個等大的子區(qū)域，原始編碼同時被刪除.

如圖3所示，當1100區(qū)域中數(shù)據(jù)超過分裂閾值后，該區(qū)域?qū)⒂?100編分裂為{110000，110001，110010，110011}編碼的4個區(qū)域.0011區(qū)域分裂情況同理.

Fig. 3 Example of GRIST geometry split圖3 區(qū)域分裂示意圖

自動空間分裂會造成空間中各部分的Geohash的編碼長度不等(稱之為不均勻編碼)，在傳統(tǒng)的均勻編碼下，可以使用Geohash編碼、解碼算法完成空間到編碼集合的映射.但是在不均勻編碼時，傳統(tǒng)方式無法完成.同時，空間劃分的集合也更加不易維護，需要動態(tài)更新.因此GRIST提出了針對不均勻編碼的編碼存儲與索引集維護方法，并針對不均勻空間給出了編碼和映射算法.

3.3.2 不均勻Geohash編碼存儲與索引集維護

由于不均勻編碼，空間中不同區(qū)域?qū)?yīng)的Geohash編碼長度不一，使得搜索難度增大.因此，GRIST設(shè)計了一種統(tǒng)一的64 b長整型的編碼，對不均勻的Geohash進行存儲.

編碼的轉(zhuǎn)換規(guī)則如圖4所示.假設(shè)Geohash編碼長度為L，位置0～7位為L，位置8～61-L位為0，位置62-L～61位為Geohash編碼本身，下標62～63位為0.

以1111為例，轉(zhuǎn)換后的64 b為：00 1111 00…000 00000100.這種轉(zhuǎn)換有2個明顯的好處：一方面是節(jié)省空間索引編碼的空間消耗，將字符串轉(zhuǎn)為整型進行存儲；另一方面，該編碼保留了空間上的鄰近性，空間上越鄰近轉(zhuǎn)換后的數(shù)值大小越接近.同時，可以保證一個Geohash編碼的所有前綴編碼對應(yīng)的整型值都小于等于該Geohash對應(yīng)的整型值，這個優(yōu)點對下文中提到的空間映射前綴查找很有幫助.

Fig. 4 Spatio code圖4 編碼轉(zhuǎn)換規(guī)則示意圖

通過不均勻Geohash編碼，整個空間可以表示為一系列長整形Geohash編碼的集合，稱之為空間索引集.初始的空間索引集為整個空間(GEORect(GPSData(-180,-90),GPSData(180,90)))在編碼長度為最小編碼長度(用戶設(shè)定)時的均勻Geohash編碼集合.在索引的構(gòu)建過程中，隨著數(shù)據(jù)的不斷加入，空間索引集也在動態(tài)變化.

3.3.3 不均勻Geohash空間編碼和映射方法

對于時空索引，給定空間在索引集上的映射是索引構(gòu)建和查詢的關(guān)鍵環(huán)節(jié)，主要分為2個步驟：1)將給定的空間編碼為Geohash值的集合；2)在空間索引集中尋找相應(yīng)的編碼集合(稱為空間映射).在GRIST中主要涉及2種空間類型：點和區(qū)域，而區(qū)域均可轉(zhuǎn)化為其外接矩形，因此以下主要討論點和矩形的編碼和映射算法.點的編碼方法為傳統(tǒng)Geohash編碼，在此不再闡述.我們在此給出在不均勻Geohash空間編碼下矩形編碼算法(算法1)、點映射算法(算法2)、矩形映射算法(算法3).

算法1. 不均勻空間矩形編碼算法.

輸入：GEORectr、編碼長度L(偶數(shù))；

輸出：編碼集合C.

① 計算r.bl和r.tr長度為L的Geohash編碼g1,g2；

② 分別使用Geohash解碼g1,g2，得到矩形r1和r2；

③ 使用r1.bl和r2.tr構(gòu)成矩形rc；

④ 計算經(jīng)度間隔：l1=360lbL；

⑤ 計算緯度間隔：l2=180lbL；

⑥ 以l1和l2均勻劃分rc,得到矩形集合R；

⑦ 計算R中每個矩形的中心點，得到點集合P；

⑧ 對P中每個點計算長度為L的Geohash編碼，得到編碼集合C；

⑨ RETURNC.

矩形編碼算法的主要思路是：首先將原始矩形的左下角和右上角進行Geohash編碼、解碼得到新的矩形rc，如圖5中左1圖、左2圖所示，之后按照編碼長度L將矩形劃分成小矩形空間，如圖5中右2圖所示，此時劃分過的矩形即為矩形對應(yīng)的Geohash區(qū)域.計算這些區(qū)域中心點的Geohash值即可得到最終的編碼集合，如圖5中右1圖所示.

Fig. 5 A example of rectangle encoding圖5 矩形編碼算法示意圖

算法2. 不均勻空間點映射算法.

輸入：空間點p、空間索引集S、最大編碼長度Lmax(用戶預(yù)設(shè))；

輸出：點編碼Cp.

① 計算點p長度為Lmax的空間點編碼g；

② 在S中搜索g的前綴編碼Cp；

③ RETURNCp.

因為使用最大編碼長度映射出的編碼未必存在于真實的空間索引集中，所以需要在空間索引集中找到與該編碼最為接近(即前綴匹配個數(shù)最多的編碼)，我們稱之為前綴編碼.由于GRIST將Geohash編碼轉(zhuǎn)化成了64 b整數(shù)類型，前綴查找的方法就變?yōu)樵诳臻g索引集中進行二分查找，找到比待查找編碼小的編碼中最大的編碼，即為待查找的前綴編碼.這樣的操作降低了原有字符串前綴匹配的時間復(fù)雜度.

算法3. 不均勻空間矩形映射算法.

輸入：矩形r、空間索引集S、最大編碼長度Lmax(用戶預(yù)設(shè))；

輸出：映射編碼集合Cr.

① 將矩形r，最大編碼長度Lmax輸入到算法1，得到矩形編碼集合C；

② 在S中搜索C中每個編碼c的前綴，將前綴加入映射編碼集合Cr中；

③ RETURNCr.

3.4 第2層時間索引

GRIST第2層索引為時間索引，采用一維R-TREE來索引時間段，每個空間分區(qū)內(nèi)的數(shù)據(jù)使用一維R-Tree建立時間索引.R-Tree內(nèi)部節(jié)點是一維的時間段，葉子節(jié)點是設(shè)備ID.它的特性使得時間上鄰近的對象會存在同一個節(jié)點.

Fig. 6 An example of temporal index building圖6 時間層索引構(gòu)建過程

3.4.1 R-Tree時間索引的構(gòu)建

R-Tree構(gòu)建時同樣以數(shù)據(jù)包為單位，對于每個數(shù)據(jù)包，都對應(yīng)一段帶有時間信息的數(shù)據(jù)，如圖6(a)所示.我們可將在時間上定頻、連續(xù)的數(shù)據(jù)歸為一段.之后，會按照這些時間段數(shù)據(jù)的起始時間構(gòu)建R-Tree.時間層索引構(gòu)建的過程如圖6(b)所示.

其中，O1，O2，O3表示3個設(shè)備的ID，L8，L9，L10，L11為O1的4個時間段數(shù)據(jù)，L12，L13，L14，L15為O2的4個時間段數(shù)據(jù)，L16，L17，L18，L19為O3的4個時間段數(shù)據(jù).這些時間段數(shù)據(jù)到達的順序為L16，L8，L12，L9，L17，L10，L13，L18，L11，L14，L19，L15.

在使用過程中，為了減小R-Tree本身的大小、提升查詢效率，本文對它的插入做了一些改進，增加了同一設(shè)備連續(xù)時間段的合并功能.假設(shè)R-Tree中已有時間段[t1,t2]以周期T到達，新來一個時間段[t3,t4]也以周期T到達，且t3與t2之間的間隔剛好為T，那么2個時間段則可以合并，合并后的時間段為[t1,t4].此時R-Tree會刪除[t1,t2]節(jié)點，插入[t1,t4].這樣不僅減小了R-Tree的大小而且便于查詢.

3.4.2 時間索引的分裂策略

當一個空間中的數(shù)據(jù)達到分裂閾值時，空間將進行分裂.伴隨空間層的分裂，時間層也會分裂.空間區(qū)域的分裂在前文已經(jīng)說明.R-Tree的分裂是將該R-Tree索引的數(shù)據(jù)重新按照新的空間劃分分為4部分，然后重新構(gòu)建R-Tree索引.

3.5 GRIST索引構(gòu)建過程

基于3.3節(jié)空間索引和3.4節(jié)時空索引，GRIST時空索引的構(gòu)建流程主要是：

1) 將整個空間(GEORect((-180,-90),(180,90)))構(gòu)建為一個矩形Rspace，將Rspace以及最小編碼長度輸入算法1，得到空間對應(yīng)的矩形編碼，作為整個空間的初始化空間索引集.

2) 計算輸入的數(shù)據(jù)包集合的摘要集合.

3) 對于每一個數(shù)據(jù)包的摘要，使用算法3計算相應(yīng)的矩形映射編碼集合.然后將數(shù)據(jù)包插入編碼集合對應(yīng)空間的R-Tree中.

4) 若R-Tree達到分裂閾值則分裂相應(yīng)空間和時間索引；否則結(jié)束.

算法偽碼如算法4.

算法4. GRIST索引構(gòu)建算法.

輸入：整個空間矩形Rspace、數(shù)據(jù)包集合packages、最小編碼長度Lmin(用戶預(yù)設(shè))、最大編碼長度Lmax(用戶預(yù)設(shè)).

① 將Rspace,Lmin輸入算法1得到空間索引集S；

② 計算packages的摘要集合digests；

③ for eachdigestindigests

④ 將digest,S,Lmax輸入算法3得到矩形映射編碼集合Cr；

⑤ 將digest對應(yīng)的package插入Cr中每一個編碼C的R-Tree中；

⑥ 如果R-Tree達到分裂閾值則分裂相應(yīng)空間和時間索引；否則RETURN；

⑦ end for

4 GRIST索引的查詢

GRIST索引支持本文提到的所有面向時空的查詢，同時支持面向時間的查詢和面向空間的查詢.其中，面向空間的查詢可以看作面向時空查詢的特殊情況(即時間取全集)；面向時間的查詢則是通過對數(shù)據(jù)包在系統(tǒng)存儲層中的排序組織方法予以支持的[20].因而，在此只重點討論面向時空的查詢.

面向時空的查詢均是基于時空索引所做的查詢，其中比較重要的是時空范圍查詢.時空范圍查詢包含設(shè)備查詢(本文2.3節(jié)查詢1和查詢2)與軌跡查詢(本文2.3節(jié)查詢3).在GRIST索引中，面向時空的查詢需要經(jīng)過空間層查詢、時間層查詢2層索引查詢得到所需結(jié)果.

時空范圍查詢見算法5，基本流程如下：

1) 空間層查詢.將查詢區(qū)域映射為索引區(qū)域.

2) 時間層查詢.將每個索引區(qū)域?qū)?yīng)的R-Tree讀到內(nèi)存，進行時間點/段查詢，得到滿足時間條件的包的集合.

3) 時空過濾.遍歷所有的包中的數(shù)據(jù)進行時空過濾，得到結(jié)果設(shè)備集合.

4) 若為設(shè)備查詢，則直接返回結(jié)果集.若為軌跡查詢，則將相同deviceid的設(shè)備分入一組，每組數(shù)據(jù)按照時間升序排列，形成軌跡并返回.

算法5. GRIST時空范圍查詢算法.

輸入：時間查詢范圍Qtime、空間查詢范圍Qspatial、空間索引集S、最大編碼長度Lmax(用戶預(yù)設(shè))；

輸出：空間點集合[S]n、軌跡集合T.

① 空間層查詢.將Qspatial,S,Lmax輸入算法3得到矩形映射編碼集合Crectangle；

② 時間層查詢.在Crectangle中每個編碼C的R-Tree中查詢滿足Qtime的包集合P；

③ 根據(jù)Qtime和Qspatial對P中每一個數(shù)據(jù)進行時空過濾.若為設(shè)備查詢，則直接返回結(jié)果點集.若為軌跡查詢，則將相同deviceid的設(shè)備分入一組，每組數(shù)據(jù)按照時間升序排列，形成軌跡并返回.

5 索引性能實驗

5.1 實驗說明

為了測試GRIST索引的性能，本文基于NoSQL的K-V數(shù)據(jù)庫Cassandra實現(xiàn)了索引和數(shù)據(jù)的持久化，并使用Spark實現(xiàn)GRIST的分布式查詢.實驗主要分為2部分：

1) GRIST相關(guān)參數(shù)對比實驗；

2) GRIST，GeoMesa，PostGIS系統(tǒng)導(dǎo)入與查詢對比實驗.

5.2 實驗準備

5.2.1 實驗環(huán)境

本節(jié)的實驗環(huán)境分為單機和集群2種條件，單機節(jié)點系統(tǒng)為Ubuntu14,i7處理器、30 GB內(nèi)存.集群采用6節(jié)點集群，其中每個節(jié)點配置和單機節(jié)點相同.開發(fā)語言使用Java(JDK1.8)，Cassandra版本為3.3，Spark版本為2.0.

5.2.2 實驗數(shù)據(jù)

本文實驗使用的數(shù)據(jù)來源如表1所示，實驗采用了Uber開源的真實數(shù)據(jù)，但是由于數(shù)據(jù)量較少，本文在Uber數(shù)據(jù)基礎(chǔ)上開發(fā)了隨機數(shù)據(jù)生成器，模擬設(shè)備移動產(chǎn)生的更多數(shù)據(jù).這些隨機數(shù)據(jù)分布不均勻，產(chǎn)生頻率為一個設(shè)備每分鐘1個數(shù)據(jù)點，每個設(shè)備共產(chǎn)生10萬或100萬個數(shù)據(jù)點.為體現(xiàn)GRIST在大數(shù)據(jù)量下的表現(xiàn)，下文實驗主要使用隨機數(shù)據(jù)，同時也會在必要地方使用Uber數(shù)據(jù)進行分析.

Table 1 Data Size of Performance Experiments表1 索引性能實驗數(shù)據(jù)規(guī)模

5.3 GRIST相關(guān)參數(shù)實驗

在GRIST系統(tǒng)中，包大小、R-Tree分裂閾值對GRIST系統(tǒng)的數(shù)據(jù)導(dǎo)入和查詢表現(xiàn)產(chǎn)生一定影響.所以本節(jié)實驗主要圍繞以上2個因素對GRIST索引進行參數(shù)實驗，實驗均使用隨機生成的數(shù)據(jù)(5 000萬條數(shù)據(jù))，在集群條件下進行實驗.

5.3.1 包大小對導(dǎo)入和查詢的影響

本節(jié)的實驗環(huán)境中包大小從100～1 000等間隔取值，間隔為100.編碼長度最小為6，最大為10.R-Tree分裂閾值為1 000.查詢范圍為編碼長度為2，4，6，8，10，12對應(yīng)的空間區(qū)域，時間長度為1年，隨機生成.實驗結(jié)果如圖7所示:

Fig. 7 Result of package size experiment圖7 包大小對導(dǎo)入和查詢的影響實驗結(jié)果

由圖7可以看出，隨著包大小數(shù)值的增大，時空索引數(shù)據(jù)導(dǎo)入時間逐漸減小，且和包大小呈反比關(guān)系.其主要原因是，包的大小越大包的數(shù)量越少，同一批次寫入Cassandra中的數(shù)據(jù)點數(shù)越多.在Cassandra批量寫入的承受閾值內(nèi)，寫入的執(zhí)行速度會隨包大小(包中數(shù)據(jù)點的數(shù)量)而減小.

在查詢效率方面，隨著包大小數(shù)值的增大，查詢時間逐漸減小.其主要原因是隨著包大小增大，系統(tǒng)中維護的包數(shù)量減少，在做相同區(qū)域的查詢時獲取的GRIST數(shù)據(jù)包減少，數(shù)據(jù)包的序列化、反序列化總時間減小.

5.3.2 R-Tree分裂閾值對導(dǎo)入和查詢的影響

本實驗中包大小采用500，編碼長度最小為6、最大為10.R-Tree分裂閾值200～1 000等間隔取值，間隔為100.查詢范圍為編碼長度為2，4，6，8，10，12對應(yīng)的空間區(qū)域，時間長度為1年，隨機生成.實驗結(jié)果如圖8所示.

由圖8可以看出：R-Tree分裂的閾值越小，數(shù)據(jù)插入時間越短，主要原因是R-Tree分裂次數(shù)增多，數(shù)量增長，單個R-Tree規(guī)模下降，將其序列化到磁盤的時間縮短.

同時還可以看出：R-Tree分裂的閾值對查詢耗時影響不大.這是因為在包大小不變時，查詢時間主要由查詢結(jié)果集的大小決定.

Fig. 8 Result of R-Tree splite threshold experiment圖8 R-Tree分裂閾值對導(dǎo)入和查詢的影響實驗結(jié)果

5.4 現(xiàn)有系統(tǒng)對比

與現(xiàn)有系統(tǒng)對比的實驗主要在單機和分布式2種環(huán)境下進行.單機實驗主要以千萬級以下數(shù)據(jù)為數(shù)據(jù)集，分布式實驗主要以千萬級以上數(shù)據(jù)為數(shù)據(jù)集.

5.4.1 單機環(huán)境系統(tǒng)對比實驗

在本實驗中PostGIS系統(tǒng)選用2.1版本，對Geometry類型的數(shù)據(jù)點構(gòu)建GIST索引.GeoMesa系統(tǒng)選用底層為Cassandra存儲的版本，版本號為1.3.1.實驗結(jié)果為10次實驗的平均值.

本實驗中包大小為500，編碼長度最小為6、最大為10，R-Tree分裂閾值為50.Uber數(shù)據(jù)查詢條件為數(shù)據(jù)集所在全部區(qū)域，時間為6個月，隨機生成.Random數(shù)據(jù)查詢條件為編碼為2，4，6，8，10，12對應(yīng)的空間區(qū)域，時間為1個月，隨機生成.實驗結(jié)果如圖9所示：

Fig. 9 Result of comparative experiment in single node environment圖9 單機系統(tǒng)對比實驗結(jié)果

5.4.2 分布式環(huán)境系統(tǒng)對比實驗

在本實驗中，由于PostGIS系統(tǒng)為單機系統(tǒng)，所以不對PostGIS進行實驗.GeoMesa系統(tǒng)選用底層為Cassandra存儲的版本，版本號為1.3.1.由于GeoMesa在億級別以上數(shù)據(jù)集上數(shù)據(jù)插入時間超過1 d，所以GeoMesa實驗僅在5 000萬條Random數(shù)據(jù)集上進行實驗.同時，為驗證GRIST系統(tǒng)在大數(shù)據(jù)集的運行效果，GRIST實驗將在千萬及以上級別數(shù)據(jù)集(如表1所示)上進行實驗.實驗結(jié)果為10次實驗的平均值.

本實驗中導(dǎo)入?yún)?shù)與查詢條件與5.4.1節(jié)中相同，不在此贅述.實驗結(jié)果如圖10所示.

Fig. 10 Result of comparative experiment in cluster environment圖10 分布式系統(tǒng)對比實驗結(jié)果

5.4.3 實驗分析

由圖9和圖10可以看出：相比GeoMesa和PostGIS，GRIST在單機與分布式版本的導(dǎo)入速度上優(yōu)勢明顯，單機版本快10～45倍，集群版本可以達到200倍以上.這主要是因為GRIST首先對數(shù)據(jù)進行了打包，充分利用了Cassandra在批量插入上的優(yōu)勢，且在R-Tree索引中也按照時間進行了聚集，導(dǎo)致索引更新次數(shù)急劇下降，速度帶來顯著提升.

在查詢性能上，查詢區(qū)域大小相同的情況下，GRIST比GeoMesa和PostGIS快2～4倍.這主要是因為數(shù)據(jù)的打包減小了時間索引的個數(shù)，查詢時索引操作次數(shù)降低，查詢速度增快.

6 總 結(jié)

本文針對海量時空數(shù)據(jù)的高效查詢提出了一種新型的索引結(jié)構(gòu)GRIST，并介紹了該索引的構(gòu)建和查詢算法.

2層的時空索引GRIST可以支持海量的、未知分布的數(shù)據(jù)索引；支持多種類型的時空查詢；支持分布式的查詢.同時，本文使用Cassandra和Spark對GRIST實現(xiàn)了索引持久化以及分布式查詢，并針對該系統(tǒng)的參數(shù)對數(shù)據(jù)導(dǎo)入和查詢性能做了實驗分析.與PostGIS和GeoMesa系統(tǒng)對比，GRIST具有很強的數(shù)據(jù)導(dǎo)入性能(10～45倍)以及較強的查詢性能(2～4倍).

未來GRIST還將在以下方面繼續(xù)改進：支持更豐富軌跡查詢的種類，如軌跡相似性、進/出等；支持實時數(shù)據(jù)寫入與查詢操作；支持對未來的預(yù)測查詢；支持時空數(shù)據(jù)分析，如：先將數(shù)據(jù)進行采樣分析數(shù)據(jù)的分布，在數(shù)據(jù)導(dǎo)入前進行數(shù)據(jù)分區(qū)，減少導(dǎo)入的負擔.