馮 鈞，李頂圣，陸佳民，張立霞

(河海大學計算機與信息學院，南京211100)(* 通信作者電子郵箱 jiamin.luu@hhu.edu.cn)

0 引言

隨著智能定位設備的不斷發(fā)展，路網移動對象數據量呈現指數級的增長趨勢。此外，路網移動對象數據具有對象沿路網運動、數據在不同的路段中分布不均等特點。傳統(tǒng)的關系型數據庫已經無法滿足海量路網數據的存儲需求，HBase作為一種分布式的數據庫系統(tǒng)，數據以key/value的形式進行存儲，有效解決了海量數據的存儲低效問題，但HBase缺少高效路網環(huán)境下的時空索引。

為了彌補原生HBase針對時空對象高效索引機制的不足，近幾年提出的具有代表性的索引研究主要有兩種:可擴展的基于位置服務的數據管理系統(tǒng)——MD-HBase(Multidimensional Data HBase)［1］和 時 空 HBase 索 引 (Spatial-TEmporal HBase IndeX，STEHIX)框架［2］。MD-HBase是文獻［1］提出的索引框架，相比原生的HBase能夠顯著提高海量時空數據的查詢性能，但是由于只在上層創(chuàng)建索引，未考慮在存儲層創(chuàng)建索引，其性能提高有限。針對這一問題，文獻［2］在MD-HBase的結構上進行改進提出了STEHIX索引框架，主要用于提高時空數據的范圍查詢和 KNN查詢的查詢效率。與MD-HBase相比，STEHIX索引框架因為在存儲層創(chuàng)建了一維索引，因此對時空數據的查詢效率有很大提升。上述兩種索引框架在應用到路網環(huán)境下的時空數據索引當中時，依然存在以下幾方面的問題:利用常見的等大小的空間劃分方法，如四叉樹［3］或者 kd-tree［4］的空間劃分方法，在對空間對象的查詢過程中會出現“死空間”問題;由于在不同路段中車流量信息是分布不均的，采用均衡的子空間分配算法可能會導致集群節(jié)點的熱點問題，從而造成服務器的存儲壓力;原生的HBase只支持基于Rowkey鍵的查詢、基于Rowkey區(qū)間的范圍查詢和全表掃描，不能支持復雜的多條件查詢。而STEHIX索引框架并沒有考慮Rowkey鍵設計對索引的影響，同時STEHIX應用于路網的性能有待提高。

針對STEHIX處理路網環(huán)境移動對象時空索引存在的數據熱點分布、空間劃分“死空間”等問題與不足，本文在HBase存儲結構的基礎上設計并實現了一種高效的路網移動對象HBase索引框架(HBase indexing framework for Road network Moving objects，RM-HBase)，通過對原生HBase索引結構的上層Hmaster進行改進，解決分布式集群數據的熱點分布問題;通過提出空間對象索引RN-tree(Road Network tree)，解決空間劃分中的“死空間”問題，提高了路網環(huán)境下的空間檢索效率;同時通過對原生Hbase的 RowKey值進行設計及下層HRegion進行索引提高路網時空數據的索引性能。

1 RM-HBase索引框架

1.1 索引框架

1.1.1 路網時空數據定義

路網移動對象數據是時空數據的一種特殊環(huán)境下的子類，數據包括一維時間和二維空間共三個維度。對路網時空數據進行定義是進行索引框架研究的基礎，其中數據包括兩種類型:空間路網數據和移動對象數據，本文對每種數據的定義如下。

1)空間路網數據。

本文研究的空間路網數據包括橫坐標和縱坐標兩個維度，移動對象(如車輛等)沿著路網中的路段在空間中運動，因此對移動對象的位置定義包括兩個維度。本文采用路段模型［5］對路網建模，路網中的基本元素為路段。模型創(chuàng)建后生成路網圖，其中:圖中頂點的集合表示兩個路段之間的交叉點;圖中的邊集合表示實際的路段。每條路段采用兩個頂點作為唯一性編碼標識。

2)移動對象數據。

移動對象數據是由路網中的移動對象(車輛等)隨時間運動而產生的數據，也就是最終存儲在集群節(jié)點中的數據。該類數據是一種時空數據，數據按條存儲在HBase的用戶表中，每條移動對象數據記錄的屬性如表1所示。

本文的分布式數據庫HBase表用于存儲路網中的移動對象數據，HBase數據庫中只存儲一張移動對象數據表:MoveObject。HBase的Region中Store數量與列簇的個數相對應，為了避免出現不同Region中的數據熱點問題，同時降低每個Region初始化時創(chuàng)建Store的代價，每張表中只設計一個列簇:objectinfo，該列簇下包括五部分屬性:移動對象標識oid、道路標識rid、經度信息pos_x、緯度信息pos_y和時間time。在MoveObject數據表中的定義形式分別是:objectinfo:oid、objectinfo:rid、objectinfo:pos_x、objectinfo:pos_y 和 objectinfo:time。此外，表中的時間戳TimeStemp屬性用于記錄數據的版本。

表1 MoveObject表的結構Tab.1 Structure of MoveObject table

1.1.2 RM-HBase 的結構

RM-HBase是本文提出的一種用于解決海量路網移動對象數據高效索引問題的新型框架，該框架基于Hbase的內部存儲結構對索引過程加以改進。將HBase劃分為上下兩層:上層包括ZooKeeper和HMaster，是數據的管理層，主要通過.ROOT表和.META 表實現關系映射索引［6］;下層包括HRegionServer，是數據的存儲層，通過Region實現數據存儲。新框架的設計思想受STEHIX索引框架啟發(fā)，結合路網環(huán)境中的數據特點，對原生HBase存儲結構作了如下三個方面的優(yōu)化:

1)設計路網空間索引RN-tree以提高索引效率，空間路網數據存儲在HMaster中的內存區(qū)域中，索引的創(chuàng)建過程包括兩個階段:空間路網劃分和RN-tree的創(chuàng)建。RN-tree是一棵多路徑平衡搜索樹。

2)基于HBase上層的索引結構設計。上層索引設計的改進包括對.META表中的存儲內容重新設計映射關系和根據路段歷史數據分布情況設計路段分配算法兩個方面，然后將所有路段數據映射到不同的Region和HRegionServer，解決數據的熱點分布問題，同時利用分布式框架的分布式查詢機制顯著提高查詢效率。

3)基于HBase下層的索引結構設計。同一路段中的移動對象數據被存儲到同一塊Region中，在每個Region中的改進包括兩部分:首先是設計 Rowkey鍵的組成結構，通過Rowkey鍵高效地組織數據記錄的存儲順序;其次是在Region中創(chuàng)建多重索引，提高移動對象數據在Region內的索引效率。

RM-HBase的結構框架如圖1所示。

1.2 基于原生HBase的結構改進

1.2.1 上層索引結構設計

為了解決數據熱點問題同時提高路網空間對象的查詢效率，本文對.META表內部的映射關系進行了改進，同時引入了歷史數據計算路段概率的方法對路段到Region進行分配。本小節(jié)主要對路段衡量指標和路段分配算法兩部分進行介紹。

1)計算路段衡量指標。

本文利用每條路段的歷史數據積累情況將路網中的路段分配到不同集群節(jié)點的服務器HRegionServer和Region中進行存儲，從而確保數據在不同集群節(jié)點中的負載均衡，解決集群節(jié)點的數據熱點問題。路段分配算法根據統(tǒng)計學原理，以查詢地區(qū)的一周(從周一到周日)數據記錄作為分配依據對歷史移動對象數據記錄數量進行統(tǒng)計，選用一周數據作為分配依據的原因是:根據文獻［7］對長期統(tǒng)計數據的研究發(fā)現，車流量數據隨一周變化出現周期的波動走勢。

圖1 RM-HBase結構框架Fig.1 Structural framework of RM-HBase

其中:i，j分別表示每條路段的兩個頂點標號;pij代表路段vivj所占的比重是本文的目標值;totalij代表路段vivj在上述一周內的移動對象數據總量;N表示查詢區(qū)域內的路段總數;totalij代表查詢區(qū)域中一周內的所有路段中產生的移動對象數據總量。

對所有查詢地區(qū)的所有路段都利用式(1)計算比值pij，最終得到一個由所有路段pij值組成的二維鏈表。鏈表節(jié)點的數據部分包括兩部分:路段編碼和路段的衡量指標pij。按照pij從大到小對路段進行排序，其中鏈表的首節(jié)點存儲pij值最大的路段信息，最終得到按pij排序的有序鏈表rlist。下面介紹利用如何利用路段分配算法將路段rlist分配到不同的Region和HRegionServer當中。

2)路段分配算法。

路段分配算法的實現思路是在已知HBase集群節(jié)點(即HRegionServer)個數k的情況下，將rlist中的所有路段分成k個子類，使得每個子類中包含的路段對應的概率之和差異最小。路段分配算法主要分為兩步進行:第一步是將路段分成k個子類;第二步是將k類中的每條路段根據路段編碼分配到不同的Region中。第一步的路段劃分算法的主要思想如下:首先設置k個空桶并對桶從0，1，…，k－1編號，將rlist中的元素按照pij值的大小，從大到小循環(huán)所有的桶，將路段依次存

本文采用的衡量標準的計算方法如式(1):放到k個桶中。例如:第一次循環(huán)將rlist［0］ ～ rlist［k－1］依次存放到桶0～k－1中。隨后，繼續(xù)判斷k個桶中當前所有路段pij值和的大小情況，確定和最小的一個桶，將下一個值rlist［k］存放到該桶中。算法的結束條件是rlist中的元素循環(huán)完畢，最終返回所有路段的分配結果列表bucketlist，該列表中存儲的是路段。根據上述分類結果，將k個桶中的路段分別存儲到對應的HRegionServer中。路段分配算法的具體執(zhí)行過程如算法1，算法1中涉及的findminbucket算法執(zhí)行過程如算法2所示。

算法 1 RoadSegDistribution()。

輸入 有序的路段對應概率數組rlist，路段劃分的類別個數k;

輸出 返回k臺服務器存儲的路段集合bucketlist。

bucketNum=k; //桶數

buckets=new LinkedList〈int〉(); //創(chuàng)建鏈表集合

for each bucketNum i do //初始化桶

buckets［i］.add(rlist［i］.value);//先將 rlist中0，1，…，k － 1元素加入桶中

end for each

bucketsum=0; //記錄每個桶的數據和

LinkedList〈LinkedList〈int〉〉bucketlist=newLinkedList

〈LinkedList〈int〉〉(); //存儲最終的路段分配結果，此外，//將0～k－1條路段加入bucketlist

for each rlist i do

int min=findminbucket(buckets); //確定和最小的桶

buckets［min］+=rlist［i］; //更新最小值

bucketlist.get(min).add(rlist［i］.rid); //加入 bucketlist

end for each

return bucketlist

算法2 findminbucket()。

輸入 鏈表集合buckets;

輸出 返回pij和最小的同的索引。

min=MAX; //初始化最小值為MAX

minIndex=0; //初始化最小值下標為0

for each buckets i do

if buckets［i］ ＜ min then

min=buckets［i］; //循環(huán)每個桶，找到 pij和最小的桶

minIndex=i;

end for each

return minIndex

算法1對路段的分配能夠解決集群節(jié)點的數據熱點問題。

1.2.2 下層索引結構設計

本文針對HRegionServer的內部數據存儲結構，在每個HRegionServer中進行了兩方面的索引改進，以提高數據在Region內的查詢效率。兩方面的改進分別是:創(chuàng)建Region索引和設計Rowkey鍵，下面分別對兩部分的改進進行說明。

1)創(chuàng)建Region索引。

本文在HRegionServer的每個Region中分別創(chuàng)建兩個索引:時間索引t-index和移動對象索引o-index，分別用于提高時間屬性的查詢效率和移動對象的查詢效率。時間索引t-index創(chuàng)建在時間屬性 objectinfo:time上，移動對象索引o-index創(chuàng)建在對象屬性objectinfo:oid上。

本文提出的索引是一種多重索引。上層索引相當于主索引，創(chuàng)建在.META表中，通過表中的映射關系確定每條路段的起始存儲地址。o-index和t-index相當于附加索引。創(chuàng)建索引時，以移動對象和時間作為次關鍵碼，分別創(chuàng)建兩個鏈式索引用以索引時間和移動對象。圖2是對移動對象索引的鏈表結構，左側存儲次關鍵碼信息和對應關鍵碼的頭指針，右側的鏈表是將存儲有次關鍵碼的記錄，按照時間順序連接在一起;每個鏈表節(jié)點中存儲的是該記錄的存儲地址。t-index結構與o-index的索引結構相類似，此關鍵碼是時間區(qū)間，鏈表頭指針指向的是按照時間的先后順序排列的移動對象記錄。在對移動對象進行查詢時，首先查詢左側的表，判斷移動對象是不是位于當前的塊中，如果當前塊中包含該移動對象則繼續(xù)通過對應記錄的頭指針查找該移動對象的所有記錄;如果當前塊中不含有待查詢的移動對象數據，則將放棄對該塊的查詢，這種索引的設計能夠有效地提高移動對象數據的查詢效率。在進行時間查詢時，過程與上述過程類似:首先通過此關鍵碼判斷候選Region中是否存在待查詢的時間區(qū)間，如果不存在則放棄在該塊內的繼續(xù)查詢，如果存在則通過頭指針查詢當前時間區(qū)間內的鏈表信息，找到所有滿足時間的候選記錄集合。

2)設計Rowkey鍵。

HBase表中的數據基于行鍵進行存儲。在進行Rowkey鍵設計時要充分拉開不同Rowkey鍵的差異性。通過設計Rowkey鍵提高HBase的查詢效率，在文獻［8］和文獻［7］中已經得到了成功的應用。根據HBase表數據按照字典序排序的原則，本文對表中Rowkey鍵的設計內容如式(2):其中:rid是路段的標識id;T表示移動對象記錄的存儲時間;oid是移動對象的id?；谝陨系腞owkey設計，數據首先按照路段存儲，其次按照時間屬性進行存儲，最后依照移動對象進行存儲。

圖2 o-index索引結構Fig.2 Index structure of o-index

當查詢條件到來時，首先匹配路段rid，如果路段id匹配。系統(tǒng)首先沿當前Region查找當前路段的入口地址，由于數據首先是按照所在的路段進行存儲的，因此上述Rowkey設計能夠極大地提高路段起始存儲地址的定位速度。其次匹配條件中的時間范圍，最后再考慮移動對象oid。這種Rowkey設計的優(yōu)點在于:在每個Region的StoreFile中同一路段的移動對象時空數據被連續(xù)存儲在一起，查詢時只需要確定當前StoreFile的首地址和下一個連續(xù)StoreFile的首地址就能夠判斷當前塊中是否存儲了所有當前路段，從而直接獲取所有的當前路段數據。此外同一條路段的數據，按時間進行連續(xù)存儲，這種設計方式能夠提高索引的創(chuàng)建效率，通過上述Rowkey設計能夠快速獲取連續(xù)時間段的數據集合和滿足移動對象條件的記錄集合。

1.3 路網索引RN-tree設計

1.3.1 RN-tree結構設計

本文提出的RM-HBase索引框架中包括兩層索引機制:上層是RN-tree用于檢索待查詢對象的空間信息;下層采用鏈表組成的一維索引o-tree和t-tree索引用于檢索時間和對象屬性。本小節(jié)介紹的正是上層的RN-tree索引的結構，該索引的創(chuàng)建目的是希望通過該索引提高空間路段的查詢效率。

通過按路段的路網劃分方法解決等大小的空間劃分方法出現的“死空間”問題;通過在中間節(jié)點中存儲范圍、葉子節(jié)點存儲路段的索引設計，在實現范圍查詢的同時實現對空間的降維［9］。索引的創(chuàng)建包括三個階段:路網建模、路網劃分和RN-tree創(chuàng)建。路網建模是以路段作為最小單位對路網空間進行建模，路網空間最終被轉換成圖結構，圖中頂點代表路段與路段之間的拐點;路網劃分是根據圖的路段數量對路網空間進行劃分，中間節(jié)點存儲一個空間范圍，葉子節(jié)點存儲路段信息，子路網的劃分見1.3.2節(jié);RN-tree是一棵多層次搜索樹，葉子節(jié)點的存儲范圍的并集是父節(jié)點的存儲范圍，RN-tree的創(chuàng)建過程見 1.3.3 節(jié)。

1.3.2 路網空間劃分算法

RN-tree中路網劃分的最小單位為路段，將整個空間路網區(qū)域根據路段劃分成多個子區(qū)域［10］。劃分過程借鑒G-tree［11］的劃分思想:劃分過程包括兩個參數f和n，參數f表示樹的中間節(jié)點的孩子節(jié)點個數，參數n表示最小子圖中包含的最大路段條數。假設當前任意最小子圖包含的元素個數為count，則當圖的劃分滿足count≤n時，路網劃分過程結束。n在路網劃分算法中作為算法的一個輸入，該值的大小根據用戶的需求由用戶進行自定義設置。本文采用改進的Kernighan-Lin算法［12］對路網進行劃分。

算法3是路網的劃分算法，該算法的思想是將當前路網一分為二。首先對初始狀態(tài)的路網區(qū)域以路段為單位進行隨機劃分，隨后通過不斷交換兩個子區(qū)域中的路段，使得最終兩個子圖的代價差最小，此時對路網的劃分結束。

算法3 RoadNetworkPartition()。

輸入 G(V，E)，G表示待劃分的圖，f表示孩子節(jié)點數，n表示子圖中最大元素個數;

輸出 f個劃分后的子圖graphset，該過程是一個迭代的過程。

graphset=initializeGraph(G，f，n);

//將圖G隨機劃分成兩個子圖(A1，B1)

do //循環(huán)gset中的每個子圖中的邊界A1=A，B1=B;

//計算每個節(jié)點的內部和外部代價g=internalcost+externalcost

for each|V|/2 i do //循環(huán)每個子圖中的節(jié)點

int maxmal=0;

g［i］ =d［a［i］］ +d［b［i］］ － 2*c［a［i］］［b［i］］;

//計算每個頂點i的權重和

if g［i］ ＞ maxmal then

maxmal=g［i］;

//找到 g［i］值最大的兩個路段 a［i］和 b［i］

end if

a［i］→ B1，b［i］→ A1; //分別交換 a［i］和 b［i］到 B1和 A1

UpdatedValue(graphset，a［i］，b［i］);

//更新交換后兩個子圖的d值

end for each

int k=FindK(g［i］)

//找到 g［1］，g［2］，…，g［k］，其中 g［k］是 g［i］中的最大值

if g［k］ ＞ 0 then

a［1］，a［2］，…，a［k］ ［1］，b［2］，…，b［k］;

end if

return graphset

上述算法是將區(qū)域一分為二的劃分方法，當需要將區(qū)域劃分為2n(其中n＞1)個子圖時，繼續(xù)采用算法3中的方法進行迭代劃分。對路網的劃分方法與等空間的劃分方法相比，能夠有效避免將一條路段切分成多段的情況，為高效的路網空間對象查詢奠定了基礎。

1.3.3 RN-tree 結構設計

RN-tree是一棵多路徑平衡搜索樹，樹中存在兩種節(jié)點:中間節(jié)點和葉子節(jié)點。如圖3是f=2，n=4的RN-tree結構示意圖。索引中將整個路網空間作為根節(jié)點G0。利用1.3.2小節(jié)提出的路網劃分算法，對路網區(qū)域進行劃分。例如，首先將根節(jié)點G0覆蓋的范圍被劃分成兩個子區(qū)域G1和G2，根據路段對路網空間繼續(xù)劃分，最終將所有路段劃分到索引中的葉子節(jié)點當中，下面分別對中間節(jié)點和葉子節(jié)點的內部結構進行介紹。

中間節(jié)點存儲兩部分數據:孩子子圖的子圖邊界和當前子圖的覆蓋范圍。每個圖的子圖個數為f，為了記錄f個子圖兩兩之間的子圖邊界信息，通過鏈表結構存儲子圖邊界數據。鏈表的數據部分分為兩部分:分別存儲兩個路段頂點的編號和兩個頂點的位置信息。編號的存儲位置存在前后差別，前部分編號表示當前頂點存儲在左側子圖中、后部分編號表示當前頂點位于右側子圖中，其中每條子圖邊界指向.META表中的一行記錄的地址。根據中間節(jié)點包含的路段的最小外界矩形的四個頂點確定中間節(jié)點在兩個平面維度上的范圍。

圖3 RN-tree索引結構Fig.3 Index structure of RN-tree

葉子節(jié)點存儲最終的路段數據。葉子節(jié)點存儲兩部分信息:路段的空間范圍和路段的頂點信息。利用兩個頂點vi(x1，y1)，vj(x2，y2)的位置信息，確定路段的空間范圍。當子路網中的路段數滿足count≤n時，路網劃分過程停止，葉子節(jié)點中的元素來自當前子路網中的路段元素。每個葉子節(jié)點存儲一個路段，該葉子節(jié)點中存儲該路段的最小外接矩形的對角線信息，也就是該路段的頂點信息。最終，每個葉子節(jié)點指向.META表中的一行記錄，該記錄就是路段到Region及HRegionServer的映射信息。

RN-tree創(chuàng)建在空間路網數據上，RN-tree存儲在HMaster的內存當中。在進行時空查詢時，系統(tǒng)首先通過RN-tree確定查詢條件中的空間范圍路段集合rset，根據索引的查詢結果確定HMaster中的.META表定位該路段中數據的存儲位置;其次通過.META表的映射關系確定當前路段中的移動對象存儲的Region和HRegionServer信息，利用Region內的時間索引和對象索引進一步提高篩選對象和時間信息的效率;最終利用數據記錄的空間信息pos_x和pos_x，精確定位移動對象的記錄。由于RN-tree的中間節(jié)點存儲了范圍信息，葉子節(jié)點存儲的是對應的路段，在查詢的最后通過RN-tree將多維的范圍信息轉換成了一維的路段編碼，因此與STEHIX相比，RN-tree相當于代替了四叉樹和Hilbert曲線兩部分的功能，能夠同時實現空間對象查詢和空間降維工作。

2 路網時空查詢算法

2.1 時空范圍查詢

1)查詢類型定義。

路網中的時空范圍查詢主要有兩種類型:基于范圍覆蓋的查詢和基于路徑覆蓋的查詢?；诜秶采w的查詢指查詢范圍是一個矩形區(qū)域或者圓形區(qū)域，基于路徑覆蓋的范圍查詢指查詢范圍是多條完整的路段。本文首先介紹基于范圍覆蓋的查詢，基于范圍覆蓋的查詢定義如下:

定義1 給定路網G(V，E)，查詢條件包括矩形覆蓋范圍(［x1，x2］，［y1，y2］) 和時間區(qū)間［ts，te］兩部分。查詢結束后返回在時間區(qū)間［ts，te］內經過區(qū)域(［x1，x2］，［y1，y2］) 的所有移動對象記錄。

2)查詢算法實現。

基于范圍覆蓋的查詢算法的查詢過程包括三個子過程:可以簡要概括為“空間 時間 空間”。第一個“空間”是利用RN-tree索引當前查詢范圍覆蓋的所有路段，這個過程是一個空間的模糊查詢過程;“時間”是利用RM-HBase下層的時間索引t-index選出滿足查詢時間區(qū)間的記錄，第二個“空間”是利用HBase的字典序排序特點和Rowkey鍵的設計，對候選集內的記錄再次進行空間位置篩選。

基于范圍覆蓋的范圍查詢算法實現過程如算法4所示。

算法4 RangeQuery()。

輸入 范圍查詢區(qū)間(［x1，x2］，［y1，y2］)，時間區(qū)間［t1，

t2］;

輸出 符合查詢條件的移動對象集合。

rset=searchRoadTree(RR，x1，y1，x2，y2);//查找RN-tree確定查詢范圍內的所有路段，//其中RR是RN-tree的根節(jié)點

rslist=getMetaTable(rset);

//定位路段對應的Region和HRegionServer地址

Map(roadID，HRegionServer，rlist);

//利用MapReduce將候選集中的路段查詢任務分配到

//對應的HRegionServer和Region中并行執(zhí)行

for each rslist.HRegionServer do //所有 HRegionServer并行運行

startRowkey=getThisRowkey(rslist.roadID)

//獲取每個路段的起始存儲地址

endRowkey=getNextRowkey(rslist.roadID)

//查詢下一路段的起始地址Rowkey

scan.setStartRow(startRowkey);

scan.setStopRow(endRowkey);

//利用scan函數得到當前路段的候選集合

for each scan.result do

if t1≤ r.getTimeStemp≤ t2

＆＆ r.pos∈ (x1，y1，x2，y2)then

molist.Add(r);

end if

end for each

end for each

olist=ReduceRecord(roadID，molist);

//利用Reduce將不同服務器的結果合并

return olist //返回滿足條件的移動對象

基于路徑覆蓋的查詢的查詢過程比基于范圍覆蓋的查詢更簡潔。查詢過程分為路段查詢和時間查詢兩部分:首先通過HMaster中的RN-tree索引查詢該范圍內的路段，通過.META表確定存儲了待查詢路段的Region及HRegionServer;然后在Region中利用內部時間索引t-index索引確定滿足時間條件的記錄。

2.2 時空范圍查詢

1)查詢類型定義。

空間中的KNN查詢主要包括兩類:靜態(tài)空間的KNN查詢和動態(tài)時空的KNN查詢。本文主要解決動態(tài)時空數據的KNN查詢問題，該查詢需要同時考慮時間和空間維度，本文所述的時空KNN查詢中查詢點和被查詢點都位于路網的路段當中，具體的查詢定義如下:

定義2 給定路網G(V，E)，查詢條件包括三部分:查詢的點坐標 p(x，y)、待查詢對象數量k和時間區(qū)間［ts，te］。查詢最后返回在時間區(qū)間［ts，te］內出現的距離點p最近的k個移動對象記錄。

2)查詢算法實現。

路網環(huán)境中的時空KNN［14］查詢是一個遞歸的查詢過程:第一次首先查詢點p所在的路段，隨后查詢該路段中距離p點最近的k個對象記錄;第二次查詢與該路段查相鄰的路段中的移動對象記錄;直到新的路段中距離p點最近的點的距離dist(p，ox)要大于候選集合中的最遠距離distmax，此時對于該路段及其后續(xù)路段的查詢結束，查詢過程直至所有路段的查詢都結束。其中 dist利用歐氏距離:dist(p，px) =計算得到，ox代表未知查詢點。

本文提出的時空KNN查詢算法的偽代碼描述如算法5。

算法5 KNNQuery()。

輸入 查詢點p，時間區(qū)間［t1，t2］和k;

輸出 符合查詢條件的移動對象集合。

rset=getRoadRRTree(q) //確定q的所在路段，RR為根節(jié)點

molist=getMovingObject(rset，t1，t2);

//找到路段中的所有移動對象

if molist.lenght ＞ k then

molist=chooseKObject(q，molist);

//選擇距離q最近的k個移動對象重新賦值

end if

distmax=getMaxDis(molist);

vlist← {r.vi，r.vj}; //相關邊的頂點列表

return RecursQuery(vlist，molist，distmax);

路網時空KNN查詢的向外擴展可以采用遞歸調用算法6是遞歸查詢過程的具體實現。

算法6 RecursQuery()。

輸入 頂點集合vlist，移動個對象候選集molist，最大距離distmax;

輸出 符合條件的移動對象。

if vlist==null then

return molist;

end if

v=vlist.dequeue(); //相關頂點出棧

rset=FindEdgeOfV(v); //找到與v相關的所有路段

for each rset.r in elist do

distmin=getMinDis(q，r); //當前路段中距離q的最短距離

if distmax≥distmin then

list← getMovingObject(r，t1，t2);

molist=list+molist;

if molist.length ＞ k then

molist=chooseKObject(q，molist);

end if

vlist.enqueue(edge.vj); //將邊的另一個頂點加入隊列

end if

end for each

distmax=getMaxDis(molist);

return RecursQuery(vlist，molist，distmax);

2.3 移動對象軌跡查詢

1)查詢類型定義。

移動對象軌跡查詢［15］，顧名思義其查詢過程中需要同時考慮查詢的時間屬性和空間屬性兩個方面。移動對象在路網中運動，因此其運動軌跡必然是沿著路網中的路段，具體查詢定義如下:

定義3 給定路網G(V，E)，查詢條件包括兩部分內容:查詢對象標識o和查詢時間區(qū)間［ts，te］。最后返回在時間區(qū)間［ts，te］內移動對象o的運動軌跡。

2)查詢算法實現。

由于查詢條件中只給出了移動對象的標識信息，因此無法預先確定移動對象經過的位置信息。查詢條件中不包含空間位置，因此不需要RN-tree索引的參與。該查詢過程可以概括為三個子過程:“全路段 移動對象 時間”。其中“全路段”查詢是利用.META表的映射向所有的路段發(fā)送查詢;“移動對象”查詢是利用Region中的移動對象索引o-index查詢移動對象的記錄;“時間”查詢則是利用o-index中的按時間順序排列的鏈表結構，確定滿足時間條件的記錄集合。

本文提出的移動對象軌跡查詢算法的偽代碼描述算法7。

算法7 TrajectoryQuery()。

輸入 移動對象o，時間區(qū)間［t1，t2］;

輸出 按時間排序的移動對象位置坐標tjlist。

roadlist=getTotalRoadSegmet(); //得到所有路段的id

for each roadlist.roadID do

roadID→HRegionServer;//映射到不同的HRegionServer，并行查詢

end for each

for each roadID in HRegionServer do

//循環(huán)每個HRegionServer中的路段

sRowkey=getStartRowkey(roadID);

eRowkey=getEndRowkey(roadID);

for each Rowkey∈［sRowkey，eRowkey］do

if Rowkey.oId==o ＆＆ t1≤ Rowkey.time≤ t2then

keylist.Add(Rowkey);

end if

end for each

end for each

tjlist.Add(getObjectResult(keylist));

return InsertSort(tjlist); //進行排序

3 實驗與結果分析

3.1 索引框架的性能分析

3.1.1 實驗環(huán)境

本文實驗基于HBase分布式數據庫平臺，因為HBase部署在Hadoop集群上層，因此實驗環(huán)境首先需要部署Hadoop集群環(huán)境。實驗環(huán)境包括兩部分:硬件環(huán)境和軟件環(huán)境。

硬件環(huán)境:本文采用阿里云的租賃式服務器ECS進行實驗，實驗采用的Hadoop集群節(jié)點數為5，其中1個節(jié)點配置為NameNode，4個節(jié)點配置為DataNode(其中NameNode設置為 HBase的 HMaster，DataNode設置為 HBase的 4個HRegionServer)。

軟件環(huán)境:開發(fā)環(huán)境為Myeclipse2014;開發(fā)操作系統(tǒng)為Windows 10;Hadoop 版本為2.5;HBase版本為1.2。

實驗方案:本文的實驗數據通過BerlinMod Benchmark［13］來生成。為了區(qū)分不同時間段的數據量，本文在生成實驗數據時，將移動對象的運動軌跡按照工作日和雙休日進行規(guī)劃，根據路段對數據進行不均勻的分配。實驗中生成了2 000個移動對象的運動軌跡，并對每個移動對象的運動軌跡按如下的方式進行設計:在工作日設置家和工作點作為運動軌跡的起始位置;雙休日的運動軌跡隨機生成。關于數據量的增長問題，先生成1 GB數據，若實驗中對數據的需求量大于1 GB，則采用復制的方式增加數據量。

3.1.2 實驗:集群的數據分配

本文在設計RM-HBase索引框架時，將路段映射到不同的HRegionServer和Region中，當該路段中產生了路網移動對象時空數據時，數據被存儲到該路段映射的Region中。其中，本文對“路段——Region”的映射關系是利用每條路段的歷史數據量分布情況產生。這種分配算法能夠有效地解決Hadoop分布式集群節(jié)點的數據熱點問題，圖4是在一次實驗中100 GB數據在不同節(jié)點上的分布情況，將上述數據分別利用STEHIX和RM-HBase在DataNode集群節(jié)點中進行存儲。圖4中的對比實驗結果顯示:在RM-HBase的不同節(jié)點中，數據分配表現出均衡的特性，STEHIX索引框架的數據分布則不是很均衡。

圖4 不同集群節(jié)點的數據量Fig.4 Data amount of different cluster nodes

由于實驗不具有普遍性，為了檢驗RM-HBase索引框架在解決數據熱點問題中表現出的普遍性性能優(yōu)勢。接下來本文進一步對上述結果進行分析，選用標準差作為數據指標，用于表現集群中不同節(jié)點之間的數據量差異。式(3)給出了標準差的計算方法:

其中:N代表集群的節(jié)點數量;μ表示集群中數據的均值;xi表示節(jié)點i中數據的存儲量。

標準差隨著數據量從40 GB到320 GB相應的變化情況如圖5所示。從圖5中能夠明顯看出，隨著集群中存儲的數據量的增加，STEHIX索引框架中集群節(jié)點數據量的標準差都大于10 GB，這一數值說明在STEHIX的分布式集群節(jié)點中，數據的分配是不均衡的;而RM-HBase索引框架中集群節(jié)點數據量的標準差都小于2.5 GB，這一數值表明數據在RM-HBase索引框架的分布式集群的節(jié)點中，數據分布是均衡的，不會出現數據熱點問題。

圖5 集群節(jié)點的數據分配Fig.5 Data allocation of cluster nodes

出現上述數據分布現象的原因可以通過RM-HBase索引框架中路段分配算法加以解釋:由于路網環(huán)境中移動對象只在路段中運動且路段之間的數據量存在較大差異。若采用等大小的矩形區(qū)域劃分方法創(chuàng)建索引，則單位時間內每個子區(qū)域中產生的數據量存在巨大差異，從而造成集群的每個節(jié)點中的數據量參差不齊，繼而引起集群節(jié)點中的數據熱點分布問題。而由于RM-HBase索引框架利用不同路段的歷史數據量將路段均勻映射到不同的服務器中進行存儲，從而有效避免了數據熱點問題的發(fā)生。

3.2 算法的性能分析

針對三種時空查詢算法的性能分析，本文實驗部分選用的對比對象是 STEHIX索引框架，實驗的具體配置與RM-HBase索引框架的實驗相同，本小節(jié)主要介紹算法實驗的數據來源和數據生成過程，然后依次對時空范圍查詢、時空KNN查詢和移動對象軌跡查詢的算法性能實驗結果進行分析。

3.2.1 實驗數據

本文實驗數據利用MinnesotaTG項目對外提供的數據生成接口，用戶能夠對路網區(qū)域、生成的移動對象數量、移動對象的運動軌跡、生成時間進行自定義。路網選取美國Colorado區(qū)域的交通網絡;車輛時空數據則是利用BerlinMod Benchmark［13］測試集來動態(tài)生成。

實驗選擇的區(qū)域覆蓋了1057066個路段，數據模擬周期為7 d，每分鐘記錄一條位置信息，初始移動對象為2 000個，通過復制已獲得數據集的方式獲取更多數據。

3.2.2 實驗一:時空范圍查詢

時空范圍查詢實驗分別包括查詢窗口大小和數據量對范圍查詢耗時的影響。圖6顯示了隨著查詢窗口大小變化，時空范圍查詢耗時的變化情況。實驗固定時間維度，依次選取1×1、2×2、3×3、4×4、5×5、6×6矩形查詢窗口，查詢2 h的移動對象數據記錄。實驗結果表明:隨著查詢窗口的擴大，STEHIX和RM-HBase的時空范圍查詢耗時都在不斷地增加，但是STEHIX索引框架的查詢時間增加速度要明顯高于RMHBase索引框架。產生這種現象的原因在于:RM-HBase中的RN-tree索引能夠提高路段數據的查詢效率，同時根據RN-tree中的路段分配算法，相鄰的路段可能被分配到不同的HRegionServer中存儲，因此在進行范圍查詢時不同HRegionServer的路段能夠進行并行查詢，同時;在Region內對Rowkey鍵值的結構進行了改進，能進一步提高移動對象的查詢效率。此外，RM-HBase在Region中創(chuàng)建了高效的時間索引t-index，該索引能夠高效地篩選時間區(qū)間。

圖6 查詢窗口對范圍查詢性能的影響Fig.6 Effect of query window on range query performance

圖7 是隨著移動對象數據量的增加范圍查詢的耗時變化情況。實驗設定查詢窗口大小為6×6，其中分布式集群的數據量變化區(qū)間為40 GB～320 GB。從圖7中能夠明顯看出:隨著數據量的增加，兩種索引框架的范圍查詢耗時也在不斷地增加。但是與STEHIX相比，RM-HBase索引框架的耗時存在明顯的性能較低情況。此外，隨著數據量的增加RM-HBase的范圍查詢耗時增速越來越緩慢。出現上述現象的原因:隨著移動對象數據的不斷增加，Region塊內的時間索引也需要不斷進行更新操作，因此查詢耗時隨之增加。

圖8顯示了隨著集群節(jié)點變化，時空范圍查詢的耗時變化情況。實驗設定查詢窗口大小為6×6，數據量為320 GB，其中分布式集群節(jié)點數量變化區(qū)間為1～10。從圖8中能夠明顯看出:隨著集群節(jié)點數量的增加，兩種索引框架的范圍查詢耗時也在不斷地減少，且RM-HBase的查詢效率明顯優(yōu)于STEHIX，但是RM-HBase的查詢耗時降幅越來越緩慢。出現上述現象的原因:隨著集群節(jié)點的數量不斷增加，通過下層索引檢索最終結果的耗時情況會趨向穩(wěn)定。時空KNN查詢與軌跡查詢的實驗現象與此實驗一致，因此后面不再介紹。

圖7 數據量對范圍查詢性能的影響Fig.7 Effect of data amount on range query performance

圖8 集群節(jié)點數量對范圍查詢性能的影響Fig.8 Effect of number of cluster nodes on range query performance

造成上述索引差異的原因是:RM-HBase對HBase進行了全面的改進，首先通過RN-tree，明顯縮小了范圍查詢的區(qū)域，使得每次的查詢過程都是有效的，避免“死空間”問題的出現，從而提高了路段對象的查詢效率;其次通過Rowkey鍵的設計，數據按照“路段 時間 移動對象”的字典序進行數據連續(xù)存儲。因此在確定了查詢區(qū)間范圍后，能夠快速地定位該范圍內的所有移動對象記錄;而STEHIX只是按照矩形空間對數據進行存儲，在每個Region內數據的存儲是無序的，因此查詢性能受到影響。

3.2.3 實驗二:時空KNN查詢

該部分實驗分為兩組實驗:第一組實驗測試隨著k值的變化KNN查詢的耗時變化情況;第二組實驗測試隨著移動對象數據量的變化KNN查詢耗時的變化情況。

隨著查詢中k值變化時空KNN查詢的耗時變化結果如圖9所示。實驗設置整個查詢區(qū)域中初始移動對象數量為2000，其中 k 值依次取 4、8、16、32、64。通過實驗結果可以得出:隨著k值的增加，兩種索引框架的耗時也是不斷增加的，但是RM-HBase的耗時增加速率要低于STEHIX索引框架;在相同k值的查詢中，STEHIX索引框架的查詢耗時明顯大于RM-HBase索引框架。這說明:隨著k值的增加，RM-HBase索引框架的時空KNN查詢性能明顯優(yōu)于同等條件下的STEHIX索引框架。

出現上述性能差異的原因是由于:RM-HBase索引在進行KNN查詢時，首先利用RN-tree通過路段與路段間的連接關系快速定位移動對象所在的路段，能夠高效地對空間查詢范圍進行剪枝;其次，根據當前路段的頂點再進行擴展路段的查詢，在Region內則通過時間索引t-index提高時間維度的查詢效率并利用本文的Rowkey設計能提高目標記錄的查詢速度。而STEHIX索引框架在進行KNN查詢時，對空間路段的查詢是盲目的，它是通過查詢與查詢點相鄰的所有子區(qū)域找到所有的查詢結果，因此查詢效率較低。

圖10是隨著數據量的不斷增加，KNN查詢的耗時變化情況。實驗中設定查詢條件k=3，移動對象的數據量變化范圍為40 GB～320 GB。實驗結果同樣顯示:隨著數據量的不斷增加，RM-HBase索引框架的時空KNN查詢中具有突出的性能優(yōu)勢。出現上述性能差異的原因是:隨數據量的增加，RM-HBase通過RN-tree能夠有效減少需要路段的查詢范圍，實現對查詢范圍的快速剪枝?？臻g路段查詢結束后，RM-HBase利用鏈式時間索引t-index篩選滿足時間區(qū)間的對象記錄。由于本文在Rowkey設計時充分考慮了數據的字典序連續(xù)存儲問題，因此時間的查詢效率能夠得到有效的提高。STEHIX索引框架沒有考慮路網環(huán)境的特點，因此在KNN查詢時，需要連續(xù)查詢多個連續(xù)的數據區(qū)域，每次的擴展查詢都是需要查詢四個方向的數據區(qū)域，而RM-HBase改變了這種查詢局面，只需要查詢與現有空間相連的路段，同時能夠避免KNN查詢的不完全性。

圖9 k值變化對KNN查詢性能的影響Fig.9 Effect of k value change on KNN query performance

圖10 數據量對KNN查詢性能的影響Fig.10 Effect of data amount on KNN query performance

3.2.4 實驗三:移動對象軌跡查詢

本文提出的RM-Hbase除了能夠支持時空范圍查詢和時空KNN查詢外，該索引框架還能高效地支持移動對象軌跡查詢。查詢條件包括移動對象和時間區(qū)間，該部分實驗主要測試隨著移動對象數量變化，軌跡查詢的響應耗時情況。

隨著數據量的不斷增加，查詢一個移動對象在2 h內運動軌跡的查詢耗時情況如圖11所示。實驗結果顯示:RMHBase索引框架的查詢性能要明顯優(yōu)于STEHIX。兩種索引框架與非分布式相比在軌跡查詢時效率都能表現出明顯的增加，這是由于分布式集群的固有優(yōu)勢而確定的。出現上述現象的原因包括兩方面:首先RM-HBase在Region內增加了移動對象索引o-index，能夠高效地確定移動對象是否位于當前Region以及移動對象的存儲位置;其次RM-HBase重新設計了Rowkey鍵的結構，這也進一步提高了移動對象和時間區(qū)間的檢索效率;更重要的是，RM-HBase的o-index結構中包括移動對象記錄單鏈表，單鏈表按照時間排序，因此在找到移動對象記錄后，能夠通過其后面的鏈表首地址找到當前Region中所有的滿足移動對象和時間條件的記錄。STEHIX在移動對象查詢時由于沒有提供移動對象索引，因此需要查詢所有的Region，此外通過t-index找到所有滿足時間區(qū)間條件的記錄，最后需要從大量的滿足時間的數據中篩選移動對象信息。

圖11 數據量對軌跡查詢性能的影響Fig.11 Effect of data amount on trajectory query performance

4 結語

RM-HBase是針對Hadoop子項目HBase的索引結構改進而提出的索引框架，主要用以解決海量路網移動對象數據的高效時空索引問題。本文通過對原生HBase索引框架的上下層重新設計，有效地解決了路網空間移動對象的查詢過程中的“死空間”和路段分配中的集群數據熱點問題，同時設計了針對RM-HBase框架的相關查詢算法。實驗結果表明RMHBase框架相對于STEHIX框架在路網環(huán)境下移動對象有時空檢索效率的提升;然而本文中路網劃分方法的計算代價較大且由于RN-tree索引節(jié)點中存儲了大量的數據，需要占用更大的索引存儲空間，因此進一步的研究方向是如何提高路網空間的劃分效率。