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

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

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

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

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

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

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

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

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

0 引言

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

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

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

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

1 相關工作

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

1.1 二級索引

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

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

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

1.2 空間索引

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

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

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

1.3 時空索引

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

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

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

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

2.1 索引結構

2.1.1 GT時空索引

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

圖1 GT時空索引結構

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

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

2.1.2 TG時空索引

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

圖2 TG時空索引結構

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

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

2.1.3 STG時空索引

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

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

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

圖3 STG時空索引結構

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

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

2.1.4 SGT時空索引

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

圖4 SGT時空索引結構

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

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

2.2.1 時空查詢框架

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

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

2.2.2 算法描述

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

算法1 索引構建算法。

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

輸出 一維字符串。

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

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

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

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

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

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

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

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

輸出 符合查詢條件的結果集A。

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

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

步驟3 通過查詢半徑d對A′進行過濾，得到最終結果集A；

步驟4 返回最終結果集A。

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

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

輸出 符合查詢條件的結果集A。

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

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

if查詢時間范圍在一天之內then調用算法4； 將算法4的返回結果集添加到集合A中；

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

end if；

步驟3 返回最終結果集A。

算法4 查詢子算法。

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

輸出 符合查詢條件的結果集A。

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

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

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

步驟4 通過HBase過濾器對B進行值過濾，得到結果集A；

步驟5 返回結果集A。

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

3 實驗結果及分析

3.1 實驗環(huán)境

本文實驗的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內存，10TB硬盤的PC兩臺；雙CPU，四核處理器，8GB內存，10TB硬盤的PC三臺。

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

本文實驗的交通數(shù)據(jù)是車輛GPS數(shù)據(jù)，來源于某市智能交通系統(tǒng)的真實歷史數(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所示。各種索引結構下數(shù)據(jù)在HBase中的存儲模型如表2所示：Rowkey中的時間年代前兩位是去掉的，這樣可以在不影響時間精度的前提下縮短Rowkey的長度，精確到秒是為了使得每一條記錄都單獨存一行，采用9位的Geohash編碼，可以精確到4.8m×4.8m的空間區(qū)域；A是HBase的列族名；Others指的是其他不重要的數(shù)據(jù)列。SGT算法中Geohash取四位前綴。

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

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

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

3.3 實驗結果及分析

下面分別按基于時間點的區(qū)域查詢和基于時間范圍的區(qū)域查詢進行實驗：

實驗1 基于時間點的區(qū)域查詢。

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

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

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

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

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

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

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

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

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

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

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

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

4 結語

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

)

[1] 申德榮,于戈,王習特,等.支持大數(shù)據(jù)管理的NoSQL系統(tǒng)研究綜述[J].軟件學報,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] 葉小平,郭歡,湯庸,等.基于相點分析的移動數(shù)據(jù)索引技術[J].計算機學報,2011,34(2):256-274.(YEXP,GUOH,TANGY,etal.Indexofmobiledatabasedonphrasepointsanalysis[J].ChineseJournalofComputers, 2011, 34(2): 256-274.)

[5] 尹章才,李霖,王錚.基于HR-樹擴展的時空索引機制研究[J].武漢大學學報(信息科學版),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二級索引的設計與實踐[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。 基金項目:北京市自然科學基金資助項目(4131001, 4142023)。

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

1001- 9081(2017)02- 0311- 05

10.11772/j.issn.1001- 9081.2017.02.0311

TP311.133.1

A