基于實時數據和歷史查詢分布的時空索引新方法

孟學潮 ，葉少珍,2

(1.福州大學 數學與計算機科學學院, 福州 350108； 2.福建省醫療器械與醫藥技術重點實驗室，福州 350002) (*通信作者電子郵箱yeshzh@fzu.edu.cn)

基于實時數據和歷史查詢分布的時空索引新方法

孟學潮1，葉少珍1,2*

(1.福州大學 數學與計算機科學學院, 福州 350108； 2.福建省醫療器械與醫藥技術重點實驗室，福州 350002) (*通信作者電子郵箱yeshzh@fzu.edu.cn)

在大數據時代，數據具有體量大、時空復雜性明顯、對實時性要求較高等特點，而傳統基于樹形結構對大規模時空數據進行索引的方法存在存儲空間浪費和查詢效率較低的問題。為了解決該問題，提出了一種基于數據和歷史查詢記錄分布建立時空索引的新方法HDL-index。該算法一方面根據數據在空間上的分布，通過空間劃分的思想建立索引網格；另一方面考慮到查詢在時間上的延續性，對查詢記錄對象進行密度聚類后抽象出查詢代表模型，然后根據模型的坐標位置和其查詢粒度對整體查詢區域進行分割。兩部分所得到的索引網格都采用Geohash編碼，最終合并得到最優的索引編碼。HDL-index在考慮數據分布的同時充分考慮用戶查詢行為，使得頻繁查詢區域上的索引更加細化。在真實航空數據集上與同類方法進行比較測試的結果表明，其創建索引的效率提高了50%；同時在數據均勻分布的情況下對熱點區域的查詢效率可提高75%以上。

時空索引；大數據；GeoHash編碼；密度聚類；熱點區域查詢

0 引言

近來隨著時空數據的價值在各個領域逐漸凸顯，尤其在商業航空領域行業，客機使用全球定位系統(Global Positioning System, GPS)進行高頻率的信息采集產生大量的數據；同時時空數據本身具有高維度性、軌跡連續性，使時空數據在實際應用面臨查詢效率上的挑戰。

目前國內外在這個方面都有很多研究，基于B-tree，尤其是在R-tree[1]和R*-tree[2]上的變形和發展最多。這是因為對較大規模數據進行索引，如采用非平衡的樹形索引結構很難滿足查詢效率的要求，即使如此面對現有的大規模數據其依然在查詢效率上存在很大的問題。TPR-Tree[3]、TPR*-Tree[4]和HTPR*-tree[5]就是基于兩者的重要變形，它們致力于減小索引規模，同時提高索引的查找和維護效率，如TPR-Tree引入類似最小邊界矩形(Minimum Bounding Rectangle, MBR) 的速度邊界矩形(Velocity Bounding Rectangle, VBR) 的概念，用于減小索引的重疊區域進而提高查找效率，但VBR不斷地移動會增加算法的復雜性，難以滿足現在系統對實時性的要求。

同時面對海量時空數據，樹形結構的索引方法存在大量閑置的內部節點，占用了大部分的索引空間，而且存在難以用并行化方式進行索引管理的問題[6]。近些年，采用空間劃分并編碼以實現索引的思想逐漸受到重視并用于圖像空間和地理空間的檢索[7-9]，其中文獻[6]提出的D-Tree實質上是一個虛擬的無內部節點的樹，它以一定的編碼方式對包含數據的葉子節點進行編碼。D-Tree避免了對內部節點的存儲，同時也剪除了空的葉子節點，降低了存儲成本，一定程度上提高了查詢效率。然而D-Tree完全根據數據分布進行區域劃分，面對頻繁大量的數據插入時，每次都需在所有數據上重新建立索引，這在高頻寫入的實時系統中將耗費大量的時間和空間資源。

針對上述問題，本文提出了HDL-index (Hybrid spatio-temporal data indexing based on data and query-log distribution, HDL-index)索引方法。HDL-index對實時數據采用空間劃分的思想，使數據平均分布在所劃分的單元格內；同時有效利用歷史查詢記錄，將在查詢熱點區域上進行查詢的歷史記錄聚類后抽象出查詢模型，然后根據模型的坐標位置和其查詢粒度對整體查詢區域進行分割從而建立索引。最終基于GeoHash編碼進行兩部分索引的合并[10]，同時對數據采用在時間維度上的多層存儲方式進行存儲。

1 HDL-index整體思想

本文提出的索引機制結合實時數據和歷史查詢記錄兩個部分進行索引的建立。對于實時數據部分，HDL-index算法根據數據分布進行區域劃分，盡量均衡劃分得到的每個子區域所包含數據的個數，而且在區域劃分的同時對劃分得到的子區域進行GeoHash 編碼。對于歷史查詢記錄部分，HDL-index算法采用貪心策略抽象出歷史查詢記錄的代表模型[11]，然后根據這些模型的分布，將于之對應區域內默認粒度的索引單元格迭代四分到小于等于模型的粒度，本文稱之為四分基準化。同樣對得到的索引單元格進行GeoHash編碼，最終將兩部分索引合并作為新的索引待查，具體流程如圖1所示。

圖1 建立HDL-index索引流程

對于圖1中歷史查詢記錄是指在系統應用的空間范圍內進行區域查詢的記錄，而對于每一個查詢記錄對應的查詢區域本文都將其用一個能覆蓋它的最小矩形表示，以便實際應用中方便操作。

在空間數據的類型上，為了應對更加復雜的應用要求，例如對于運送危險化學物品的車輛，按照交通規定需要距離人群、住宅區、加油站一定距離行駛停放，這里就要求對整個車輛進行處理。本文將時空數據類型從點對象擴展到非零面積對象，對非零面積對象采用上面處理查詢區域的方式以矩形表示。這時考慮到數據的一致性，在處理空間點數據對象時將它當作一個矩形處理。例如：任意一個空間點PX=(x,y)，則它的矩形形式為RX=(PLL,PRU),PLL=PRU=PX(PLL為左下角坐標，PRU為右上角點坐標，下文同)，但在實際存儲時只存儲PX，這樣不但解決了數據結構不統一的問題，而且沒有占用額外的存儲空間。

按圖1中的流程最終合并得到的索引I將為下一批數據到來之前的查詢提供索引。在數據存儲方面，海量時空數據的存儲壓力大多來自數據密集區域。根據HDL-index建立的思想，在數據密集區域內，圖1中屬于Id索引的每個索引單元格的數據條數約等于按數據分布進行空間劃分時設置的每個單元格所能包含數據量的最大閾值Nmax;同時在存儲每個索引單元格包含的數據之前，需采用2個長整型記錄，分別記錄索引編碼值和數據總長度，以及用兩個時間戳存儲這些數據中的最小和最大的時間值共32個字節的標識信息，數據的實際存儲形式如圖2所示。

為了對圖2給出的數據存儲方式進行形式化的定義，假設每條數據大小為Rsize字節，每個磁盤塊大小為Bsize字節，每個磁盤頁有k個磁盤塊，則可定義用于存儲圖1中屬于Id的單個索引單元格包含數據所需的磁盤頁個數Dpage為：

(1)

圖2 數據的實際存儲形式

圖1中Id和Il兩部分索引都是對相關區域進行4等分建立起來的，但由于數據并非絕對均勻分布，因而在Id和Il合并得到I時也就不可能將Id中需要細化的單元格內的數據絕對4等分，所以可定義存儲圖1中屬于I的單個索引單元格內的數據所需磁盤頁的個數D為：

D≈Dpage/4p；p∈N

(2)

在按圖2的進行數據存儲時，對不同應用可以根據Rsize設置Bsize的大小;同時圖2所示的存儲結構為每個批次的數據分配若干個獨立的磁盤頁，將數據按時間順序進行連續存儲， 這樣可有效地解決時間維度上的查詢問題。

2 HDL-index的結構與算法

2.1 面向實時數據的索引建立

對于當前時間窗口的實時數據，本文采用空間劃分的方式，將整個二維的數據區域沿兩個維度的中線分成4個子矩形區域，然后按這種方法進行遞歸劃分，最終使每個子矩形內的數據量盡量相當。為了使每個子矩形內的數據量相近，D-tree在進行區域劃分時，需判斷區域內數據的個數，使其小于等于給定的閾值Nmax，但對于涉及多個對象的大規模實時數據系統，同一個坐標點在窗口時間內的不同時刻很可能產生多個數據。假設這個數值為nr，當nr≥Nmax時遞歸將不能完成，為此需要添加一個參數Lmin，限制子區域最小邊長。另外，由于本文將數據類型推廣到二維對象，當出現非零面積數據大面積交疊時遞歸同樣不能完成，所以需要在劃分中判斷劃分的四個子區域兩兩對角區域內的數據量較其父區域是否減少，如果兩個對角區域都未減少，則說明存在重疊區域不必再繼續劃分。具體劃分過程如算法1。

算法1 實時數據的劃分(AreaDiv)。

輸入：初始矩形Rinit,Nmax,Lmin,數據集合D,初始矩形編碼Cinit。

輸出：CRes:Tuplet=(Code,Entry-Set)。

1)

Lside← float:GetRecSide(Rinit);

2)

subRecs← QuadRec(Rinit);

3)

Define arrayDsubrecord data set in thesubRecs

exit← NumberLE(D,subRecs,Nmax,Dsub);

5)

IFLside≤Lminorexitis true THEN

6)

Add the data that contained inRinitinto Entry-SetEcurrent;

7)

Instance a newt=(Cinit,Ecurrent), add it intoRes;

8)

遠程監測平臺主要實現對集裝箱的在線管理和實時監測，遠程監測平臺采用B/S結構[14-15]，使用最新的C#技術進行開發，建立ASP.NET MVC應用程序，數據庫采用MySql[16]，根據“低耦合、高內聚”的模塊劃分原則將平臺劃分實時環境監測、實時位置監測、歷史數據查詢、歷史軌跡查詢、電子掛鎖管理等模塊。監測管理平臺界面如圖8所示。

RETURNCRes;

9)

END IF

10)

Csub←Cinit+"00";

11)

AreaDiv (subRecs[0],Nmax,Lmin,Dsub[0],Csub);

12)

Csub←Cinit+"01";

13)

AreaDiv (subRecs[1],Nmax,Lmin,Dsub[1],Csub);

14)

Csub←Cinit+"10";

15)

AreaDiv (subRecs[2],Nmax,Lmin,Dsub[2],Csub);

16)

Csub←Cinit+"11";

17)

AreaDiv (subRecs[3],Nmax,Lmin,Dsub[3],Csub);

在算法1中，調用的函數NumberLE主要是進行區域內數據個數是否小于等于Nmax的判斷，用以解決上面提到的數據位置重疊的問題。Entry-Set中每個實體都代表一個空間數據對象，具體形式為(TraID,ObjPointer)，其中TraID為空間對象一次移動過程的軌跡編號，ObjPointer指向數據地址。算法1中，在區域劃分的同時進行GeoHash編碼，GeoHash的具體編碼方式如圖3所示。

采用這樣的方式進行編碼，可以通過所提供的經緯度值快速定位到其所對應的索引編號，繼而根據其他查詢條件獲得最終結果,同時這樣的編碼方式對任意給定位置的鄰近查詢操作也是非常高效的。當所查找的相鄰區域和給定位置處于同一級別的編碼時，可直接獲取索引編碼；當兩者不在同一級別時，由于GeoHash是前綴編碼，所以依然能順利得到所要的索引編碼。

假設要查詢圖3(b)中，與索引編碼IC=1100所包含的某個空間對象相距LQ(單元格的邊長為LU，假設此時LQ=LU)的符合某些條件的空間對象。以查找IC正下方索引為例，只需取IC奇數位置上的值，與LQ/LU所得整部分值的二進制形式作二進制的減法運算，然后用所得結果替換IC對應位置的值即可得到要查找的索引編碼1001，對照圖3(b)可以看到1001正是IC正下方索引編碼。按照這樣的計算方法，結合表1給出的不同查找方位的操作列表即可求得其正上方、正左方和正右方的索引編碼。

圖3 GeoHash編碼方式示例

查詢方向涉及編碼值的位置操作(N=floor(LQ/LU))右偶數位+N下奇數位-N左偶數位-N上奇數位+N

表1中操作列中的值因二進制無法直接表述，因此采用的是十進制表述。在實際操作中需統一轉化為二進制再進行運算。對于其他四個對角線方向的鄰近查找可通過正方向間接計算出來，其中N=(2n/2-1)≤(n-1)，確保運算可正確進行。

2.2 面向歷史查詢記錄的索引建立

只面向數據通過空間劃分的方式建立索引，在每次數據更新時都需要對所有有效數據重新進行劃分。在大數據時代，面對頻繁和大量的數據更新，如果采用上述的辦法，將耗費很長的時間用于索引的建立;同時，只面向數據建立的索引只能體現數據的分布，并不一定能提供較好的查詢效果，即數據的分布和查詢的分布并不是總是一致的。在網絡拓撲等相關研究中，利用查詢記錄輔助索引建立方面國內外學者已經有不少研究[12-14]，同樣的本文將歷史查詢記錄分布作為構成索引的一部分，用以快速建立索引并提高查詢效率。

對于時空數據的查詢從空間角度可分為區域查詢和點查詢。本文將區域查詢所覆蓋的范圍用其形心代表，這樣可以將查詢統一表示為元組〈PQ,RQ〉，其中PQ為區域查詢的形心或者查詢點，RQ為查詢半徑，對于區域查詢設置其值為能覆蓋查詢區域最小正方形邊長的1/2，對于點查詢RQ=0。在面向歷史查詢記錄建立索引時，首先需要對所有PQ采用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法[15]進行聚類，使得的每個cluster內每兩個相鄰的PQ的距離不大于r(r為根據具體數據情況給定的經驗值)，這樣做的目的是為了使接下來抽象出查詢模型能盡可能大地覆蓋其代表的各個查詢區域的面積，即保證模型盡量真實。然后在對每個cluster內的元組進行模型抽象時，采用改進的DBSCAN算法獲取最近鄰點的算法依次獲取Qmodel，它是以某個確定PQ為圓心Pmodel，以r為半徑圓的外接正方形，并且能盡可能多地包含PQ。再用統計的方式獲取Qmodel中PQ對應的出現比例為prate的RQ值為Rrate。最后構造一個以Pmodel為中心，以Lc=2(Rrate+r)為邊長的正方形作為查詢代表模型，這樣在給定prate的情況下，使抽象出的模型可以覆蓋其所代表的絕大部分歷史查詢區域。這個具體過程如算法2所示。

算法2 抽象查詢代表模型(CreateModel)。

輸入：clusterTupletc=〈PQ,RQ〉集合S,r,prate。

輸出：MRes:Tupletm=(Center-Point,Side-Length)。

1)

IF the number oftcinSis equal 0 THEN

2)

RETURNMRes;

3)

END IF

4)

IF the number of〈PQ,RQ〉inSpercent is equalprateTHEN

5)

Instance a newtm=(PQ,2(RQ+r)) and add it intoMRes;

6)

RETURNMRes:

7)

END IF

8)

Create a setSrto keep rest oftcafter GreedyModel(Sr,r);

9)

Sr←S;

10)

Instance a newtm← GreedyModel(Sr,r);

11)

AddtmintoMRes;

12)

CreateModel(Sr,r);

算法2中函數GreedyModel(Sr,r)主要實現貪心策略以獲取能代表最多歷史查詢的代表模型。HDL-index將所有抽象得到的查詢代表模型記錄在Json文件中，這樣以配置文件的形式進行下面索引建立的操作，有助于索引的并行化。

在根據代表模型進行空間劃分上，首先需要根據系統設置將整個查詢區域按照2.1節的方法劃分成若干區域，作為默認查詢粒度為Ld的索引單元格。然后將所有的查詢模型對應到查詢空間上，檢查各個查詢代表模型的邊長Ld與Lc的大小關系。如果Ld>Lc，則采用2.1節的方法將相關默認粒度的索引單元格進行遞歸劃分，直至Ld≤Lc。由于劃分的思想相似，只是面向歷史查詢記錄的索引建立不涉及數據，只需要判斷Ld和Lc的關系，不需要其他限制條件，在此就不再進行累述。最后將得到的結果同樣采用GeoHash的編碼方式進行編碼，以便進行Id和Il兩部分索引的合并。

2.3 索引的合并和更新策略

2.1和2.2節完成了圖1中Id和Il兩部分索引的建立，按照HDL-index的整體思想，需要將兩部分索引合并成最終索引。由于采用同樣的編碼方式為完成合并提供了前提，在合并過程中有以下三種情況：

1)對應區域內Id和Il的編碼相同，說明它們代表完全相同的查詢區域，由于只有Id對應實際數據，只需要保留Id；

2)對應區域內Id的編碼是Il的編碼的前綴，說明Id的查詢粒度是Il的m倍(m為正整數)，這時需要將Id的編碼對應的數據，對應到以Id的編碼為前綴的Il中相應的索引區域內并保存Il；

3)對應區域內Il的編碼是Id的編碼的前綴說明Il查詢粒度較大，保存Id即可。

在合并中第2)種情況要對Id進行四分劃分，劃分后得到的索引數量必然呈4倍量級地增長，從而產生更多的索引編碼，但是Il代表查詢的熱點，所以此時小粒度的索引將大幅度提高查詢效率。由于HDL-index具有較簡單數據結構，在此是用較小空間換取了較高的時間效率。

經過上面的合并可以得到最終的索引，對于索引更新的基本策略如下：

1)在系統初始化時，由于沒有歷史查詢記錄，HDL-index只采用Id作為最終索引，等待第一批查詢記錄到來；

2)當查詢記錄到來時，按照HDL-index的思想進行索引的建立得到完整索引，然后當實時窗口數據再次到來時，停止Il的建立，只將Id與完整索引合并；

3)當步驟2)不斷合并過程中，上面合并操作第1)種情況和第3)種情況合并掉的編碼總數量，等于步驟2)中Il的編碼的數量時，回到步驟2)。

對于HDL-index基本更新策略中步驟3)觸發條件實質上是指由于數據的不同和數據整體分布的改變使得查詢熱點變化，因而目前的索引已不能很好地適應當前的查詢需求，所以需要對索引進行全部重建。由于最終索引結構與D-tree類似可采用相同的操作進行軌跡數據的刪除，具體算法可參考文獻[6]，不同的由于HDL-index采用時間分層存儲，所以可以對無時效性的數據進行批量刪除。

3 HDL-index性能評估與實驗

為了評估HDL-index的性能，本文采用國內某航空公司百萬兆字節級別的真實數據進行各項性能的測試。近數千萬條的數據分布在我國中東部地區和東南亞地區，這些數據是該航空公司采用GPS以1s為頻率采集的，實驗是針對在E114°～E116°和N21°～N23°區域內的數據進行的，大致為深圳、香港及其沿海周邊空運繁忙地區為重點實驗區域，同時經分析發現這些數據是在以邊長為1經緯度的區域內聚集分布的。

為了更清楚體現HDL-index性能的優缺點，本文選取上文提到的D-tree作為比較對象，因為兩者都采用空間編碼的方式建立索引。本文的實驗在一臺2.20GHzIntelCoreDuoCPU,2GBRAM計算上機進行，同時采用同樣數據集和相關參數設置。

3.1 索引空間性能評估

為了進行占用空間大小評估，定義了下面一系列參數以方便計算。

M：占用空間總大小；

S：總數據量

L：劃分得到的索引單元格個數；

C：索引單元格的最大容量；

p：一個指針的大小；

d：一個雙精度浮點數的大小；

i：一個整數的大小。

對于HDL-index和D-tree雖然采用不同的編碼方式，但由于都是對空間數據進行研究，兩者具有相同的索引數據形式，每個索引單元格由一個(Code,Entry-Set)元組(其中Code整數編碼；Entry-Set為數據實體集合)表示，Entry-Set中每個實體一個(TraID,ObjPointer)元組(其中TraID為整數組合編碼，由設備號和唯一時間標識組成；ObjPointer為指針，指向數據)表示。所以兩者空間占用大小M可以統一表示為：

M=L*p*(C+1)+S*(p+8*d)

(3)

在同樣的實驗數據下在表達式(3)中，兩者只有L和C兩個參數不同，本文進一步將參數C取相同值，則決定兩者占用空間大小只有參數L。由于D-tree直接采用Hash表的方式進行索引存儲，而HDL-index采用時間分層的索引存儲方式。實驗將系統置于較大壓力下運行，即每個批次的實時數據在劃分后，都能使每個索引單元格達到其最大容量C，此時在k次數據到達后，則有LD-tree=kLHDL-index，圖4展示了數據批次數(每批約100 000條數據)和索引空間的關系。

圖4 批次數與索引空間大小的關系

由于HDL-index是由Id和Il兩個部分合并得到的，而合并后的索引單元格會增加，但是由于數據量遠大于查詢記錄提取得到查詢代表的個數，合并過程中索引單元格個數只會少量增加，所以LD-tree的值會小于kLHDL-index。

3.2 時間性能評估

在索引的建立上D-tree只從數據考慮方面，通過空間劃分使得每個索引單元格內所包含的數據個數盡量均衡在Nmax左右。按照這樣策略進行索引的建立時，由于D-tree采用的是遞歸方法，所以D-tree耗費的時間t與數據量的個數是正相關的。HDL-index由于采用了在時間維度上的多層存儲結構，使得HDL-index只需要對當前窗口數據進行劃分。對于穩定系統的當前窗口數據，可以認為不同批次數據量是大致相同的，所以在HDL-index第一部分索引建立時間耗費上基本是一定的;同時由于HDL-index第二部索引只需讀取Json配置文件，然后與默認查詢粒度比較建立索引，這過程幾乎不耗費時間。所以與D-tree相比，HDL-index建立索引的時間呈大致水平狀態。圖5給出了數據量與索引建立耗費時間的關系的平均實驗結果。

由圖5可以看到，只有在數據量較少時HDL-index兩部分索引建立并合并的時間會大于D-tree。當數據量持續增大時，兩者變化趨于穩定，但由于某些批次新增數據分布情況存在較大的變化對應地導致時間上的一定變化。

圖5 數據量與索引建立耗費的時間的關系

3.3 查詢性能評估

由于HDL-index和D-tree都是采用編碼思想建立索引的，所以在設置相同的Nmax值時，兩者在一般區域查詢的效率基本一樣。只需要通過查詢條件計算出對應索引編碼，再根據其他條件進行篩選，具體可參見文獻[6]。但在熱點區域查詢方面，由于 D-tree只面向數據進行索引的建立，而HDL-index將歷史查詢記錄考慮進來，在熱點區域HDL-index根據查詢將該區域進行更細粒度的劃分，雖然會產生更多索引編碼，但是對于時空應用絕大多數的查詢都發生在熱點區域，因此熱點區域細粒度的索引不但大幅度提高該區域的查詢效率，而且也提高了系統的平均查詢效率。

對于熱點區域劃分得到索引單元格的個數和粒度，取決于抽象出的查詢代表模型的位置和查詢粒度(即模型的邊長)，而它們分別受算法2中r和prate兩個參數影響。由本章開始所給出的數據分布和聚集特點，實驗在所提到的相對較小的數據密集區域生成10 000個窗口查詢，這些查詢的查詢半徑在0.053 75～0.515 57,同時經分析發現數據聚集區域間隔在0.2經緯度左右，所以r的取值要小于0.2以保證每個聚類在同一個數據聚集區域內完成，具體r和prate對熱點區域抽象模型的兩方面影響如圖6所示。

圖6 不同參數情況下查詢模型的抽取情況

由圖6中橫向子圖間對比可以發現，prate只影響模型的查詢邊長，當r值相同時，模型的位置和每個模型覆蓋的查詢個數相同(r=0.08時，模型個數為77；r=0.04時，模型個數為183);同時,由圖6中縱向子圖間對比可以發現r影響模型所覆蓋的查詢個數，此時在相同prate位置上的半徑也因為其所覆蓋的查詢記錄集合不同而不同，而本文使用貪心的方法去選取中心點，這種方法只關注所覆蓋的查詢數量，所以在實際實驗結果中對應模型的位置也有稍微的偏移。

根據上面的分析，只要r<0.2時就能得到合理的模型，但是實驗證明r值與最終得到的模型個數成反比，所以要根據應用數據設置r的大小，本文選取r=0.08和prate=0.75以進行下面的熱點區域的查詢實驗，根據數據分布設置Lmin=1，同時由于數據覆蓋率較大結合實際劃分發現將Nmax設置為數據總量的8%左右時，能保證數據較好地平均到各個索引單元格內，然后進行不同熱點區域查詢實驗得到平均查詢時間，具體實驗結果如圖7所示。由圖7可以看出，HDL-index的查詢性能明顯優于D-tree。這是由于選擇圖6(b)的設置進行歷史查詢的模型生成，獲得模型的查詢粒度在0.1～0.92，而本文設置Lmin=1，最終使得HDL-index在相關熱點區域的查詢粒度比D-tree精確了2～16倍，同時對于熱點區域查詢數據量越大HDL-index的查詢性能優勢明顯。

圖7 熱點區域查詢耗費時間與數據量之間的關系

4 結語

本文在已有的索引思想上，對大規模時空數據的索引進行了研究。HDL-index的提出將目前在研究時空索引上所忽略的查詢記錄，這一現成且具有實際意義的數據考慮進來，解決了已有時空索引方式存在的空間浪費和熱點區域查詢效率低的問題。本文經過理論分析和實驗證明了HDL-index的可行性和有效性，但在處理大規模移動時空數據的軌跡相似性查詢時還有較大不足。對此下一步準備引入超圖對索引編碼進行組織，以便能更好地處理這類查詢， 同時超圖的引入也能更加清晰直觀地展示不同軌跡之間的關系。

致謝 在這里由衷地感謝清華大學數據科學研究院——工業大數據研究中心陸薇常務副主任提供的良好交流學習環境和實驗設備，也特別感謝中心張碩博士在選題和研究過程中精心指導及建議。

)

[1]GUTTMANA.Adynamicindexstructureforspatialsearching[J].ACMSIGMODRecord, 1984, 14(2): 47-57.

[2]BECKMANNN,KRIEGELH-P,SCHNEIDERR,etal.TheR*-tree:anefficientandrobustaccessmethodforpointsandrectangles[J].ACMSigmodRecord, 1990, 9(2): 322-331.

[3]BOKKS,YOONHW,SEODM,etal.Indexingofcontinuouslymovingobjectsonroadnetworks[J].IEICE—TransactionsonInformationandSystems, 2008,E91-D(7): 2061-2064.

[4]TAOY,PAPADIASD,SUNJ.TheTPR*-tree:anoptimizedspatio-temporalaccessmethodforpredictivequeries[C]//Proceedingsofthe29thInternationalConferenceonVeryLargeDataBases.Berlin:VLDBEndowment, 2003, 29: 790-801.

[5]FANGY,CAOJ,WANGJ,etal.HTPR*-tree:anefficientindexformovingobjectstosupportpredictivequeryandpartialhistoryquery[C]//Web-AgeInformationManagement,LNCS7142.Berlin:Springer, 2012: 26-39.

[6]HEZ,WUC,LIUG,etal.Decompositiontree:aspatio-temporalindexingmethodformovementbigdata[J].ClusterComputing, 2015, 18(4): 1481-1492.

[7] 陳建華,王衛紅,苗放.基于Ex-Dewey前綴編碼與R樹的GML空間數據索引機制[J].地球信息科學學報,2010,12(2):186-193.(CHENJH,WANGWH,MIAOF.GMLspatialdataindexmechanismbasedonEx-DeweyprefixencodingandR-tree[J].JournalofGeo-InformationScience, 2010, 12(2): 186-193.)

[8] 駱歆遠,陳剛,伍賽.基于GPU加速的超精簡型編碼數據庫系統[J].計算機研究與發展,2015,52(2):362-376.(LUOXY,CHENG,WUS.AGPU-acceleratedhighlycompactandencodingbaseddatabasesystem[J].JournalofComputerResearchandDevelopment, 2015, 52(2): 362-376.)

[9]LIY,WANGH.Spatialindexstudyformulti-dimensionvectordatabasedonimprovedquad-treeencoding[EB/OL]. [2016- 02- 09].http://xueshu.baidu.com/s?wd=paperuri%3A%2836fe3b793cc15fbceb06230d1c65a4b4%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fproceedings.spiedigitallibrary.org%2Fproceeding.aspx%3Farticleid%3D790968&ie=utf-8&sc_us=16220466832006650551.

[10] 金安,程承旗,宋樹華,等.基于Geohash的面數據區域查詢 [J].地理與地理信息科學,2013,29(5):31-35.(JINA,CHENGCQ,SONGSH,etal.Regionalqueryofareadatabasedongeohash[J].GeographyandGeo-InformationScience, 2013, 29(5):31-35.)

[11]GUDMUNDSSONJ,LEVCOPOULOSC,NARASIMHANG.Improvedgreedyalgorithmsforconstructingsparsegeometricspanners[J].SIAMJournalonComputing, 2002, 31(5): 1479-1500.

[12]BAEZA-YATESR,SAINT-JEANF.Athreelevelsearchengineindexbasedinquerylogdistribution[M]//StringProcessingandInformationRetrieval,LNCS2857.Berlin:Springer, 2003:56-65.

[13]LAMHT,PEREGOR,SILVESTRIF.Onusingquerylogsforstaticindexpruning[C]//Proceedingsofthe2010IEEE/WIC/ACMInternationalConferenceonWebIntelligenceandIntelligentAgentTechnology.Washington,DC:IEEEComputerSociety, 2010: 167-170.

[14]GURAJADAS,SREENIVASAKP.Indextuningforquery-logbasedon-lineindexmaintenance[C]//Proceedingsofthe20thACMConferenceonInformationandKnowledgeManagement.NewYork:ACM, 2011: 1997-2000.

[15]ESTERBM,KRIEGELHP,SANDERJ,etal.Adensity-basedalgorithmfordiscoveringclustersinlargespatialdatabaseswithnoise[EB/OL]. [2016- 02- 05].http://www.dblab.ntua.gr/～gtsat/collection/dbscan.pdf.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61502106),theRegionalSpecialMajorScienceandTechnologyProjectofFujianProvince(2014H4015).

MENG Xuechao, born in 1989, M.S. candidate. His research interests include large data storage and processing, spatio-temporal database index optimization.

YE Shaozhen, born in 1963, Ph. D., professor. Her research interests include intelligent analysis and processing of medical information, E-commerce.

New spatio-temporal index method based on real-time data and query log distribution

MENG Xuechao1, YE Shaozhen1,2*

(1.CollegeofMathematicsandComputerScience,FuzhouUniversity,FuzhouFujian350108,China; 2.FujianKeyLaboratoryofMedicalInstrumentationandPharmaceuticalTechnology,FuzhouFujian350002,China)

In the era of large data, the data has the characteristics of large volume, obvious spatio-temporal complexity, high real-time requirement, and etc. However, the traditional method of indexing large-scale spatio-temporal data based on tree structure has the problem of low utilization of storage space and low efficiency of query. In order to solve this problem, a new method named HDL-index was proposed to establish the spatio-temporal index based on the distribution of data and historical query records. On the one hand, the whole area was partitioned based on the spatial distribution of the data. On the other hand, taking into account the continuity of query, the query-models were obtained after density-based clustering on historical query objects, and then based on the model coordinates and query granularity of the overall query area segmentation, the two indexes were merged based on their GeoHash codes, and finally the optimal index coding was obtained. HDL-index takes better account of the data distribution and users’ queries, making the index on the frequent query area more refined. Compared with the efficiency of the similar method, the efficiency of the index creation is improved by 50%, and the query efficiency of the hotspot region can be increased by more than 75% when the data is evenly distributed in the real aeronautical data set.

spatio-temporal index; big data; GeoHash encoding; density clustering; hotspot region query

2016- 08- 15;

2016- 10- 03。

國家自然科學基金資助項目 (61502106)；福建省區域重大科技專項資助項目 (2014H4015)。

孟學潮(1989—),男,河南駐馬店人,碩士研究生,主要研究方向:大數據存儲與處理、時空數據庫索引優化； 葉少珍(1963—),女,福建福州人,教授,博士,CCF高級會員,主要研究方向:醫學信息智能分析與處理、電子商務。

1001- 9081(2017)03- 0860- 06

10.11772/j.issn.1001- 9081.2017.03.860

TP

A