孟學潮 ，葉少珍,2

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

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

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

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

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

時空索引；大數(shù)據(jù)；GeoHash編碼；密度聚類；熱點區(qū)域查詢

0 引言

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

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

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

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

1 HDL-index整體思想

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

圖1 建立HDL-index索引流程

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

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

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

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

(1)

圖2 數(shù)據(jù)的實際存儲形式

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

D≈Dpage/4p；p∈N

(2)

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

2 HDL-index的結構與算法

2.1 面向實時數(shù)據(jù)的索引建立

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

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

輸入：初始矩形Rinit,Nmax,Lmin,數(shù)據(jù)集合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)

遠程監(jiān)測平臺主要實現(xiàn)對集裝箱的在線管理和實時監(jiān)測，遠程監(jiān)測平臺采用B/S結構[14-15]，使用最新的C#技術進行開發(fā)，建立ASP.NET MVC應用程序，數(shù)據(jù)庫采用MySql[16]，根據(jù)“低耦合、高內(nèi)聚”的模塊劃分原則將平臺劃分實時環(huán)境監(jiān)測、實時位置監(jiān)測、歷史數(shù)據(jù)查詢、歷史軌跡查詢、電子掛鎖管理等模塊。監(jiān)測管理平臺界面如圖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中，調用的函數(shù)NumberLE主要是進行區(qū)域內(nèi)數(shù)據(jù)個數(shù)是否小于等于Nmax的判斷，用以解決上面提到的數(shù)據(jù)位置重疊的問題。Entry-Set中每個實體都代表一個空間數(shù)據(jù)對象，具體形式為(TraID,ObjPointer)，其中TraID為空間對象一次移動過程的軌跡編號，ObjPointer指向數(shù)據(jù)地址。算法1中，在區(qū)域劃分的同時進行GeoHash編碼，GeoHash的具體編碼方式如圖3所示。

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

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

圖3 GeoHash編碼方式示例

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

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

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

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

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

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

2.3 索引的合并和更新策略

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

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

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

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

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

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

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

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

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

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

3 HDL-index性能評估與實驗

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

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

3.1 索引空間性能評估

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

M：占用空間總大??；

S：總數(shù)據(jù)量

L：劃分得到的索引單元格個數(shù)；

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

p：一個指針的大??；

d：一個雙精度浮點數(shù)的大??；

i：一個整數(shù)的大小。

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

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

(3)

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

圖4 批次數(shù)與索引空間大小的關系

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

3.2 時間性能評估

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

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

圖5 數(shù)據(jù)量與索引建立耗費的時間的關系

3.3 查詢性能評估

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

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

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

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

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

圖7 熱點區(qū)域查詢耗費時間與數(shù)據(jù)量之間的關系

4 結語

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

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

)

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

[8] 駱歆遠,陳剛,伍賽.基于GPU加速的超精簡型編碼數(shù)據(jù)庫系統(tǒng)[J].計算機研究與發(fā)展,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的面數(shù)據(jù)區(qū)域查詢 [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)；福建省區(qū)域重大科技專項資助項目 (2014H4015)。

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

1001- 9081(2017)03- 0860- 06

10.11772/j.issn.1001- 9081.2017.03.860

TP

A