面向海量交通數(shù)據(jù)的HBase時空索引

房 俊，李 冬，郭會云，王嘉怡

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

(*通信作者電子郵箱fangjun@ncut.edu.cn)

面向海量交通數(shù)據(jù)的HBase時空索引

房 俊*，李 冬，郭會云，王嘉怡

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

(*通信作者電子郵箱fangjun@ncut.edu.cn)

針對HBase無法直接建立時空索引所帶來的交通數(shù)據(jù)查詢性能問題，基于HBase行鍵設(shè)計了面向海量交通數(shù)據(jù)的HBase時空索引。首先利用Geohash降維方法將二維空間位置數(shù)據(jù)轉(zhuǎn)化為一維編碼，再與時間維度進(jìn)行組合；然后根據(jù)組合順序的不同，提出了四種結(jié)構(gòu)模型，分別討論了模型的具體構(gòu)成以及交通數(shù)據(jù)查詢中的適應(yīng)面；最后提出了相應(yīng)的時空索引管理算法及基于Hbase時空索引的交通數(shù)據(jù)查詢方法。通過實(shí)驗驗證了提出的HBase時空索引結(jié)構(gòu)能有效提升海量交通數(shù)據(jù)的區(qū)域查詢性能，并比較了四種時空索引結(jié)構(gòu)在不同數(shù)據(jù)規(guī)模、不同查詢半徑以及不同時間范圍的查詢性能，量化驗證了不同索引結(jié)構(gòu)在交通數(shù)據(jù)查詢中的適應(yīng)場景。

海量交通數(shù)據(jù)；HBase；Geohash；時空索引；區(qū)域查詢

0 引言

近年來城市智能交通在云計算和大數(shù)據(jù)技術(shù)的推動下，取得了飛躍式的發(fā)展，對其所產(chǎn)生的海量交通數(shù)據(jù)進(jìn)行有效處理，既可以為城市管理者提供交通管理決策支持，也可以為公安部門刑偵工作提供支持。

關(guān)系型數(shù)據(jù)庫無法實(shí)現(xiàn)海量數(shù)據(jù)的有效存儲與處理，而NoSQL[1]數(shù)據(jù)庫恰恰具有優(yōu)異的海量數(shù)據(jù)存儲能力，目前在智能交通領(lǐng)域，以HBase為代表的NoSQL數(shù)據(jù)庫逐漸得到了廣泛應(yīng)用。

交通數(shù)據(jù)是一類典型的時空數(shù)據(jù)。時空數(shù)據(jù)的快速查詢一般都通過建立時空索引來實(shí)現(xiàn)。關(guān)系型數(shù)據(jù)庫常采用R樹及其變種、四叉樹和K-D樹(K-Dimension tree)等[2-5]結(jié)構(gòu)來實(shí)現(xiàn)時空索引，但交通時空數(shù)據(jù)的實(shí)時產(chǎn)生使得維護(hù)這類索引結(jié)構(gòu)代價非常高，并且應(yīng)用時需要修改原有程序框架，具有侵入性,并不適用于創(chuàng)建海量交通數(shù)據(jù)的時空索引。在此情形下，如何設(shè)計高效、無侵入的HBase時空索引，實(shí)現(xiàn)海量交通數(shù)據(jù)的快速時空查詢成了一大挑戰(zhàn)。

基于HBase只能通過行鍵(Rowkey)實(shí)現(xiàn)高效索引的事實(shí)，本文主要探討如何在HBase行鍵上基于三維(時間、經(jīng)度、緯度)時空數(shù)據(jù)實(shí)現(xiàn)索引結(jié)構(gòu)。Geohash[6]是一種有效的空間降維方法，基于Geohash與時間維度的不同組合機(jī)制，本文提出了適合不同應(yīng)用場景的四種HBase時空索引結(jié)構(gòu)，能夠有效地通過HBase行鍵和過濾器來實(shí)現(xiàn)對海量交通數(shù)據(jù)的時空查詢。

1 相關(guān)工作

HBase不直接支持多維索引，僅支持在Rowkey上建立索引。目前，國內(nèi)外在HBase多維索引研究上，已經(jīng)產(chǎn)生了部分研究結(jié)果，下面分別進(jìn)行介紹。

1.1 二級索引

華為公司的HBase二級索引[7]基于協(xié)處理器實(shí)現(xiàn)，索引建好后，對HBase的scan、Puts、Deletes操作使用HBase原生代碼(無需任何改動)即可獲得索引的效果；但是它需要在建表時指定索引列(且不支持動態(tài)修改)，同時代碼對HBase本身侵入性很大，難以升級維護(hù)。

360公司的HBase二級索引方案[8]是在吸收華為索引的優(yōu)點(diǎn)并摒棄其缺點(diǎn)的基礎(chǔ)上建立的，它對HBase的侵入性?。磺宜饕蛿?shù)據(jù)在同一個region上，避免了索引與數(shù)據(jù)不在同一服務(wù)器上造成的I/O通信，減少了查詢時間。

HBase二級索引雖然可以實(shí)現(xiàn)對多維數(shù)據(jù)的索引，但是時空查詢請求一般需要多次查詢候選數(shù)據(jù)，這會大幅降低查詢速度，并不適合交通數(shù)據(jù)的時空查詢。

1.2 空間索引

文獻(xiàn)[9]提出利用Geohash算法進(jìn)行空間降維實(shí)現(xiàn)的索引結(jié)構(gòu)，該方案實(shí)現(xiàn)簡單，不僅能有效提升鄰近車輛查詢的性能，在具體應(yīng)用時，也不需要更改原有系統(tǒng)的架構(gòu)。

文獻(xiàn)[10]提出了MD-HBase索引方案，它是一種多維空間索引(Multi-Dimensional index)方案，采用了K-D樹和四叉樹對查詢區(qū)域進(jìn)行劃分，并通過Z曲線將區(qū)域線性化，將線性化后的值作為HBase Rowkey來實(shí)現(xiàn)索引。

這兩種空間索引結(jié)構(gòu)都是采用降維思路，對空間查詢有較好的性能，雖然不能很好支持時空查詢，但其思路及實(shí)現(xiàn)方法非常具有借鑒價值。

1.3 時空索引

文獻(xiàn)[11]提出的UQE-Index索引結(jié)構(gòu)(Update and Query Efficient index framework)是一種基于HBase的、支持高吞吐率的寫入和多維查詢的索引結(jié)構(gòu)。這種索引結(jié)構(gòu)實(shí)現(xiàn)復(fù)雜，將數(shù)據(jù)分為實(shí)時數(shù)據(jù)和歷史數(shù)據(jù)，其中：實(shí)時數(shù)據(jù)的時間和空間分開建索引，時間維用的是B+樹，空間維用的是四叉樹或K-D樹；而對歷史數(shù)據(jù)采用的是R樹或網(wǎng)格。由于B樹和R樹的使用，使得這種索引結(jié)構(gòu)在數(shù)據(jù)量過大時，索引的維護(hù)會變得困難，不適用于具有實(shí)時數(shù)據(jù)存儲要求的場景。

文獻(xiàn)[12]提出了一種基于Geohash編碼和時間組合的時空索引結(jié)構(gòu)，這種索引結(jié)構(gòu)實(shí)現(xiàn)簡單，它將一位Geohash編碼和時間的年月部分作為HBase的Rowkey，三位Geohash編碼作為列族名，三位Geohash編碼和時間的日時部分作為列名。這樣的結(jié)構(gòu)將一個對象一天的記錄都存在了表的同一行里，如果存放交通數(shù)據(jù)，一行就要存上幾萬條記錄，并且由于Rowkey里只有一位Geohash碼，在經(jīng)過行鍵掃描時，需要掃描的區(qū)域范圍會非常大，得到的初始結(jié)果集很大，需要耗費(fèi)大量的時間在值過濾上，非常不利于交通數(shù)據(jù)的時空區(qū)域快速查詢。

2 面向海量交通數(shù)據(jù)的HBase時空索引

基于HBase行鍵的索引具有簡便、無侵入性等特點(diǎn)，而Geohash作為空間降維方案，能夠?qū)⒍S空間映射到一維字符串，天然適合用于Hbase行鍵索引。借鑒上述思路，本文設(shè)計了四類組合Geohash與時間的時空索引，介紹其索引結(jié)構(gòu)，描述索引管理算法及基于索引的時空范圍查詢算法，并定性分析其適用場景。

2.1 索引結(jié)構(gòu)

2.1.1 GT時空索引

GT時空索引(Geo-Time index)由Geohash編碼加上時間組合而成，其結(jié)構(gòu)如圖1所示，在HBase行鍵中，Geohash編碼在前，時間在后。這種索引結(jié)構(gòu)中起主要索引作用的是Geohash編碼，時間起輔助作用。

圖1 GT時空索引結(jié)構(gòu)

基于GT時空索引的交通數(shù)據(jù)時空查詢過程是：先將查詢區(qū)域的經(jīng)緯度轉(zhuǎn)換為Geohash編碼，然后與HBase行鍵進(jìn)行匹配，確定在查詢區(qū)域內(nèi)的記錄范圍；接著經(jīng)過行過濾器過濾掉不在查詢時間范圍內(nèi)的記錄，進(jìn)一步縮小掃描范圍；最后再用值過濾器過濾得到最終的查詢結(jié)果。

一般來講，交通數(shù)據(jù)區(qū)域查詢的Geohash編碼是一個范圍，在行鍵匹配過程中，匹配到查詢起止行鍵的相同前綴的最后一位后，后續(xù)的行鍵索引功能就失效了，即靠后的時間幾乎沒有索引效果，只能通過行鍵過濾器來減少數(shù)據(jù)的掃描范圍。如果數(shù)據(jù)庫中存儲記錄的時間范圍比較大，索引效果就會出現(xiàn)明顯下降，故這種索引結(jié)構(gòu)僅適用于數(shù)據(jù)庫中存儲數(shù)據(jù)的時間范圍跨度比較小的情景。

2.1.2 TG時空索引

TG時空索引(Time-Geohash index)是由時間加Geohash編碼作為HBase行鍵實(shí)現(xiàn)的，其結(jié)構(gòu)如圖2所示，時間處于行鍵的首字段，即在數(shù)據(jù)索引時，時間起主要索引作用，Geohash編碼起輔助作用。

圖2 TG時空索引結(jié)構(gòu)

這種索引結(jié)構(gòu)的檢索數(shù)據(jù)過程是：先通過查詢時間匹配HBase行鍵，找到在查詢時間范圍內(nèi)的記錄，縮小需要掃描的數(shù)據(jù)范圍；然后通過行鍵過濾器過濾掉不在查詢的Geohash范圍內(nèi)的記錄，進(jìn)一步減少數(shù)據(jù)掃描的范圍；最后通過值過濾器得到最終查詢結(jié)果。

這種索引結(jié)構(gòu)適用于查詢時間范圍較小的交通數(shù)據(jù)區(qū)域查詢。如基于時間點(diǎn)的時空查詢，這種情況下，需要掃描的數(shù)據(jù)范圍時間相同，時間完全可以起到索引效果，而且Geohash編碼的相同前綴也會起作用，所以查詢效果會非常好。相反地，如果查詢時間范圍較大，效果則會變差，此時Geohash編碼失去索引能力，造成查詢性能下降。相比GT索引結(jié)構(gòu)，數(shù)據(jù)庫中交通數(shù)據(jù)記錄的時間范圍大小對TG索引結(jié)構(gòu)影響不大。

2.1.3 STG時空索引

營銷與貿(mào)易類的崗位描述中，企業(yè)對“團(tuán)隊合作精神”、“管理能力”、“語言表達(dá)溝通能力”、“組織協(xié)調(diào)”、“積極主動”被提及的次數(shù)最多，依次為75.62%、58.17%、57.61%、46.64%、44.41%?？梢娖髽I(yè)招聘外籍營銷人員，主要考量其綜合素質(zhì)。同時崗位對應(yīng)聘者的“英語”和“全球思維與跨文化意識”能力也提出了較高要求。因此，團(tuán)隊合作意識強(qiáng)、善于溝通、擁有良好的外語能力，且具有全球化意識的外籍人才更為企業(yè)所需求。

針對交通數(shù)據(jù)的特點(diǎn)，結(jié)合了GT和TG兩種索引結(jié)構(gòu)的優(yōu)點(diǎn)，將時間與Geohash編碼經(jīng)過特殊組合作為HBase行鍵構(gòu)建HBase時空索引，本文稱為STG時空索引(Special Time-Geo index)，其結(jié)構(gòu)如圖3所示，它將時間分割成年月日和時分秒兩部分，并將年月日作為行鍵首字符，然后是Geohash編碼，最后是時間的時分秒，即年月日+Geohash編碼+時分秒的結(jié)構(gòu)。

STG索引結(jié)構(gòu)檢索數(shù)據(jù)的過程是：先通過時間的年月日部分與Geohash編碼的相同前綴組成的字段過濾掉大部分記錄，得到一個較少的數(shù)據(jù)掃描范圍，然后通過值過濾器即可得到最終的查詢結(jié)果，這個過程幾乎可以不用行鍵過濾器。

圖3 STG時空索引結(jié)構(gòu)

這種索引結(jié)構(gòu)解決了TG索引結(jié)構(gòu)在基于時間范圍的時空查詢時行鍵大部分失效的問題，在查詢時間范圍為一天以內(nèi)的區(qū)域，時空查詢有著良好的性能表現(xiàn)，但是在超過一天之后，Geohash編碼會失去索引效果。對于交通數(shù)據(jù)而言，基于時間范圍的區(qū)域查詢，大多情況下時間范圍很少超過一天。對于查詢時間范圍超過了一天的特例，本文的數(shù)據(jù)查詢算法(詳情見2.2.2節(jié))會將時間范圍按天進(jìn)行劃分，最終得到若干時間范圍都在一天內(nèi)的子查詢后再進(jìn)行查詢，這樣保證了行鍵中整個年月日+Geohash部分都會起到索引效果，總體不會明顯降低行鍵索引效果。整體而言，基于STG索引結(jié)構(gòu)的時空查詢性能明顯優(yōu)于TG索引結(jié)構(gòu)。

相對GT索引結(jié)構(gòu)，STG索引結(jié)構(gòu)的優(yōu)勢也是明顯的。在實(shí)際應(yīng)用中，HBase數(shù)據(jù)庫中一般會存長達(dá)數(shù)年的交通車輛動態(tài)數(shù)據(jù)，即對于同一個地點(diǎn)可能會存有近千萬條記錄，SGT在檢索數(shù)據(jù)時，通過年月日+Geohash可以更大地減少需要掃描的數(shù)據(jù)范圍，相對于GT索引結(jié)構(gòu)掃描的數(shù)據(jù)會少很多，查詢速度自然快了不少。

2.1.4 SGT時空索引

可以看到，STG算法實(shí)際是將時間維度進(jìn)行分解后再與空間維度組合，相應(yīng)地，空間維度分解后與時間維度組合也是一種索引方案，本文稱為SGT(Special Geo Time index)時空索引，其結(jié)構(gòu)如圖4所示。它將Geohash碼分割成前綴和偏移量兩部分，中間放入時間，即 Geohash前綴+時間+Geohash偏移量的結(jié)構(gòu)。

圖4 SGT時空索引結(jié)構(gòu)

這種索引結(jié)構(gòu)在查詢區(qū)域范圍較小的情形下，往往效果較好，這是因為如果具有相同的Geohash前綴的話，時間這個維度也被用來進(jìn)行索引過濾，從而克服了GT算法的不足。但是在查詢區(qū)域較大的情形下，會出現(xiàn)大量的冗余候選結(jié)果，效果會比較差。更為重要的是，Geohash前綴位數(shù)的設(shè)置會直接影響索引效果，而交通數(shù)據(jù)查詢查詢半徑和查詢時間范圍都是變化的，這導(dǎo)致難以找到一個較優(yōu)的設(shè)置參數(shù)。STG方法則不存在該問題。

相比較而言，STG索引結(jié)構(gòu)最適合應(yīng)用在海量交通數(shù)據(jù)時空查詢場景。下面重點(diǎn)介紹基于STG索引結(jié)構(gòu)的相關(guān)算法，GT、TG和SGT的相應(yīng)算法也是類似的。

2.2.1 時空查詢框架

基于時空索引的時空查詢框架如圖5所示，由客戶端、查詢區(qū)域處理模塊、索引層、數(shù)據(jù)庫和過濾模塊五個部分組成?？蛻舳酥饕?fù)責(zé)發(fā)出查詢請求；查詢區(qū)域處理模塊主要負(fù)責(zé)將客戶端選擇的查詢區(qū)域和查詢時間進(jìn)行時空處理，得到與HBase 行鍵格式對應(yīng)的字符串；索引層是查詢關(guān)鍵，主要通過行鍵匹配，從數(shù)據(jù)庫中檢索出初始結(jié)果集；數(shù)據(jù)庫主要負(fù)責(zé)數(shù)據(jù)存儲；過濾模塊則通過將行鍵掃描到的初始結(jié)果集進(jìn)行行鍵和值過濾，得到最終結(jié)果集，并返回給客戶端。

圖5 數(shù)據(jù)查詢示意圖

2.2.2 算法描述

STG索引策略用到了索引構(gòu)建和數(shù)據(jù)查詢兩種算法，其中索引構(gòu)建算法如算法1所示，數(shù)據(jù)查詢算法按照區(qū)域的不同分為圓區(qū)域查詢和矩形區(qū)域查詢算法，如算法2和算法3所示。

算法1 索引構(gòu)建算法。

輸入 車輛全球定位系統(tǒng)(Global Positioning System, GPS)數(shù)據(jù)。

輸出 一維字符串。

步驟1 獲取車輛GPS數(shù)據(jù)的經(jīng)度、緯度和時間；

步驟2 將經(jīng)緯轉(zhuǎn)為Geohash編碼(G)；

步驟3 將時間切分為年月日(yyMMdd)和時分秒(hhmmss)兩部分；

步驟4 將yyMMdd、G和hhmmss組合成一個字符串str；

步驟5 返回步驟4得到字符串str。

該算法將車輛GPS數(shù)據(jù)的經(jīng)緯度和時間三個維度的數(shù)據(jù)組合成了一個一維的字符串，使之符合HBaseRowkey的需求，進(jìn)而實(shí)現(xiàn)HBase時空索引。

算法2 圓區(qū)域查詢算法。

輸入 查詢點(diǎn)的經(jīng)緯度(lat,lon)、查詢半徑d和查詢時間范圍t0～t1。

輸出 符合查詢條件的結(jié)果集A。

步驟1 通過查詢點(diǎn)的經(jīng)緯度(lat,lon)和查詢半徑d,求出查詢區(qū)域的右上頂點(diǎn)(lat1,lon1)和左下頂點(diǎn)(lat2,lon2)；

步驟2 調(diào)用算法3，并將算法3的返回值賦給A′；

步驟3 通過查詢半徑d對A′進(jìn)行過濾，得到最終結(jié)果集A；

步驟4 返回最終結(jié)果集A。

算法3 矩形區(qū)域查詢算法。

輸入 查詢區(qū)域的右上頂點(diǎn)(lat1,lon1)、左下頂點(diǎn)(lat2,lon2)和查詢時間范圍t0～t1。

輸出 符合查詢條件的結(jié)果集A。

步驟1 將兩個頂點(diǎn)的經(jīng)緯度轉(zhuǎn)為Geohash編碼G1、G2。

步驟2 判斷查詢時間范圍t0～t1是否在一天之內(nèi)：

if查詢時間范圍在一天之內(nèi)then調(diào)用算法4； 將算法4的返回結(jié)果集添加到集合A中；

elsethen將查詢時間范圍按日進(jìn)行分割，得到一個子查詢時間范圍的List集合tlist； 對tlist中的每一個元素都進(jìn)行一次算法4的調(diào)用，并獲得返回值； 將每一次算法4的返回結(jié)果集添加到集合A中；

end if；

步驟3 返回最終結(jié)果集A。

算法4 查詢子算法。

輸入G1、G2、查詢半徑d和查詢時間范圍ti0～ti1。

輸出 符合查詢條件的結(jié)果集A。

步驟1 將查詢時間范圍的年月日部分切分出來得到y(tǒng)yMMdd(起止時間的yyMMdd是相同的，只需一個即可)；

步驟2 將yyMMdd分別與G1、G2組合得到查詢的起止行鍵:r1、r2；

步驟3 掃描HBase中Rowkey在r1和r2之間的數(shù)據(jù)得到初始結(jié)果集B；

步驟4 通過HBase過濾器對B進(jìn)行值過濾，得到結(jié)果集A；

步驟5 返回結(jié)果集A。

數(shù)據(jù)查詢算法通過掃描HBase中與查詢區(qū)域得到的字符串具有相同yyMMdd+Geohash前綴的行鍵來實(shí)現(xiàn)快速定位數(shù)據(jù)，可以減少大量的冗余數(shù)據(jù)掃描，提升了數(shù)據(jù)查詢速度。

3 實(shí)驗結(jié)果及分析

3.1 實(shí)驗環(huán)境

本文實(shí)驗的HBase集群環(huán)境如下：

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

2)硬件環(huán)境：雙CPU，四核處理器，32GB內(nèi)存，10TB硬盤的PC兩臺；雙CPU，四核處理器，8GB內(nèi)存，10TB硬盤的PC三臺。

3.2 實(shí)驗數(shù)據(jù)

本文實(shí)驗的交通數(shù)據(jù)是車輛GPS數(shù)據(jù)，來源于某市智能交通系統(tǒng)的真實(shí)歷史數(shù)據(jù)，共有三種數(shù)據(jù)集，分別為500萬級、2 500萬級和7 500萬級，其中：500萬級為2012年10月03日一天的數(shù)據(jù)，2 500萬級是2012年10月03日—2012年10月07日的數(shù)據(jù)，7 500萬級是2012年10月03日—2012年10月17日的數(shù)據(jù)，其數(shù)據(jù)模型如表1所示。各種索引結(jié)構(gòu)下數(shù)據(jù)在HBase中的存儲模型如表2所示：Rowkey中的時間年代前兩位是去掉的，這樣可以在不影響時間精度的前提下縮短Rowkey的長度，精確到秒是為了使得每一條記錄都單獨(dú)存一行，采用9位的Geohash編碼，可以精確到4.8m×4.8m的空間區(qū)域；A是HBase的列族名；Others指的是其他不重要的數(shù)據(jù)列。SGT算法中Geohash取四位前綴。

表1 原始數(shù)據(jù)模型

表2 不同索引類型的數(shù)據(jù)在HBase中的存儲結(jié)構(gòu)

本文實(shí)驗的主要目的是測試在不同查詢半徑(查詢區(qū)域)、不同查詢時間范圍、不同數(shù)量級情況下，GT、TG、SGT和STG四種時空索引的性能。

3.3 實(shí)驗結(jié)果及分析

下面分別按基于時間點(diǎn)的區(qū)域查詢和基于時間范圍的區(qū)域查詢進(jìn)行實(shí)驗：

實(shí)驗1 基于時間點(diǎn)的區(qū)域查詢。

隨機(jī)設(shè)定某時間點(diǎn)(2012- 10- 03T00:12:52)，查詢區(qū)域中心點(diǎn)為東經(jīng)116.534 456 7，北緯39.567 421 3?？紤]查詢半徑與候選數(shù)據(jù)集規(guī)模對查詢性能的影響。

1)在7 500萬數(shù)量級的數(shù)據(jù)下，分別對四種時空索引方案進(jìn)行不同查詢半徑的區(qū)域查詢實(shí)驗，實(shí)驗結(jié)果如圖6所示。從圖中可以看，TG索引結(jié)構(gòu)在基于時間點(diǎn)的區(qū)域查詢上性能最優(yōu)，SGT和STG索引次之，GT索引最差。從圖中還可以看出查詢范圍的變化對GT、SGT索引結(jié)構(gòu)的性能影響最大，對TG索引結(jié)構(gòu)性能影響最小，對STG索引結(jié)構(gòu)的性能影響比TG索引結(jié)構(gòu)略大一點(diǎn)，但是影響幅度不大。

2)在查詢半徑為1 000m的前提下，分別對四種時空索引方案在不同數(shù)據(jù)量級的數(shù)據(jù)下進(jìn)行查詢實(shí)驗，實(shí)驗結(jié)果如圖7所示。從圖中可看出，在基于時間點(diǎn)的區(qū)域查詢時，STG和TG兩種索引結(jié)構(gòu)在不同數(shù)據(jù)量級情況下性能幾乎不變，即數(shù)量級對它們基于時間點(diǎn)的區(qū)域查詢性能影響不明顯，而對于SGT和GT索引結(jié)構(gòu)影響較大。

圖6 不同查詢半徑的時間點(diǎn)區(qū)域查詢

圖7 不同數(shù)據(jù)量級別的時間點(diǎn)區(qū)域查詢

實(shí)驗2 基于時間范圍的區(qū)域查詢。

隨機(jī)設(shè)定查詢區(qū)域中心點(diǎn)為東經(jīng)116.534 456 7、北緯39.567 421 3，查詢半徑為1 000m?？紤]查詢時間范圍與候選數(shù)據(jù)集規(guī)模對查詢性能的影響。

1)在7 500萬數(shù)量級的數(shù)據(jù)下，分別對四種時空索引方案進(jìn)行不同時間范圍內(nèi)的區(qū)域查詢實(shí)驗，實(shí)驗結(jié)果如圖8所示，圖中橫坐標(biāo)為待查詢的時間范圍(單位：h)，縱坐標(biāo)為查詢耗時(單位:s)。從圖中可以看出，在基于時間范圍的時空區(qū)域查詢性能上，STG索引優(yōu)于GT索引，GT索引優(yōu)于TG索引，SGT與GT性能相當(dāng)。STG、SGT和GT這三種索引在基于時間范圍的區(qū)域查詢上的性能隨著時間范圍的增大變化不大，而TG索引結(jié)構(gòu)對時間范圍的變化非常敏感。

圖8 不同時間范圍的區(qū)域查詢

2)在查詢時間范圍為(2012- 10- 03T00:12:52，2012- 10- 03T01:12:52)的前提下，分別在不同數(shù)量級的數(shù)據(jù)下對四種時空索引方案進(jìn)行區(qū)域查詢實(shí)驗，實(shí)驗結(jié)果如圖9所示。從圖中可以看出，數(shù)量級對STG和TG這兩種索引在基于時間范圍的區(qū)域查詢上的性能影響不大，而對于GT和SGT索引影響明顯。

圖9 不同數(shù)據(jù)量級別的時間范圍區(qū)域查詢

綜合實(shí)驗結(jié)果分析可知，在上述四種索引中，本文提出的TG時空索引結(jié)構(gòu)在基于時間點(diǎn)的交通數(shù)據(jù)區(qū)域查詢上性能最優(yōu)，STG時空索引結(jié)構(gòu)在基于時間范圍的交通數(shù)據(jù)區(qū)域查詢上性能最優(yōu)。雖然在基于時間點(diǎn)的區(qū)域查詢上STG的性能稍遜于TG的性能，但是在基于時間范圍的區(qū)域查詢上SGT的性能優(yōu)勢明顯，在同時有基于時間點(diǎn)和基于時間范圍的時空區(qū)域查詢需求下，STG時空索引方法應(yīng)該是一個最佳的索引選擇。此外，實(shí)驗表明，基于STG時空索引，數(shù)據(jù)量級對于時空區(qū)域查詢的性能影響不大，該特性非常適合在擁有海量數(shù)據(jù)的智能交通領(lǐng)域中應(yīng)用。

4 結(jié)語

針對基于HBase管理海量交通數(shù)據(jù)時面臨時空查詢性能低下的問題，本文結(jié)合HBase行鍵的特點(diǎn)，基于空間維度和時間維度的組合與分解機(jī)制，提出了無侵入的HBase時空索引方案，詳細(xì)介紹了索引結(jié)構(gòu)，并分析了不同時空索引方法的實(shí)用場景，提出了基于上述索引方案的交通數(shù)據(jù)查詢算法。實(shí)驗結(jié)果表明沒有任何一種方案在所有場景都能達(dá)到最優(yōu)效果，但綜合考慮，STG方案在大多數(shù)情況下能夠具有比較明顯的查詢性能。下一步的工作主要包括兩個方面：首先是測試與樹形索引結(jié)構(gòu)的性能對比；其次是尋找一種動態(tài)優(yōu)選最佳索引的方法，即針對不同的查詢條件，根據(jù)不同的優(yōu)選策略，動態(tài)挑選出最佳的索引方案進(jìn)行查詢。

)

[1] 申德榮,于戈,王習(xí)特,等.支持大數(shù)據(jù)管理的NoSQL系統(tǒng)研究綜述[J].軟件學(xué)報,2013，24(8):1786-1803.(SHENDR,YUG,WANGXT,etal.SurveyonNoSQLformanagementforbigdata[J].JournalofSoftware, 2013, 24(8): 1786-1803.)

[2]GONGJ,KES,ZHUQ,etal.AnefficienttrajectorydataindexinegratingR-tree,HashandB*-tree[J].ActaGeodaetcaetCartographicaSinica, 2015, 44(5): 570-577.

[3]KOTHURIRKV,RAVADAS,ABUGOVD.QuadtreeandR-treeindexesinoraclespatial:acomparisonusingGISdata[C]//SIGMOD’02:Proceedingsofthe2002ACMSIGMODInternationalConferenceonManagementofData.NewYork:ACM, 2002: 546-557.

[4] 葉小平,郭歡,湯庸,等.基于相點(diǎn)分析的移動數(shù)據(jù)索引技術(shù)[J].計算機(jī)學(xué)報,2011,34(2):256-274.(YEXP,GUOH,TANGY,etal.Indexofmobiledatabasedonphrasepointsanalysis[J].ChineseJournalofComputers, 2011, 34(2): 256-274.)

[5] 尹章才,李霖,王錚.基于HR-樹擴(kuò)展的時空索引機(jī)制研究[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2007,32(12):1131-1134.(YINZC,LIL,WANGZ.Spatio-temporalindexbasedonextendedHR-tree[J].GeomaticsandInformationScienceofWunanUniversity, 2007, 32(12): 1131-1134.)

[6]Wikipedia.Geohash[EB/OL].[2016- 06- 29].https://en.wikipedia.org/wiki/Geohash.

[7]hindex[EB/OL].[2016- 06- 29].https://github.com/Huawei-hadoop/hindex.

[8] 趙健博.奇虎360HBASE二級索引的設(shè)計與實(shí)踐[EB/OL].[2016- 06- 29].http://www.infoq.com/cn/presentations/qihoo360-hbase-two-stage-index-design-and-practice.(ZHAOJB.Thedesignandimplementationof360’ssecondaryindexofHBASE.[EB/OL].[2016- 06- 29].http://www.infoq.com/cn/presentations/qihoo360-hbase-two-stage-index-design-and-practice).

[9]SHEND,FANGJ,HANY.Anearbyvehiclesearchalgorithmbasedonhbasespatialindex[C]//WISA2015:Proceedingsofthe12thWebInformationSystemandApplicationConference.Piscataway,NJ:IEEE, 2015: 71-74.

[10]NISHIMURAS,DASS,AGRAWALD,etal.MD-HBase:designandimplementationofanelasticdatainfrastructureforcloud-scalelocationservices[J].DistributedandParallelDatabases, 2012, 31(2): 289-319.

[11]MAY,RAOJ,HUW,etal.AnefficientindexformassiveIOTdataincloudenvironment[C]//CIKM’12:Proceedingsofthe21stACMInternationalConferenceonInformationandKnowledgeManagement.NewYork:ACM, 2012: 2129-2133.

[12]FOXA,EICHELBERGERC,HUGHESJ,etal.Spatio-temporalindexinginnon-relationaldistributeddatabases[C]//Proceedingsofthe2013IEEEInternationalConferenceonBigData.Washington,DC:IEEEComputerSociety, 2013: 291-299.

ThisworkispartiallysupportedbytheBeijingMunicipalNaturalScienceFoundation(4131001, 4142023).

FANG Jun, born in 1976, Ph.D., associate research fellow.His research interests include cloud data management, massive spatio-temporal data management.

LI Dong, born in 1989, M.S.candidate.His research interests include cloud data management.

GUO Huiyun, born in 1992, M.S.candidate.Her research interests include distributed system scheduling.

WANG Jiayi, born in 1993, M.S.candidate.Her research interests include massive spatio-temporal data management.

Spatio-temporal index for massive traffic data based on HBase

FANG Jun*, LI Dong, GUO Huiyun, WANG Jiayi

(BeijingKeyLaboratoryonIntegrationandAnalysisofLarge-scaleStreamData,NorthChinaUniversityofTechnology,Beijing100041,China)

Focusing on the issue that the HBase storage without spatio-temporal index degrades the traffic data query performance, some HBase spatio-temporal indexes based on row keys were proposed for massive traffic data.Firstly, the dimensionality reduction method based on Geohash was used to convert two-dimensional spatial position data into a one-dimensional code.Then the code was combined with the temporal dimension.Secondly, four index models were put forward based on combination order, and the structures of the models and their adaption conditions for traffic data query were discussed.Finally, the algorithm of index creation as well as traffic data query algorithm was proposed.Experimental results show that the proposed HBase spatio-temporal index structure can effectively enhance the traffic data query performance.In addition, the query performance of four different spatio-temporal index structures in different data size, different query radius and different query time range were compared, which verified the different adaption scenes of different index structures in traffic data query.

massive traffic data; HBase; Geohash; spatio-temporal index; range query

2016- 08- 12;

2016- 09- 06。 基金項目:北京市自然科學(xué)基金資助項目(4131001, 4142023)。

房俊(1976—),男,江蘇南京人,副研究員,博士,主要研究方向:云數(shù)據(jù)管理、海量時空數(shù)據(jù)管理; 李冬(1989—),男,湖南永州人,碩士研究生,主要研究方向:云數(shù)據(jù)管理; 郭會云(1992—),女,河南漯河人,碩士研究生,主要研究方向:分布式系統(tǒng)調(diào)度; 王嘉怡(1993—),女,北京人,碩士研究生,主要研究方向:海量時空數(shù)據(jù)管理。

1001- 9081(2017)02- 0311- 05

10.11772/j.issn.1001- 9081.2017.02.0311

TP311.133.1

A