李 冬 房 俊

(北方工業(yè)大學(xué)大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室 北京 100041)

基于HBase的交通數(shù)據(jù)區(qū)域查詢方法

李 冬 房 俊

(北方工業(yè)大學(xué)大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室 北京 100041)

隨著智能交通的發(fā)展,交通數(shù)據(jù)呈現(xiàn)出指數(shù)性增長(zhǎng)。為了提升時(shí)空區(qū)域查詢性能,論文提出了一種基于HBase的交通數(shù)據(jù)區(qū)域查詢方法HRQ。該方法利用交通數(shù)據(jù)的三維時(shí)空特性,采用Geohash算法將交通數(shù)據(jù)的經(jīng)緯度信息轉(zhuǎn)為Geohash編碼,然后與時(shí)間組合作為HBase行鍵,并設(shè)計(jì)了相應(yīng)的查詢算法。實(shí)驗(yàn)結(jié)果表明,與直接組合經(jīng)緯度和時(shí)間作為行鍵的方法相比,在基于時(shí)間范圍的區(qū)域查詢上HRQ方法的性能要高30%以上,在基于區(qū)域范圍的區(qū)域查詢上HRQ的性能優(yōu)勢(shì)隨著查詢區(qū)域的增大而增加。

HBase; Geohash算法; 區(qū)域查詢; 海量交通數(shù)據(jù); 時(shí)空特性

Class Number TP311

1 引言

隨著智能交通的發(fā)展,交通數(shù)據(jù)呈現(xiàn)出指數(shù)性增長(zhǎng)。傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)無(wú)法應(yīng)對(duì)海量交通數(shù)據(jù)的高效存儲(chǔ)和處理需求,以HBase為代表的NoSQL數(shù)據(jù)庫(kù)[1]具有擴(kuò)展性強(qiáng)、并發(fā)性能好、數(shù)據(jù)模型靈活等優(yōu)點(diǎn),在海量數(shù)據(jù)存儲(chǔ)和查詢方面具有先天的優(yōu)勢(shì),國(guó)內(nèi)外很多大型互聯(lián)網(wǎng)公司都用它來(lái)存儲(chǔ)和管理海量數(shù)據(jù)[2～3]。

車輛數(shù)據(jù)的區(qū)域查詢[4]是智能交通應(yīng)用的一種基礎(chǔ)數(shù)據(jù)服務(wù),像Uber和滴滴等打車軟件的叫車服務(wù)和公安機(jī)關(guān)的刑偵過(guò)程一般都需要對(duì)車輛GPS數(shù)據(jù)等交通數(shù)據(jù)進(jìn)行區(qū)域查詢。交通數(shù)據(jù)具有三維時(shí)空特征,對(duì)交通數(shù)據(jù)的區(qū)域查詢其實(shí)就是一種時(shí)空查詢,這對(duì)于只能在行鍵上構(gòu)建字典序索引的HBase是一個(gè)挑戰(zhàn),即如何實(shí)現(xiàn)在HBase中對(duì)交通數(shù)據(jù)進(jìn)行快速有效的區(qū)域查詢是一大難點(diǎn)。

針對(duì)上述問(wèn)題,本文提出了一種基于HBase的交通數(shù)據(jù)區(qū)域查詢方法——HRQ(HBase based Regional Query)時(shí)空區(qū)域查詢方法。該方法是通過(guò)Geohash算法[5]的降維思想將交通數(shù)據(jù)的位置信息(經(jīng)度、緯度)轉(zhuǎn)為一維字符串,然后加上記錄的時(shí)間作為HBase行鍵,實(shí)現(xiàn)對(duì)交通數(shù)據(jù)的快速區(qū)域查詢。它不僅能有效提升交通數(shù)據(jù)區(qū)域查詢的性能,而且也不需要更改原有系統(tǒng)的架構(gòu),具有很高的實(shí)用性。

2 相關(guān)工作

為了更好地實(shí)現(xiàn)對(duì)時(shí)空數(shù)據(jù)的區(qū)域查詢,近年來(lái)很多研究者采用將R-樹與其他索引結(jié)構(gòu)組合的方式[6～11]實(shí)現(xiàn)空間索引和時(shí)空索引。其中文獻(xiàn)[9]提出了一種利用R-樹對(duì)區(qū)域進(jìn)行劃分的區(qū)域查詢方法,它是由區(qū)域索引、對(duì)象位置索引和對(duì)象索引三部分組成,采用了R-樹、網(wǎng)格和Hash三種數(shù)據(jù)結(jié)構(gòu),該方法在查詢對(duì)象分布不均勻時(shí)具有比R-樹和網(wǎng)格有更優(yōu)的查詢性能。文獻(xiàn)[10]提出了一種基于R-樹和四叉樹的空間索引結(jié)構(gòu),它的節(jié)點(diǎn)構(gòu)造是按空間數(shù)據(jù)的分布來(lái)進(jìn)行的,使得樹的高度盡可能降低,有利于提升區(qū)域查詢的性能。文獻(xiàn)[11]提出了一種基于KD樹和R-樹的多維索引結(jié)構(gòu),是一種雙層索引模型,與R-樹索引相比具有一定優(yōu)勢(shì)。上述三種方法采用混合索引結(jié)構(gòu)實(shí)現(xiàn)空間索引,占用大量的冗余空間,實(shí)現(xiàn)復(fù)雜,并且樹形結(jié)構(gòu)使索引維護(hù)變得困難,在海量數(shù)據(jù)環(huán)境下,樹的索引性能可能會(huì)退化為線性檢索從而導(dǎo)致查詢性能大大降低。

針對(duì)時(shí)空數(shù)據(jù)的多維特性進(jìn)行降維處理,在降維得到的信息上構(gòu)建索引來(lái)提升空間區(qū)域查詢性能,是近年來(lái)的一個(gè)新的研究熱點(diǎn)。文獻(xiàn)[12]提出了一種在Mysql數(shù)據(jù)庫(kù)中實(shí)現(xiàn)的基于Geohash的面數(shù)據(jù)區(qū)域查詢方法,即將數(shù)據(jù)的經(jīng)緯度信息轉(zhuǎn)為Geohash編碼,存到一個(gè)列中,并在該列上建索引,這種方法在關(guān)系型數(shù)據(jù)庫(kù)中相對(duì)于基于經(jīng)緯度、R樹的查詢有一定的優(yōu)勢(shì)。文獻(xiàn)[13]提出了一種在HBase數(shù)據(jù)庫(kù)中實(shí)現(xiàn)的基于Geohash的車輛數(shù)據(jù)鄰近查詢方法,該方法將車輛信息的經(jīng)緯得到Geohash編碼與車牌ID組合作為HBase行鍵,來(lái)實(shí)現(xiàn)車輛數(shù)據(jù)的空間區(qū)域查詢。上述兩種研究工作只利用了數(shù)據(jù)的空間信息,僅對(duì)只有空間特征的數(shù)據(jù)查詢具有較好的性能。

3 基于HBase的交通數(shù)據(jù)區(qū)域查詢

3.1 相關(guān)定義

定義1 交通數(shù)據(jù)集C={ci|i∈(1,n)},其中ci表示一條車輛信息記錄,包括車輛檢測(cè)設(shè)備(如GPS設(shè)備)的ID、車輛ID、時(shí)間、經(jīng)度、緯度和車輛其他信息等。

定義2 兩點(diǎn)距離是指對(duì)于點(diǎn)A、B,令(Lona,Lata)表示A點(diǎn)經(jīng)緯度,(Lonb,Latb)表示B點(diǎn)經(jīng)緯度,由谷歌地圖計(jì)算方法可得A,B兩點(diǎn)的距離d(A,B)=S*R,其中R為地球半徑。S值由如下公式求得:

其中,a=Lata-Lotb為兩點(diǎn)緯度之差,b=Lona-Lonb為兩點(diǎn)經(jīng)度之差。

下面給出交通數(shù)據(jù)區(qū)域查詢的定義,本文目前僅考慮矩形區(qū)域查詢及圓形區(qū)域查詢。

定義3 矩形查詢區(qū)域是指由點(diǎn)p1(Lat1,Lon1)、p2(Lat2,Lon2)、p3(Lat3,Lon3)、p4(Lat4,Lon4)(其中p1、p2、p3、p4分別為查詢區(qū)域的左下角點(diǎn),右下角點(diǎn),左上角點(diǎn)和右上角點(diǎn))所構(gòu)成的空間區(qū)域。

圖1 最小外接矩形

定義5 區(qū)域時(shí)空查詢是指在對(duì)某一選中區(qū)域,在此區(qū)域內(nèi)查詢?cè)跁r(shí)間段(Ts,Te)內(nèi)的交通數(shù)據(jù)。即求Csub?C,使得:

?∈Csub,c.lat∈(Lat1,Lat3)&

c.lon∈(Lon1,Lon2)&c.t∈(Ts,Te),

其結(jié)果集記為Cn。如果是矩形區(qū)域查詢,則Cn為最終結(jié)果;如果是圓形區(qū)域查詢,還需滿足:

?c∈Cn,d(p,c)≤D

3.2 基于HBase區(qū)域查詢的一般方法

圖2 經(jīng)緯度加時(shí)間的行鍵組合示例圖

由于交通數(shù)據(jù)具有時(shí)空三維特性,結(jié)合HBase行鍵的特征,想要能夠有效檢索出具有時(shí)空特性的交通數(shù)據(jù),就需要將交通數(shù)據(jù)中時(shí)空的三個(gè)維度屬性全都放在HBase行鍵中。HBase傳統(tǒng)的區(qū)域時(shí)空查詢方法是直接用經(jīng)緯度加時(shí)間作為行鍵實(shí)現(xiàn)的,其組合過(guò)程如圖2所示。采用該方法時(shí),數(shù)據(jù)存儲(chǔ)到HBase中的邏輯數(shù)據(jù)模型如表1所示。

表1 基于經(jīng)緯度的HBase數(shù)據(jù)模型

基于該方法的時(shí)空區(qū)域查詢步驟如下:

第一步,確定查詢區(qū)域;

第二步,通過(guò)查詢區(qū)域的左下角和右上角兩個(gè)頂點(diǎn)的經(jīng)緯度和查詢起止時(shí)間,確定需要掃描HBase的行鍵范圍;

第三步,設(shè)置行鍵過(guò)濾器和值過(guò)濾器;

第四步,對(duì)HBase進(jìn)行掃描,輸出結(jié)果集。

采用該方法的行鍵設(shè)計(jì),由于數(shù)據(jù)的時(shí)空屬性全在行鍵之中,在檢索數(shù)據(jù)時(shí),可以通過(guò)行鍵減少數(shù)據(jù)掃描的范圍。但是,該方法的數(shù)據(jù)在HBase中的存儲(chǔ)順序是先按照緯度排序,再按照經(jīng)度排序,最后按照時(shí)間排序的,即在行鍵中時(shí)空的三個(gè)維度權(quán)重都不一樣。由于HBase基于行鍵掃描數(shù)據(jù)時(shí),只有首字段會(huì)有很好的索引效果,所以這種區(qū)域時(shí)空查詢方法在掃描數(shù)據(jù)時(shí),會(huì)先掃描在查詢區(qū)域的緯度范圍內(nèi)的所有數(shù)據(jù),造成很多經(jīng)度不在查詢范圍內(nèi)的冗余數(shù)據(jù)掃描,大大增加了數(shù)據(jù)查詢時(shí)間,降低了查詢性能。

3.3 HRQ區(qū)域時(shí)空查詢方法

為了使交通數(shù)據(jù)的經(jīng)緯度和時(shí)間三個(gè)維度在HBase行鍵中起到更好的索引效果,本文提出一種HRQ區(qū)域時(shí)空查詢方法。它將交通數(shù)據(jù)的經(jīng)緯度信息通過(guò)Geohash算法轉(zhuǎn)為一維字符串,再與時(shí)間組合成一個(gè)新的字符串,作為HBase記錄的行鍵,其組合過(guò)程如圖3所示,數(shù)據(jù)在HBase表中的邏輯數(shù)據(jù)如表2所示。

圖3 Geohash編碼加時(shí)間的行鍵組合示例圖

RowkeyDATAcarIDlatlontimeOtherswx494q937nbt2012021112122京A666639.5867386N116.1163483E2012-02-1112:12:291,5000,m

基于該方法的時(shí)空區(qū)域查詢算法如下所示。

第一步,確定查詢區(qū)域;

第二步,將查詢區(qū)域的左下和右上兩個(gè)頂點(diǎn)的經(jīng)緯度轉(zhuǎn)為Geohash編碼;

第三步,將兩個(gè)Geohash編碼分別與查詢的起止時(shí)間組合得到起止行鍵;

第四步,設(shè)置行鍵過(guò)濾器和值過(guò)濾器;

第五步,掃描HBase數(shù)據(jù)庫(kù),如果是矩形區(qū)域查詢,輸出最終結(jié)果值;如果是圓形區(qū)域查詢,執(zhí)行第六步;

第六步,從掃描出來(lái)的結(jié)果集中找出所有到查詢點(diǎn)的距離小于查詢半徑的結(jié)果,并輸出。

以Geohash編碼和時(shí)間組合作為的行鍵相對(duì)于經(jīng)緯度加時(shí)間組合作為的行鍵更短,減少了冗余存儲(chǔ)空間,最重要的是Geohash編碼使得經(jīng)緯度在行鍵中具有了同等權(quán)重,并且Geohash編碼本身代表的就是一個(gè)區(qū)域范圍,在查詢時(shí)通過(guò)行鍵匹配即可直接找到對(duì)應(yīng)的查詢區(qū)域或其最小外接矩形。在查詢掃描時(shí),先通過(guò)居于行鍵首字段的Geohash編碼找到整個(gè)查詢區(qū)域的最小外接矩形內(nèi)的車輛信息,然后通過(guò)居于行鍵末端的時(shí)間來(lái)進(jìn)行行鍵過(guò)濾,找出查詢區(qū)域的最小外接矩形內(nèi)屬于查詢時(shí)間范圍內(nèi)的車輛信息,最后再通過(guò)值過(guò)濾器得到最終的結(jié)果值。即掃描的是由查詢條件的緯度范圍和經(jīng)度范圍組成的區(qū)域內(nèi)的數(shù)據(jù),而不是所有屬于查詢緯度范圍內(nèi)的數(shù)據(jù),大量減少了冗余掃描,減少了查詢時(shí)間,從而提升了區(qū)域查詢的性能。為保證查找出符合條件的所有數(shù)據(jù),實(shí)際查詢時(shí)掃描的區(qū)域總是會(huì)比需要查詢的區(qū)域要大一些,即總是會(huì)有冗余掃描,HBase的值過(guò)濾器會(huì)過(guò)濾掉所有不符合查詢條件的數(shù)據(jù),保證最終結(jié)果都在查詢的時(shí)空區(qū)域內(nèi),從而保證了結(jié)果的準(zhǔn)確性。

在實(shí)際查詢時(shí),基于Geohash編碼的特性,可以將查詢區(qū)域的最小外包矩形與Geohash編碼表示的空間區(qū)域?qū)?yīng)起來(lái),這樣查詢時(shí)直接找到查詢區(qū)域所在的最小外接Geohash網(wǎng)格即可,如圖4所示,當(dāng)它們處于1關(guān)系時(shí)可以直接查詢包含查詢區(qū)域Q的G網(wǎng)格來(lái)獲取查詢結(jié)果。但是由于Geohash網(wǎng)格代表的是固定區(qū)域,而實(shí)際查詢時(shí),選擇的區(qū)域很有可能會(huì)剛好位于幾個(gè)Geohash網(wǎng)格的邊界上,如圖4中的關(guān)系2所示,所以在實(shí)際查詢時(shí),需要對(duì)查詢區(qū)域進(jìn)行一定處理,以與Geohash網(wǎng)格對(duì)應(yīng)。

圖4 Q與G的關(guān)系

對(duì)于圖4中的關(guān)系2的情況,傳統(tǒng)的Geohash區(qū)域處理方法是將G和它鄰近的8個(gè)區(qū)域一起來(lái)作為查詢區(qū)域,如圖5(a)所示。這種處理方法會(huì)造成大量的冗余數(shù)據(jù)掃描,像圖5(b)中所示,如果Q處于實(shí)線框的情況,只需要掃描4格Geohash網(wǎng)格,實(shí)際卻掃描了9格,處于虛線框的情況,由于Q包含了整個(gè)G,則需要按圖4中的1情況處理,這樣實(shí)際掃描的Geohash網(wǎng)格是32格,而實(shí)際只需要掃描12格。為了盡量減少冗余數(shù)據(jù)掃描,本文的HRQ方法采用了一種新的區(qū)域處理方法,對(duì)圖4中的兩種情況都適用,其算法如下所示。

算法:查詢區(qū)域處理算法

輸入:查詢區(qū)域的頂點(diǎn)經(jīng)緯度p1(Lat1,Lon1)、p2(Lat2,Lon2)、p3(Lat3,Lon3)、p4(Lat4,Lon4)或查詢點(diǎn)p(Latp,Lonp)和半徑D。

輸出:Geohash網(wǎng)格集G

算法步驟:

1) 判斷查詢類型,如果是矩形區(qū)域查詢,執(zhí)行步驟3;如果是圓形區(qū)域查詢,執(zhí)行步驟2)。

3) 分別將p1、p2、p3、p4的經(jīng)緯度值轉(zhuǎn)為Geohash編碼g1、g2、g3、g4。

4) 獲取g1、g2、g3、g4的相同前綴g,即找到包含g1、g2、g3、g4的最小外接Geohash網(wǎng)格。

5) 分別取g1、g2、g3、g4中除去前綴g之后的第一位Geohash碼b1、b2、b3、b4。

6) 將32個(gè)base32標(biāo)示碼依次加入到鏈表listb中。

7) 遍歷listb,找出在b1～b4圍成的區(qū)域內(nèi)的base32標(biāo)識(shí)碼(含b1～b4),并加上Geohash前綴g之后依次添加到Geohash網(wǎng)格集G中。

8) 返回Geohash網(wǎng)格集G。

該算法得到的Geohash網(wǎng)格集G中的元素是查詢區(qū)域在其最小外接的Geohash網(wǎng)格內(nèi)跨越的所有Geohash子網(wǎng)格,即需要掃描的整個(gè)Geohash區(qū)域。查詢算法只需依次查詢G中各個(gè)Geohash子網(wǎng)格內(nèi)的數(shù)據(jù),最后合并結(jié)果值就可以得到最終的結(jié)果值。該算法通過(guò)第五步過(guò)濾掉了包含查詢區(qū)域的最小外接Geohash網(wǎng)格內(nèi)所有與查詢區(qū)域無(wú)交集的Geohash子網(wǎng)格,大大減少了冗余區(qū)域的查詢,使得查詢的冗余數(shù)據(jù)明顯減少,例如對(duì)于表4中的關(guān)系1的情況,只需要掃描G中的12個(gè)子網(wǎng)格即可,減少了20格子網(wǎng)格的掃描,對(duì)表4中的關(guān)系2的情況只需掃描4個(gè)Geohash子網(wǎng)格,減少了5個(gè)Geohash子網(wǎng)格?？梢娫摲椒ù蟠鬁p小了冗余數(shù)據(jù)的掃描。

圖5(a) 鄰近單元a

圖5(b) 鄰近單元b

4 實(shí)驗(yàn)對(duì)比及分析

本文從時(shí)空區(qū)域的區(qū)域范圍和時(shí)間范圍以及數(shù)據(jù)集的量級(jí)三個(gè)方面來(lái)對(duì)本文提出的HRQ區(qū)域查詢方法和傳統(tǒng)的經(jīng)緯度加時(shí)間的區(qū)域查詢方法進(jìn)行交通數(shù)據(jù)的區(qū)域查詢性能對(duì)比實(shí)驗(yàn)。

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

1) 軟件環(huán)境:Hadoop-1.2.1、Zookeeper-3.4.6、HBase-0.94.8、jdk7、centos7操作系統(tǒng)。

2) 硬件環(huán)境:2顆四核處理器,32G內(nèi)存,10T硬盤的測(cè)試服務(wù)器兩臺(tái);2顆四核處理器,8G內(nèi)存,10T硬盤的測(cè)試服務(wù)器三臺(tái);2顆四核處理器,4G內(nèi)存,500G硬盤的測(cè)試客戶機(jī)一臺(tái)。

實(shí)驗(yàn)數(shù)據(jù):本文的實(shí)驗(yàn)數(shù)據(jù)來(lái)自實(shí)驗(yàn)室購(gòu)買的的實(shí)際車輛GPS數(shù)據(jù),其中千萬(wàn)級(jí)數(shù)據(jù)集為2012年10月03日的數(shù)據(jù),約3000萬(wàn)條記錄,億級(jí)數(shù)據(jù)集為2012年10月03日到2012年10月06日的數(shù)據(jù),約1.1億條記錄。數(shù)據(jù)未存入到HBase數(shù)據(jù)庫(kù)之前的結(jié)構(gòu)如表3所示,主要由GPS唯一標(biāo)識(shí)符(ID)、數(shù)據(jù)采集時(shí)間點(diǎn)(TIME)、經(jīng)度(LON)、緯度(LAT)以及其他一些信息組成。經(jīng)過(guò)處理后存到HBase中的數(shù)據(jù)的結(jié)構(gòu)如表4所示,只存儲(chǔ)了GPS唯一標(biāo)識(shí)符(ID)、數(shù)據(jù)采集時(shí)間點(diǎn)(TIME)、經(jīng)度(LON)和緯度(LAT)四個(gè)信息。

表3 原始數(shù)據(jù)的結(jié)構(gòu)

表4 HBase中數(shù)據(jù)的結(jié)構(gòu)

實(shí)驗(yàn)一在千萬(wàn)級(jí)數(shù)據(jù)集下分別對(duì)兩種方法進(jìn)行查詢區(qū)域點(diǎn)為東經(jīng)116.3265305、北緯39.8885880,半徑分別為0.5km、1km、1.5km,時(shí)間點(diǎn)為(2012-10-0301:51:23)的交通數(shù)據(jù)區(qū)域查詢實(shí)驗(yàn)。

實(shí)驗(yàn)結(jié)果如圖6所示,在查詢范圍較小的時(shí)候,HRQ方法相對(duì)于經(jīng)緯度加時(shí)間方法的性能優(yōu)勢(shì)不是很明顯,但是隨著查詢區(qū)域范圍的擴(kuò)大性能優(yōu)勢(shì)也隨之變得明顯,即HRQ在相同時(shí)間點(diǎn)的區(qū)域時(shí)空查詢上性能要優(yōu)于傳統(tǒng)的HBase交通數(shù)據(jù)區(qū)域查詢方法,并且查詢區(qū)域越大,性能優(yōu)勢(shì)越明顯。

圖6 時(shí)間點(diǎn)的車輛數(shù)據(jù)區(qū)域查詢

實(shí)驗(yàn)二分別對(duì)兩種查詢方法在千萬(wàn)級(jí)數(shù)據(jù)集和億級(jí)數(shù)據(jù)集下進(jìn)行時(shí)間范圍在(2012-10-03 01:51:23,2012-10-03 01:51:33)、(2012-10-03 01:51:23,2012-10-03 01:52:23)、(2012-10-03 01:51:23,2012-10-03 02:51:23)、(2012-10-03 01:51:23,2012-10-03 06:51:23)、(2012-10-03 01:51:23,2012-10-0311:51:23)、(2012-10-03 01:51:23,2012-10-0316:51:23)、(2012-10-03 01:51:23,2012-10-04 01:51:23)內(nèi)、查詢區(qū)域中心點(diǎn)為東經(jīng)116.3265305,北緯39.8885880、查詢半徑為1km的區(qū)域進(jìn)行車輛數(shù)據(jù)時(shí)空查詢實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖7和8所示,可以看出,HRQ在時(shí)間范圍的交通數(shù)據(jù)區(qū)域查詢上,性能要明顯優(yōu)于經(jīng)緯度加時(shí)間的HBase交通數(shù)據(jù)區(qū)域查詢方法,其中千萬(wàn)級(jí)數(shù)據(jù)集下查詢性能要高40%以上,億級(jí)數(shù)據(jù)集下查詢性能高30%以上。

綜合圖7和圖8的結(jié)果可以看出隨著數(shù)據(jù)集的增大,HRQ方法相對(duì)于經(jīng)緯度加時(shí)間的方法的優(yōu)勢(shì)會(huì)降低。主要原因是在HRQ方法中時(shí)間信息處于行鍵的最后位置,時(shí)間的索引作用最低,它幾乎只能靠行鍵過(guò)濾器來(lái)起作用。這使得同一查詢條件下的區(qū)域查詢,HBase中存儲(chǔ)記錄跨越的時(shí)間區(qū)間越大掃描到的冗余數(shù)據(jù)就越多,從而造成查詢性能降低,即HRQ的查詢性能會(huì)隨著HBase中存儲(chǔ)記錄所跨越的時(shí)間區(qū)間變大而降低,這是今后的研究工作中需要解決的一個(gè)問(wèn)題。

圖7 千萬(wàn)級(jí)數(shù)據(jù)集時(shí)間范圍車輛數(shù)據(jù)區(qū)域查詢

圖8 億級(jí)數(shù)據(jù)集時(shí)間范圍車輛數(shù)據(jù)區(qū)域查詢

綜合實(shí)驗(yàn)結(jié)果分析可知,本文提出的HRQ交通數(shù)據(jù)區(qū)域查詢方法相較直接由經(jīng)緯度加時(shí)間實(shí)現(xiàn)的傳統(tǒng)交通數(shù)據(jù)區(qū)域查詢方法有著明顯的查詢性能優(yōu)勢(shì)。但是該方法還有不足之處,由于在方法中時(shí)間在行鍵中處于靠后位置,所以時(shí)間起到的索引能力要遠(yuǎn)遠(yuǎn)小于Geohash起到的索引能力,使得查詢性能隨著HBase存儲(chǔ)記錄跨越的時(shí)間區(qū)間的變大而降低,所以該方法適合用在HBase中存儲(chǔ)的記錄的時(shí)間區(qū)間跨度不是很大的場(chǎng)景。本文也考慮過(guò)將時(shí)間放在前面,但是那樣Geohash的索引效果就會(huì)降低,只在查詢時(shí)間范圍較小的交通數(shù)據(jù)區(qū)域查詢上會(huì)有很好的效果。

5 結(jié)語(yǔ)

本文利用了Geohash算法降維和HBase行鍵的特點(diǎn),提出的基于HBase的交通數(shù)據(jù)區(qū)域查詢方法(HRQ)。為了提高對(duì)HBase中交通數(shù)據(jù)的區(qū)域查詢,該方法將車輛GPS數(shù)據(jù)的經(jīng)緯度通過(guò)Geohash算法轉(zhuǎn)為一維字符串,再和時(shí)間信息一起組合作為HBase的行鍵,可以在檢索數(shù)據(jù)時(shí)大大減少數(shù)據(jù)的掃描范圍,一定程度上提升了區(qū)域查詢的性能,具有一定實(shí)際應(yīng)用價(jià)值。未來(lái)的工作方向是研究如何使時(shí)間、經(jīng)度和緯度這三個(gè)屬性的值在行鍵中盡可能的具有相等的權(quán)值,以更好地提升交通數(shù)據(jù)區(qū)域查詢性能。

[1] 申德榮,于戈,王習(xí),等.支持大數(shù)據(jù)管理的NoSQL系統(tǒng)研究綜述[J].軟件學(xué)報(bào),2013(8):1786-1803. SHEN Derong, YU Ge, WANG Xi, et al. Survey on NoSQL for management of big data. RuanJianXueBao/Journal of Software[J]. 2013,24(8):1786-1803.

[2] 葛微,羅圣美,周文輝,等.HiBase:一種基于分層式索引的高效HBase查詢技術(shù)與系統(tǒng)[J].計(jì)算機(jī)學(xué)報(bào),2016,39(1):140-153. GE Wei, LUO Shengmei, ZHOU Wenhui, et al. HiBase: A Hierarchical Indexing Mechanism and System for Efficient HBase Query[J]. Chinese Journal of Computers,2016,39(1):140-153.

[3] Nick Dimiduk, Amandeep Khurana. HBase實(shí)戰(zhàn)[M].謝磊,譯.北京:人民郵電出版社,2013:197-228. Nick Dimiduk, AmandeepKhurana. HBase In ACTION[M]. XIE Lei, translate. Beijing: Posts & Telecom Press,2013:197-228.

[4]David Taniar, Wenny Rahayu. A taxonomy for region queries in spatial databases[J]. Journal of Computer and System Sciences,2015,81:1508-1531.

[5] Geohash[Z]. https://en.wikipedia.org/wiki/Geohash.

[6] Shoji Nishimura, Sudipto Das, Divyakant Agrawal, et al. MD-HBase:design and implem-entation of an elastic data infrastructure for cloud-scallocaltion services[J]. Distrib Parallel Databases,2013,31:289-319.

[7] Anthony Fox, Chris Eichelberger, James Hughes, et al. Spatio-temporal Indexing in Non-relational Distrbuted Databases[C]//IEEE International Conference on Big Data. Santa Clara, CA, USA,2013.

[8] GONG Jun, KE Shengnan, ZHU Qing, et al. An Efficient Trajectory Data Index Inegrating R-tree, Hash and B*-tree[J]. Acta Geodaetcaet Cartographica Sinica,2015,44(5):570-577.

[9] 郭超,李坤,王永炎,等.面向?qū)崟r(shí)定位系統(tǒng)的位置區(qū)域索引[J].計(jì)算機(jī)研究與發(fā)展,2011,48(10):1908-1917. GUO Chao, LI Kun, Wang Yongyan, et al. A location Index for Range Query in Real-Time Locating System[J]. Journal of Computer Research and Development,2011,48(10):1908-1917.

[10] 劉潤(rùn)濤,郝忠孝.R-樹和四叉樹的空間索引結(jié)構(gòu):RQOP_樹[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2010,42(2):324-327. LIU Runtao, HAO Zhongxiao. Spatial index structure based on R-tree and quadtree: RQOP_tree[J]. Journal of Harbin Institute of Technology,2010,42(2):324-327.

[11] 何婧,吳躍,楊帆,等.基于KD樹和R樹的多維云數(shù)據(jù)索引[J].計(jì)算機(jī)應(yīng)用,2014,34(11):3218-3221,3278. HE Jing, WU Yue, YANG Fan, et al. Multi-dimensional cloud index based on KD-tree and R-tree[J]. Journal of Computer Applications,2014,34(11):3218-3221,3278.

[12] 金安,程承旗,宋樹華,等.基于Geohash的面數(shù)據(jù)區(qū)域查詢[J].地理與地理信息科學(xué),2013,29(5):31-33. JIN An, CHENG Chengqi. SONG Shuhua, et al. Regional Query of Area Data Based on Geohash[J]. Geography and Geo-Information Science,2013,29(5):31-33.

[13] Shen D, Fang J, Han Y. A Nearby Vehicle Search Algorithm Based on HBase Spatial Index[C]//Web Information System and Application Conference. IEEE,2015:71-74.

A Regional Query Method of Traffic Data Based on HBase

LI Dong FANG Jun

(Beijing Key Laboratory on Integration and Analysis of Large-scale Stream Data, North China University of Technology, Beijing 100041)

With the development of intelligent traffic, traffic data has exponential growth. To improve the query’s performance of spatial and temporal region, this article proposes HRQ region query methods of traffic data based on HBase. The method uses the Geohash algorithm to make traffic data’s latitude and longitude information become a Geohash code, and combines time to form HBase’s keys. This article designs the corresponding query algorithms too. Experimental results show that, compared to the direct combination of latitude, longitude and time as HBase’s keys, the performance of HRQ method is 30% higher in time-based region query, and HRQ’s performance advantage increases as query area increases in region’s query based on regional.

HBase, Geohash algorithm, regional query, massive traffic, spatial and tempal feature

2016年8月11日,

2016年9月27日

北京市自然科學(xué)基金重點(diǎn)資助項(xiàng)目“面向大規(guī)模流式數(shù)據(jù)處理的數(shù)據(jù)空間理論與關(guān)鍵技術(shù)研究”(編號(hào):4131001)資助。

李冬,男,碩士研究生,研究方向:云數(shù)據(jù)管理。房俊,男,博士,副研究員,研究方向:服務(wù)計(jì)算和云計(jì)算。

TP311

10.3969/j.issn.1672-9722.2017.02.008