基于HBase的路網(wǎng)移動(dòng)對(duì)象時(shí)空索引方法

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

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

0 引言

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

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

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

1 RM-HBase索引框架

1.1 索引框架

1.1.1 路網(wǎng)時(shí)空數(shù)據(jù)定義

路網(wǎng)移動(dòng)對(duì)象數(shù)據(jù)是時(shí)空數(shù)據(jù)的一種特殊環(huán)境下的子類，數(shù)據(jù)包括一維時(shí)間和二維空間共三個(gè)維度。對(duì)路網(wǎng)時(shí)空數(shù)據(jù)進(jìn)行定義是進(jìn)行索引框架研究的基礎(chǔ)，其中數(shù)據(jù)包括兩種類型:空間路網(wǎng)數(shù)據(jù)和移動(dòng)對(duì)象數(shù)據(jù)，本文對(duì)每種數(shù)據(jù)的定義如下。

1)空間路網(wǎng)數(shù)據(jù)。

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

2)移動(dòng)對(duì)象數(shù)據(jù)。

移動(dòng)對(duì)象數(shù)據(jù)是由路網(wǎng)中的移動(dòng)對(duì)象(車輛等)隨時(shí)間運(yùn)動(dòng)而產(chǎn)生的數(shù)據(jù)，也就是最終存儲(chǔ)在集群節(jié)點(diǎn)中的數(shù)據(jù)。該類數(shù)據(jù)是一種時(shí)空數(shù)據(jù)，數(shù)據(jù)按條存儲(chǔ)在HBase的用戶表中，每條移動(dòng)對(duì)象數(shù)據(jù)記錄的屬性如表1所示。

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

表1 MoveObject表的結(jié)構(gòu)Tab.1 Structure of MoveObject table

1.1.2 RM-HBase 的結(jié)構(gòu)

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

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

2)基于HBase上層的索引結(jié)構(gòu)設(shè)計(jì)。上層索引設(shè)計(jì)的改進(jìn)包括對(duì).META表中的存儲(chǔ)內(nèi)容重新設(shè)計(jì)映射關(guān)系和根據(jù)路段歷史數(shù)據(jù)分布情況設(shè)計(jì)路段分配算法兩個(gè)方面，然后將所有路段數(shù)據(jù)映射到不同的Region和HRegionServer，解決數(shù)據(jù)的熱點(diǎn)分布問題，同時(shí)利用分布式框架的分布式查詢機(jī)制顯著提高查詢效率。

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

RM-HBase的結(jié)構(gòu)框架如圖1所示。

1.2 基于原生HBase的結(jié)構(gòu)改進(jìn)

1.2.1 上層索引結(jié)構(gòu)設(shè)計(jì)

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

1)計(jì)算路段衡量指標(biāo)。

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

圖1 RM-HBase結(jié)構(gòu)框架Fig.1 Structural framework of RM-HBase

其中:i，j分別表示每條路段的兩個(gè)頂點(diǎn)標(biāo)號(hào);pij代表路段vivj所占的比重是本文的目標(biāo)值;totalij代表路段vivj在上述一周內(nèi)的移動(dòng)對(duì)象數(shù)據(jù)總量;N表示查詢區(qū)域內(nèi)的路段總數(shù);totalij代表查詢區(qū)域中一周內(nèi)的所有路段中產(chǎn)生的移動(dòng)對(duì)象數(shù)據(jù)總量。

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

2)路段分配算法。

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

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

算法 1 RoadSegDistribution()。

輸入 有序的路段對(duì)應(yīng)概率數(shù)組rlist，路段劃分的類別個(gè)數(shù)k;

輸出 返回k臺(tái)服務(wù)器存儲(chǔ)的路段集合bucketlist。

bucketNum=k; //桶數(shù)

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; //記錄每個(gè)桶的數(shù)據(jù)和

LinkedList〈LinkedList〈int〉〉bucketlist=newLinkedList

〈LinkedList〈int〉〉(); //存儲(chǔ)最終的路段分配結(jié)果，此外，//將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; //初始化最小值下標(biāo)為0

for each buckets i do

if buckets［i］ ＜ min then

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

minIndex=i;

end for each

return minIndex

算法1對(duì)路段的分配能夠解決集群節(jié)點(diǎn)的數(shù)據(jù)熱點(diǎn)問題。

1.2.2 下層索引結(jié)構(gòu)設(shè)計(jì)

本文針對(duì)HRegionServer的內(nèi)部數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，在每個(gè)HRegionServer中進(jìn)行了兩方面的索引改進(jìn)，以提高數(shù)據(jù)在Region內(nèi)的查詢效率。兩方面的改進(jìn)分別是:創(chuàng)建Region索引和設(shè)計(jì)Rowkey鍵，下面分別對(duì)兩部分的改進(jìn)進(jìn)行說明。

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

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

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

2)設(shè)計(jì)Rowkey鍵。

HBase表中的數(shù)據(jù)基于行鍵進(jìn)行存儲(chǔ)。在進(jìn)行Rowkey鍵設(shè)計(jì)時(shí)要充分拉開不同Rowkey鍵的差異性。通過設(shè)計(jì)Rowkey鍵提高HBase的查詢效率，在文獻(xiàn)［8］和文獻(xiàn)［7］中已經(jīng)得到了成功的應(yīng)用。根據(jù)HBase表數(shù)據(jù)按照字典序排序的原則，本文對(duì)表中Rowkey鍵的設(shè)計(jì)內(nèi)容如式(2):其中:rid是路段的標(biāo)識(shí)id;T表示移動(dòng)對(duì)象記錄的存儲(chǔ)時(shí)間;oid是移動(dòng)對(duì)象的id。基于以上的Rowkey設(shè)計(jì)，數(shù)據(jù)首先按照路段存儲(chǔ)，其次按照時(shí)間屬性進(jìn)行存儲(chǔ)，最后依照移動(dòng)對(duì)象進(jìn)行存儲(chǔ)。

圖2 o-index索引結(jié)構(gòu)Fig.2 Index structure of o-index

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

1.3 路網(wǎng)索引RN-tree設(shè)計(jì)

1.3.1 RN-tree結(jié)構(gòu)設(shè)計(jì)

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

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

1.3.2 路網(wǎng)空間劃分算法

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

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

算法3 RoadNetworkPartition()。

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

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

graphset=initializeGraph(G，f，n);

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

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

//計(jì)算每個(gè)節(jié)點(diǎn)的內(nèi)部和外部代價(jià)g=internalcost+externalcost

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

int maxmal=0;

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

//計(jì)算每個(gè)頂點(diǎn)i的權(quán)重和

if g［i］ ＞ maxmal then

maxmal=g［i］;

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

end if

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

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

//更新交換后兩個(gè)子圖的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ū)域一分為二的劃分方法，當(dāng)需要將區(qū)域劃分為2n(其中n＞1)個(gè)子圖時(shí)，繼續(xù)采用算法3中的方法進(jìn)行迭代劃分。對(duì)路網(wǎng)的劃分方法與等空間的劃分方法相比，能夠有效避免將一條路段切分成多段的情況，為高效的路網(wǎng)空間對(duì)象查詢奠定了基礎(chǔ)。

1.3.3 RN-tree 結(jié)構(gòu)設(shè)計(jì)

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

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

圖3 RN-tree索引結(jié)構(gòu)Fig.3 Index structure of RN-tree

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

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

2 路網(wǎng)時(shí)空查詢算法

2.1 時(shí)空范圍查詢

1)查詢類型定義。

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

定義1 給定路網(wǎng)G(V，E)，查詢條件包括矩形覆蓋范圍(［x1，x2］，［y1，y2］) 和時(shí)間區(qū)間［ts，te］兩部分。查詢結(jié)束后返回在時(shí)間區(qū)間［ts，te］內(nèi)經(jīng)過區(qū)域(［x1，x2］，［y1，y2］) 的所有移動(dòng)對(duì)象記錄。

2)查詢算法實(shí)現(xiàn)。

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

基于范圍覆蓋的范圍查詢算法實(shí)現(xiàn)過程如算法4所示。

算法4 RangeQuery()。

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

t2］;

輸出 符合查詢條件的移動(dòng)對(duì)象集合。

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

rslist=getMetaTable(rset);

//定位路段對(duì)應(yīng)的Region和HRegionServer地址

Map(roadID，HRegionServer，rlist);

//利用MapReduce將候選集中的路段查詢?nèi)蝿?wù)分配到

//對(duì)應(yīng)的HRegionServer和Region中并行執(zhí)行

for each rslist.HRegionServer do //所有 HRegionServer并行運(yùn)行

startRowkey=getThisRowkey(rslist.roadID)

//獲取每個(gè)路段的起始存儲(chǔ)地址

endRowkey=getNextRowkey(rslist.roadID)

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

scan.setStartRow(startRowkey);

scan.setStopRow(endRowkey);

//利用scan函數(shù)得到當(dāng)前路段的候選集合

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將不同服務(wù)器的結(jié)果合并

return olist //返回滿足條件的移動(dòng)對(duì)象

基于路徑覆蓋的查詢的查詢過程比基于范圍覆蓋的查詢更簡(jiǎn)潔。查詢過程分為路段查詢和時(shí)間查詢兩部分:首先通過HMaster中的RN-tree索引查詢?cè)摲秶鷥?nèi)的路段，通過.META表確定存儲(chǔ)了待查詢路段的Region及HRegionServer;然后在Region中利用內(nèi)部時(shí)間索引t-index索引確定滿足時(shí)間條件的記錄。

2.2 時(shí)空范圍查詢

1)查詢類型定義。

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

定義2 給定路網(wǎng)G(V，E)，查詢條件包括三部分:查詢的點(diǎn)坐標(biāo) p(x，y)、待查詢對(duì)象數(shù)量k和時(shí)間區(qū)間［ts，te］。查詢最后返回在時(shí)間區(qū)間［ts，te］內(nèi)出現(xiàn)的距離點(diǎn)p最近的k個(gè)移動(dòng)對(duì)象記錄。

2)查詢算法實(shí)現(xiàn)。

路網(wǎng)環(huán)境中的時(shí)空KNN［14］查詢是一個(gè)遞歸的查詢過程:第一次首先查詢點(diǎn)p所在的路段，隨后查詢?cè)撀范沃芯嚯xp點(diǎn)最近的k個(gè)對(duì)象記錄;第二次查詢與該路段查相鄰的路段中的移動(dòng)對(duì)象記錄;直到新的路段中距離p點(diǎn)最近的點(diǎn)的距離dist(p，ox)要大于候選集合中的最遠(yuǎn)距離distmax，此時(shí)對(duì)于該路段及其后續(xù)路段的查詢結(jié)束，查詢過程直至所有路段的查詢都結(jié)束。其中 dist利用歐氏距離:dist(p，px) =計(jì)算得到，ox代表未知查詢點(diǎn)。

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

算法5 KNNQuery()。

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

輸出 符合查詢條件的移動(dòng)對(duì)象集合。

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

molist=getMovingObject(rset，t1，t2);

//找到路段中的所有移動(dòng)對(duì)象

if molist.lenght ＞ k then

molist=chooseKObject(q，molist);

//選擇距離q最近的k個(gè)移動(dòng)對(duì)象重新賦值

end if

distmax=getMaxDis(molist);

vlist← {r.vi，r.vj}; //相關(guān)邊的頂點(diǎn)列表

return RecursQuery(vlist，molist，distmax);

路網(wǎng)時(shí)空KNN查詢的向外擴(kuò)展可以采用遞歸調(diào)用算法6是遞歸查詢過程的具體實(shí)現(xiàn)。

算法6 RecursQuery()。

輸入 頂點(diǎn)集合vlist，移動(dòng)個(gè)對(duì)象候選集molist，最大距離distmax;

輸出 符合條件的移動(dòng)對(duì)象。

if vlist==null then

return molist;

end if

v=vlist.dequeue(); //相關(guān)頂點(diǎn)出棧

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

for each rset.r in elist do

distmin=getMinDis(q，r); //當(dāng)前路段中距離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); //將邊的另一個(gè)頂點(diǎn)加入隊(duì)列

end if

end for each

distmax=getMaxDis(molist);

return RecursQuery(vlist，molist，distmax);

2.3 移動(dòng)對(duì)象軌跡查詢

1)查詢類型定義。

移動(dòng)對(duì)象軌跡查詢［15］，顧名思義其查詢過程中需要同時(shí)考慮查詢的時(shí)間屬性和空間屬性兩個(gè)方面。移動(dòng)對(duì)象在路網(wǎng)中運(yùn)動(dòng)，因此其運(yùn)動(dòng)軌跡必然是沿著路網(wǎng)中的路段，具體查詢定義如下:

定義3 給定路網(wǎng)G(V，E)，查詢條件包括兩部分內(nèi)容:查詢對(duì)象標(biāo)識(shí)o和查詢時(shí)間區(qū)間［ts，te］。最后返回在時(shí)間區(qū)間［ts，te］內(nèi)移動(dòng)對(duì)象o的運(yùn)動(dòng)軌跡。

2)查詢算法實(shí)現(xiàn)。

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

本文提出的移動(dòng)對(duì)象軌跡查詢算法的偽代碼描述算法7。

算法7 TrajectoryQuery()。

輸入 移動(dòng)對(duì)象o，時(shí)間區(qū)間［t1，t2］;

輸出 按時(shí)間排序的移動(dòng)對(duì)象位置坐標(biāo)tjlist。

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

for each roadlist.roadID do

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

end for each

for each roadID in HRegionServer do

//循環(huán)每個(gè)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); //進(jìn)行排序

3 實(shí)驗(yàn)與結(jié)果分析

3.1 索引框架的性能分析

3.1.1 實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)基于HBase分布式數(shù)據(jù)庫平臺(tái)，因?yàn)镠Base部署在Hadoop集群上層，因此實(shí)驗(yàn)環(huán)境首先需要部署Hadoop集群環(huán)境。實(shí)驗(yàn)環(huán)境包括兩部分:硬件環(huán)境和軟件環(huán)境。

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

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

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

3.1.2 實(shí)驗(yàn):集群的數(shù)據(jù)分配

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

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

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

其中:N代表集群的節(jié)點(diǎn)數(shù)量;μ表示集群中數(shù)據(jù)的均值;xi表示節(jié)點(diǎn)i中數(shù)據(jù)的存儲(chǔ)量。

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

圖5 集群節(jié)點(diǎn)的數(shù)據(jù)分配Fig.5 Data allocation of cluster nodes

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

3.2 算法的性能分析

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

3.2.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)數(shù)據(jù)利用MinnesotaTG項(xiàng)目對(duì)外提供的數(shù)據(jù)生成接口，用戶能夠?qū)β肪W(wǎng)區(qū)域、生成的移動(dòng)對(duì)象數(shù)量、移動(dòng)對(duì)象的運(yùn)動(dòng)軌跡、生成時(shí)間進(jìn)行自定義。路網(wǎng)選取美國Colorado區(qū)域的交通網(wǎng)絡(luò);車輛時(shí)空數(shù)據(jù)則是利用BerlinMod Benchmark［13］測(cè)試集來動(dòng)態(tài)生成。

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

3.2.2 實(shí)驗(yàn)一:時(shí)空范圍查詢

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

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

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

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

圖7 數(shù)據(jù)量對(duì)范圍查詢性能的影響Fig.7 Effect of data amount on range query performance

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

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

3.2.3 實(shí)驗(yàn)二:時(shí)空KNN查詢

該部分實(shí)驗(yàn)分為兩組實(shí)驗(yàn):第一組實(shí)驗(yàn)測(cè)試隨著k值的變化KNN查詢的耗時(shí)變化情況;第二組實(shí)驗(yàn)測(cè)試隨著移動(dòng)對(duì)象數(shù)據(jù)量的變化KNN查詢耗時(shí)的變化情況。

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

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

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

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

圖10 數(shù)據(jù)量對(duì)KNN查詢性能的影響Fig.10 Effect of data amount on KNN query performance

3.2.4 實(shí)驗(yàn)三:移動(dòng)對(duì)象軌跡查詢

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

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

圖11 數(shù)據(jù)量對(duì)軌跡查詢性能的影響Fig.11 Effect of data amount on trajectory query performance

4 結(jié)語

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