基于HBase的交通數據區域查詢方法

李 冬 房 俊

(北方工業大學大規模流數據集成與分析技術北京市重點實驗室 北京 100041)

基于HBase的交通數據區域查詢方法

李 冬 房 俊

(北方工業大學大規模流數據集成與分析技術北京市重點實驗室 北京 100041)

隨著智能交通的發展,交通數據呈現出指數性增長。為了提升時空區域查詢性能,論文提出了一種基于HBase的交通數據區域查詢方法HRQ。該方法利用交通數據的三維時空特性,采用Geohash算法將交通數據的經緯度信息轉為Geohash編碼,然后與時間組合作為HBase行鍵,并設計了相應的查詢算法。實驗結果表明,與直接組合經緯度和時間作為行鍵的方法相比,在基于時間范圍的區域查詢上HRQ方法的性能要高30%以上,在基于區域范圍的區域查詢上HRQ的性能優勢隨著查詢區域的增大而增加。

HBase; Geohash算法; 區域查詢; 海量交通數據; 時空特性

Class Number TP311

1 引言

隨著智能交通的發展,交通數據呈現出指數性增長。傳統的關系型數據庫無法應對海量交通數據的高效存儲和處理需求,以HBase為代表的NoSQL數據庫[1]具有擴展性強、并發性能好、數據模型靈活等優點,在海量數據存儲和查詢方面具有先天的優勢,國內外很多大型互聯網公司都用它來存儲和管理海量數據[2～3]。

車輛數據的區域查詢[4]是智能交通應用的一種基礎數據服務,像Uber和滴滴等打車軟件的叫車服務和公安機關的刑偵過程一般都需要對車輛GPS數據等交通數據進行區域查詢。交通數據具有三維時空特征,對交通數據的區域查詢其實就是一種時空查詢,這對于只能在行鍵上構建字典序索引的HBase是一個挑戰,即如何實現在HBase中對交通數據進行快速有效的區域查詢是一大難點。

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

2 相關工作

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

針對時空數據的多維特性進行降維處理,在降維得到的信息上構建索引來提升空間區域查詢性能,是近年來的一個新的研究熱點。文獻[12]提出了一種在Mysql數據庫中實現的基于Geohash的面數據區域查詢方法,即將數據的經緯度信息轉為Geohash編碼,存到一個列中,并在該列上建索引,這種方法在關系型數據庫中相對于基于經緯度、R樹的查詢有一定的優勢。文獻[13]提出了一種在HBase數據庫中實現的基于Geohash的車輛數據鄰近查詢方法,該方法將車輛信息的經緯得到Geohash編碼與車牌ID組合作為HBase行鍵,來實現車輛數據的空間區域查詢。上述兩種研究工作只利用了數據的空間信息,僅對只有空間特征的數據查詢具有較好的性能。

3 基于HBase的交通數據區域查詢

3.1 相關定義

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

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

其中,a=Lata-Lotb為兩點緯度之差,b=Lona-Lonb為兩點經度之差。

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

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

圖1 最小外接矩形

定義5 區域時空查詢是指在對某一選中區域,在此區域內查詢在時間段(Ts,Te)內的交通數據。即求Csub?C,使得:

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

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

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

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

3.2 基于HBase區域查詢的一般方法

圖2 經緯度加時間的行鍵組合示例圖

由于交通數據具有時空三維特性,結合HBase行鍵的特征,想要能夠有效檢索出具有時空特性的交通數據,就需要將交通數據中時空的三個維度屬性全都放在HBase行鍵中。HBase傳統的區域時空查詢方法是直接用經緯度加時間作為行鍵實現的,其組合過程如圖2所示。采用該方法時,數據存儲到HBase中的邏輯數據模型如表1所示。

表1 基于經緯度的HBase數據模型

基于該方法的時空區域查詢步驟如下:

第一步,確定查詢區域;

第二步,通過查詢區域的左下角和右上角兩個頂點的經緯度和查詢起止時間,確定需要掃描HBase的行鍵范圍;

第三步,設置行鍵過濾器和值過濾器;

第四步,對HBase進行掃描,輸出結果集。

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

3.3 HRQ區域時空查詢方法

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

圖3 Geohash編碼加時間的行鍵組合示例圖

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

基于該方法的時空區域查詢算法如下所示。

第一步,確定查詢區域;

第二步,將查詢區域的左下和右上兩個頂點的經緯度轉為Geohash編碼;

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

第四步,設置行鍵過濾器和值過濾器;

第五步,掃描HBase數據庫,如果是矩形區域查詢,輸出最終結果值;如果是圓形區域查詢,執行第六步;

第六步,從掃描出來的結果集中找出所有到查詢點的距離小于查詢半徑的結果,并輸出。

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

在實際查詢時,基于Geohash編碼的特性,可以將查詢區域的最小外包矩形與Geohash編碼表示的空間區域對應起來,這樣查詢時直接找到查詢區域所在的最小外接Geohash網格即可,如圖4所示,當它們處于1關系時可以直接查詢包含查詢區域Q的G網格來獲取查詢結果。但是由于Geohash網格代表的是固定區域,而實際查詢時,選擇的區域很有可能會剛好位于幾個Geohash網格的邊界上,如圖4中的關系2所示,所以在實際查詢時,需要對查詢區域進行一定處理,以與Geohash網格對應。

圖4 Q與G的關系

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

算法:查詢區域處理算法

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

輸出:Geohash網格集G

算法步驟:

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

3) 分別將p1、p2、p3、p4的經緯度值轉為Geohash編碼g1、g2、g3、g4。

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

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

6) 將32個base32標示碼依次加入到鏈表listb中。

7) 遍歷listb,找出在b1～b4圍成的區域內的base32標識碼(含b1～b4),并加上Geohash前綴g之后依次添加到Geohash網格集G中。

8) 返回Geohash網格集G。

該算法得到的Geohash網格集G中的元素是查詢區域在其最小外接的Geohash網格內跨越的所有Geohash子網格,即需要掃描的整個Geohash區域。查詢算法只需依次查詢G中各個Geohash子網格內的數據,最后合并結果值就可以得到最終的結果值。該算法通過第五步過濾掉了包含查詢區域的最小外接Geohash網格內所有與查詢區域無交集的Geohash子網格,大大減少了冗余區域的查詢,使得查詢的冗余數據明顯減少,例如對于表4中的關系1的情況,只需要掃描G中的12個子網格即可,減少了20格子網格的掃描,對表4中的關系2的情況只需掃描4個Geohash子網格,減少了5個Geohash子網格。可見該方法大大減小了冗余數據的掃描。

圖5(a) 鄰近單元a

圖5(b) 鄰近單元b

4 實驗對比及分析

本文從時空區域的區域范圍和時間范圍以及數據集的量級三個方面來對本文提出的HRQ區域查詢方法和傳統的經緯度加時間的區域查詢方法進行交通數據的區域查詢性能對比實驗。

實驗環境:

1) 軟件環境:Hadoop-1.2.1、Zookeeper-3.4.6、HBase-0.94.8、jdk7、centos7操作系統。

2) 硬件環境:2顆四核處理器,32G內存,10T硬盤的測試服務器兩臺;2顆四核處理器,8G內存,10T硬盤的測試服務器三臺;2顆四核處理器,4G內存,500G硬盤的測試客戶機一臺。

實驗數據:本文的實驗數據來自實驗室購買的的實際車輛GPS數據,其中千萬級數據集為2012年10月03日的數據,約3000萬條記錄,億級數據集為2012年10月03日到2012年10月06日的數據,約1.1億條記錄。數據未存入到HBase數據庫之前的結構如表3所示,主要由GPS唯一標識符(ID)、數據采集時間點(TIME)、經度(LON)、緯度(LAT)以及其他一些信息組成。經過處理后存到HBase中的數據的結構如表4所示,只存儲了GPS唯一標識符(ID)、數據采集時間點(TIME)、經度(LON)和緯度(LAT)四個信息。

表3 原始數據的結構

表4 HBase中數據的結構

實驗一在千萬級數據集下分別對兩種方法進行查詢區域點為東經116.3265305、北緯39.8885880,半徑分別為0.5km、1km、1.5km,時間點為(2012-10-0301:51:23)的交通數據區域查詢實驗。

實驗結果如圖6所示,在查詢范圍較小的時候,HRQ方法相對于經緯度加時間方法的性能優勢不是很明顯,但是隨著查詢區域范圍的擴大性能優勢也隨之變得明顯,即HRQ在相同時間點的區域時空查詢上性能要優于傳統的HBase交通數據區域查詢方法,并且查詢區域越大,性能優勢越明顯。

圖6 時間點的車輛數據區域查詢

實驗二分別對兩種查詢方法在千萬級數據集和億級數據集下進行時間范圍在(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)內、查詢區域中心點為東經116.3265305,北緯39.8885880、查詢半徑為1km的區域進行車輛數據時空查詢實驗。實驗結果如圖7和8所示,可以看出,HRQ在時間范圍的交通數據區域查詢上,性能要明顯優于經緯度加時間的HBase交通數據區域查詢方法,其中千萬級數據集下查詢性能要高40%以上,億級數據集下查詢性能高30%以上。

綜合圖7和圖8的結果可以看出隨著數據集的增大,HRQ方法相對于經緯度加時間的方法的優勢會降低。主要原因是在HRQ方法中時間信息處于行鍵的最后位置,時間的索引作用最低,它幾乎只能靠行鍵過濾器來起作用。這使得同一查詢條件下的區域查詢,HBase中存儲記錄跨越的時間區間越大掃描到的冗余數據就越多,從而造成查詢性能降低,即HRQ的查詢性能會隨著HBase中存儲記錄所跨越的時間區間變大而降低,這是今后的研究工作中需要解決的一個問題。

圖7 千萬級數據集時間范圍車輛數據區域查詢

圖8 億級數據集時間范圍車輛數據區域查詢

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

5 結語

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

[1] 申德榮,于戈,王習,等.支持大數據管理的NoSQL系統研究綜述[J].軟件學報,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查詢技術與系統[J].計算機學報,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實戰[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] 郭超,李坤,王永炎,等.面向實時定位系統的位置區域索引[J].計算機研究與發展,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-樹和四叉樹的空間索引結構:RQOP_樹[J].哈爾濱工業大學學報,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樹的多維云數據索引[J].計算機應用,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的面數據區域查詢[J].地理與地理信息科學,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日

北京市自然科學基金重點資助項目“面向大規模流式數據處理的數據空間理論與關鍵技術研究”(編號:4131001)資助。

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

TP311

10.3969/j.issn.1672-9722.2017.02.008