李征宇，趙卓峰

（1.北方工業(yè)大學信息學院，北京 100144；2.大規(guī)模流數據集成與分析技術北京市重點實驗室（北方工業(yè)大學）,北京 100144）

隨著定位技術的廣泛應用，軌跡數據成為近年來一類典型的大數據。軌跡數據涵蓋的領域非常廣泛，其中包括人類出行軌跡、自然現象移動軌跡和動物遷徙軌跡等［1］。海量高質的軌跡數據中蘊含著豐富的信息，通過對其進行深入的分析與研究，可以掌握人類活動和遷移的規(guī)律，分析交通、大氣環(huán)境的移動特征［2］，其結果可以應用到城市規(guī)劃［3］、路線推薦［4］和城市熱點區(qū)域發(fā)掘［5］等方面，推動其他各個領域的發(fā)展。以Hadoop 為代表的大數據技術被用來支持軌跡數據的存儲和查詢，然而直接使用Hadoop 等大數據技術將軌跡數據存儲于分布式集群中，只解決了海量軌跡數據的存儲問題，并不能滿足對海量軌跡數據的高效查詢需求。例如：只是簡單將數據存儲在分布式文件系統上，或是不做任何處理地將數據存儲于NOSQL 數據庫中，做局部的查詢與分析工作就意味著對整體存儲做一次全掃描，耗時長、資源占用率高等問題就會凸顯，從而導致整個任務流程效率低下。 因此，基于分布式存儲系統與NOSQL 數據庫，建立高效的索引結構與查詢策略來提高存儲和查詢效率，是當前存儲與查詢軌跡數據的主流方法。傳統小規(guī)模軌跡數據的索引策略主要分為基于R-Tree 方法與基于網格方法［2］?；赗-Tree 的方法隨著存儲軌跡數據時間跨度的增長與數據量的增加，不同的3D 框之間重疊變得頻繁，導致查詢效率下降，不適合在分布式大數據環(huán)境下進行海量軌跡數據的存儲和查詢；基于網格的方法是將空間劃分成均勻的網格并加上時間維，查詢時將查詢任務轉換成覆蓋不同網格的子查詢。它將所有的網格等價看待，沒有充分考慮時空軌跡數據在時空間分布上不均勻的特點。本文設計并實現了一種基于歷史數據預分區(qū)的軌跡數據索引結構，用于加速海量不均勻軌跡數據的軌跡查詢，在非關系型數據庫HBase 中設計了存儲模型并設計了基于此索引的查詢優(yōu)化算法。索引結構利用Geohash 編碼，借助了編碼的空間鄰近性，首先在歷史數據集上隨機抽取軌跡數據用于構建不均勻的分區(qū)，根據Geohash 數量分布情況對Geohash 編碼進行合并，并生成Geohash 的倒排索引，使得Geohash 編碼與分區(qū)一一對應。在此基礎上，本文設計了基于HBase 的軌跡存儲模型以及軌跡數據查詢算法——首先在倒排索引中檢索查詢范圍覆蓋的分區(qū)情況，再依次遍歷分區(qū)，在分區(qū)內完成子查詢的分割操作，最終完成時空軌跡數據的查詢任務。

1 相關工作

現有的軌跡數據索引按構造方法也可分為兩類：數據驅動方法與空間驅動方法［6］。

數據驅動方法主要是圍繞以數據為中心，隨著數據導入的過程動態(tài)的生成索引結構。普遍是基于R 樹方法的變體或拓展，例如基于軌跡建立的3D-Rtree 方法［7］，通過構建時空R 樹的方法建立索引，將查詢問題轉化為三維查詢立方體，但是這種方法隨著數據量的增加，查詢效率急劇下降。盡管后來提出的ST-R-tree 和TB-tree［8］方法提出了解決此問題的新思路，但是隨著存儲軌跡數據時間的增加，索引框之間重疊的問題依然存在。文獻［9］提出的Rt-Tree 索引方式和文獻［10］提出的HRTree 和H+R-Tree 索引方法使用的都是多版本R樹方法。對于給定的時空查詢，這類索引首先判斷查詢窗口覆蓋哪些時間段，然后從這些時間段對應的每個空間索引中檢索查詢范圍相交的軌跡點?；赗 樹構建的索引結構相對復雜，R 樹的插入與節(jié)點分裂代價相對較大，需要動態(tài)地調整索引結構。

另一類空間驅動方法的思路是先將地理空間分為網格的形式，然后將落入每個網格的內容再依時間進行索引，達到同時索引時間維和空間維的目的。編碼方式主要以常規(guī)網格編碼的方式實現，按行、按列將空間有序地劃分。隨著空間填充曲線領域的發(fā)展，2 種可以保持空間鄰近性的空間填充方法應用比較廣泛，即Z 曲線［11］與Hilbert 曲線［12］。Hughes 等介紹了一種時空數據存儲與檢索引擎Geomesa［13］，其索引部分就是利用Z 曲線進行Base32 編碼得到的Geohash 實現，可以用于索引時空軌跡數據。JUST［14］是京東城市時空數據引擎，該引擎在Geomesa 的基礎上提出了Trajmesa［15］存儲引擎，拓展了Z2T 和XZ2T 兩種索引方式，解決時間與空間維度不匹配的問題。ST-Hash 索引方法［16］將經度、緯度、時間3 種屬性進行統一編碼，使地理位置鄰近、時間相近的數據，物理存儲的位置相近。相比較于Z 曲線，Hilbert 曲線映射步驟較多相對復雜，但數據的空間聚集性比Z 曲線更優(yōu)。文獻［17-18］使用Hilbert 曲線對空間進行編碼，同時再加入時間屬性構造索引。

數據驅動與空間驅動索引方法是從索引的形式上考慮的，面對海量軌跡數據的存儲與查詢需求，數據驅動的索引方法通常并不高效［19-20］。由于軌跡數據通常與路網、城市熱點區(qū)域以及由此帶來的移動對象出行特征密切相關，所以海量的軌跡數據通常聚集在城市熱點區(qū)域以及路網范圍內，但是空間驅動索引方法是將空間中的所有區(qū)域進行等分，這就造成了有的空間區(qū)域中數據量龐大，有的空間區(qū)域中數據量較少甚至沒有數據，使得有的子查詢需要耗時較長，有的子查詢中并沒有數據。

針對這種軌跡數據的分布不均勻問題，現有解決方法主要依靠數據的動態(tài)劃分進行解決。文獻［21］中提出了1 種基于ST-hash 的LPSTHash 的索引方案，設置了Regin 分裂的策略，當Region 中數據量達到了Region 分裂閾值，使Region 以某一個鍵值作為分界線分裂，同時，Region對應的索引樹也應該和Region 一樣一分為二。文獻［22］中，基于Geohash 和R 樹，提出了1 種2層時空索引-GRIST，通過改進原有的Geohash 的編碼及映射算法，設計了根據數據分布自適應分裂的方法，利用R-tree 存儲不均勻的Geohash 網格上的數據。動態(tài)劃分法雖然可以有效地解決數據分布不均勻的問題，但是由于數據分區(qū)是隨著數據導入時動態(tài)生成的，分區(qū)過程會花費較長時間，同時已經生成的索引結構也要動態(tài)的更改；可能會存在數據存儲完成但數據依然分布不均勻的問題。本文的方法利用了歷史數據得到軌跡數據的時空分布規(guī)律，再利用規(guī)律構建分區(qū)的方法，解決不均勻軌跡數據的存儲與查詢問題。

2 基于歷史數據預分區(qū)的索引方法

軌跡數據Traj 由一系列軌跡點構成，可以表示為集合Tra=｛P1，P2，…，Pn｝，軌跡點Pi=（loni，lati，ti），0≤i≤n，其中經度用lon 表示，緯度用lat 表示，t表示此坐標位置的時間。Traj 可以表示在三維坐標系中，其中兩維表示為地理空間-經度與緯度，第三維用于表示時間。

本文索引的生成利用了Geohash 編碼。Geohash 是一種用于處理空間數據的高效的索引方法，通過對地理信息的編碼，將二維的經緯度降維成一維字符串，Geohash 編碼代表的并不是1 個點，而是1 個矩形區(qū)域。對其加入時間維可以用于索引時空軌跡數據，在使用劃分得均勻的立方體存儲數據時，查詢問題可轉化為對查詢立方體所覆蓋的Geohash 立方體進行遍歷，產生大量的子查詢任務。如圖1 所示，對于不均勻的數據分布，這些查詢任務可能相差懸殊（每個Geohash 立方體中的數據可能相差懸殊）；對于查詢范圍遠大于單位立方體的查詢需求時，查詢會轉換成為大量的子查詢，影響查詢性能。

圖1 Geohash 立方體查詢示例Fig.1 Example of Geohash cube query

區(qū)別于只利用Geohash 編碼構建的時空數據索引方法，本文索引方法的核心是利用歷史軌跡數據提前得到軌跡數據的分布規(guī)律，在索引構建的過程利用此規(guī)律，將Geohash 編碼分區(qū)按歷史數據分布進行合并，即通過閾值的方法對其進行合并，這樣在查詢時本文方法的子查詢數量將會小于只利用Geohash 編碼的索引方法，并在查詢時對分區(qū)子查詢進行分割，避免擴大查詢區(qū)域。通過這2 種方式，有效地減少子查詢個數，提升查詢效率，并適當的平衡了任務規(guī)模。本文索引的構建過程如圖2所示。

圖2 索引構建過程Fig.2 Process of building index

2.1 基于歷史數據的分區(qū)生成

索引設計的首要步驟是利用歷史數據對Geohash 編碼進行分區(qū)，所以歷史數據的數據分布情況對索引的設計至關重要。圖3 中分別給出了北京市出租車軌跡數據集中10 月8 日與10 月9 日兩日的數據分布情況，通過觀察發(fā)現，兩日的數據分布情況基本相似，即軌跡數據總體分布總是在路網附近，由此可以利用數據在空間上的分布特征，構建基于歷史數據的分區(qū)，使其服務于時空軌跡數據的存儲與檢索。

圖3 從宏觀的角度展示出在不同日期上的數據空間分布情況。若要利用歷史軌跡數據提煉出信息，還需要判斷不同日期的Geohash 上所包含的數據量是否相似，圖4 給出了不同日期Geohash 上軌跡點數據量的部分數據，其中（Geohash）D是將Geohash 編碼轉換成十進制，Num 表示的是每日在Geohash 上數據的量，圖4 中繪制了10 月8 日～10月12 日的部分數據情況，其中Avg 是這幾日數據的平均值，可以觀察到這5 天的每個Geohash 中的數據量波動不大，屬于同一數量級，所以使用了Geohash 的平均值表示每個Geohash 網格的數據特征。

圖3 兩日數據分布對比Fig.3 Comparison of two-day data distribution

圖4 5 天Geohash 數據分布與均值Fig.4 Five-day Geohash distribution and Avg

利用設置分區(qū)合并閾值的方法完成分區(qū)的合并，即合并后所生成的Geohash 組，其所包含的數據和應大于設置的閾值。合并順序按照Geohash生成順序，如果有的網格中沒有數據，則跳過這一網格；如果將當前Geohash 網格中的數據加入后，分區(qū)中的總數據量大于所設定的閾值，即分區(qū)結束，下一條數據開始新的分區(qū)，圖5 舉例展示了分區(qū)的劃分情況，其中01、02、03、04 為4 個分區(qū)，每個分區(qū)中包含一個或多個Geohash 區(qū)域。

圖5 分區(qū)劃分示例Fig.5 Example of dividing partition

表1 中給出了分區(qū)劃分結果示例，表結構體現出了分區(qū)號與Geohash 組的映射關系，1 個分區(qū)中包含1 個或多個同一編碼長度的Geohash 編碼，每個Geohash 編碼都對應1 個分區(qū)號。分區(qū)閾值設定為5 000，其中Partition Id 代表的是分區(qū)的自增序號，Partition Number 表示的是分區(qū)內的數據量，Included Geohash 表示的是分區(qū)內包含的Geohash編碼。

表1 分區(qū)劃分的結果示例Table 1 Result of dividing partition

2.2 輔助二級索引

索引結構的主要設計思想體現在通過設置閾值，對Geohash 進行分區(qū)，將包含數據量少的Geohash 分區(qū)進行合并，從而減少查詢生成的子查詢數量。對于給定的經緯度坐標P=（lon，lat），通過Geohash 算法可以很容易地得到Geohash 編碼，但由于Partition Id 與Geohash 編碼可能是一對一關系，也可能是一對多的關系，所以根據如表1 所示的數據結構，不能直接根據Geohash 編碼得到Partition Id，所以需要1 個Geohash 與Partition Id 對應的倒排索引作為二級索引，來服務于數據的存儲與查詢。

二級索引的構建如表2 結構所示。利用Geohash 編碼與分區(qū)號進行對應，通過Geohash 編碼值可以直接獲取分區(qū)號，在數據存儲時，可以通過二級索引快速地查詢到Geohash 編碼所對應的分區(qū)號；同理，在查詢時，通過查詢范圍的解析得到查詢范圍所覆蓋的Geohash 的編碼，再通過二級索引可以檢索到這些Geohash 編碼屬于哪個分區(qū)。

表2 二級索引結構Table2 Secondary index structure

3 基于HBase 的軌跡數據索引存儲模型

與許多軌跡管理系統類似，如文獻［15］中提出的垂直存儲模式，本文方法也是利用數據庫中1 行存取1 個軌跡點數據，每1 個軌跡點數據包括如下幾個屬性。

（1）分區(qū)號：利用空間屬性與軌跡數據分布生成的自增序號。

（2）空間屬性：包括本軌跡點的經度、緯度。

（3）時間屬性：軌跡點的產生時間。

（4）其他屬性：移動對象速度等其他描述軌跡點的信息。

數據存儲模型的設計對提升查詢效率有至關重要的作用，由于HBase 中不支持設置二級索引結構，HBase 中的行鍵即為數據表的直接索引，所以將軌跡數據索引直接設計為行鍵。HBase 的存儲模型如表3 所示，其中TR 表示時間尺度，本文處設計為1 天。T表示尺度內的具體時間。本文的設計既保證了屬于同一分區(qū)的Geohash 在物理位置上鄰近，也保證了分區(qū)內相鄰時間T的軌跡點在物理上也相對鄰近。

表3 數據存儲模型Table 3 Data storage model

圖6 描述了數據存入HBase 數據庫的具體流程，其中需要的參數包括在上文中構建的不均勻網格分區(qū)的二級索引Geohash Map，即Geohash 與Partition Id 組成的倒排索引，用于獲取當前軌跡點的Geohash 所在的分區(qū)；軌跡數據為需要入庫的原始數據，從中可以分離出當前軌跡點的詳細信息，如經度、緯度、時間和速度等；Geohash 編碼長度應與前文設置的Geohash 編碼長度保持一致，存儲的數據才能在查詢時與查詢任務相匹配。本文利用Hash Map 結構存儲二級索引，通過Key便可直接查找到對應的value 值，故本算法的時間復雜度為o(n)，在空間消耗方面主要受到Geohash 編碼長度影響，編碼長度越長，其所代表的空間區(qū)域就越小，在一定的空間范圍內，包含的編碼就會更多。

圖6 軌跡數據入庫流程Fig.6 Process of importing trajectory data into HBase

4 軌跡數據時空查詢

本文提出的索引方法主要服務于軌跡數據的時空查詢，定義時空查詢?yōu)镼st，給定空間范圍［Geostart，Geoend］，其中Geox=（lonx，latx）；給定時間范圍定義為［Tstart，Tend］，對于給定時空范圍條件，查詢出的符合條件的軌跡點的集合定義為Result，Result=Qst（Geostart，Geoend，Tstart，Tend），不同于對HGrid［6］拓展的索引方式，本文提出的索引方法在時空查詢時需要設計1 個額外的查詢算法來支持。由上文可知，此時已經獲得了不均勻軌跡數據的Geohash 分區(qū)信息，并根據分區(qū)信息將數據集中的軌跡數據依據要求存入了HBase 數據庫。分區(qū)的目的就是優(yōu)化查詢效率，擴展的HGrid 方法先是利用空間維進行查詢，查詢哪些Geohash 編碼被查詢條件覆蓋，再依次遍歷每1 個Geohash，利用時間維與精確的位置信息條件進行篩選。由于引入了分區(qū)的概念，本文方法使用查詢條件向分區(qū)進行映射，得到查詢范圍所對應的分區(qū)，再在分區(qū)內劃分查詢范圍具體覆蓋的區(qū)域，在數據分布不均勻時，生成的子查詢數量會少于前者。

如圖7 所示，01、02、03、04 為分區(qū)號，例如分區(qū)01=｛ws1070，ws1071，ws1072，ws1073，ws1074｝，QueryWindow1 和QueryWindow2 分別為查詢窗口。對于QueryWindow1 來說，QueryWindow1 覆蓋的Geohash 編碼同屬于01 分區(qū)，其中包括ws1070、ws1071 和ws1074，由于ws1070 和ws1071相鄰，所以QueryWindow1 可以生成2 個子查詢，即01［ws1070，ws1071］和01［ws1074］，相較于擴展的HGrid 方法，在總體查詢數據不變的情況下，子查詢個數由3 個減少為2 個；對于QueryWindow2，即整個區(qū)域都為查詢范圍，依據本文設計的查詢方法QueryWindow2 可生成4 個子查詢，為01［ws1070，ws1071，ws1072，ws1073，ws1074］、02［w s1075］、03［ws1076，ws1077，ws1078，ws1079］和04［ws107b，ws107c，ws107d，ws107e，ws107f，ws107g］，相較于擴展的HGrid 方法，在總掃描數據不變的情況下，子查詢個數由16 個減少為4 個，查詢效率可以得到顯著提升。圖8 給出了軌跡時空查詢的詳細分解與執(zhí)行過程，在時間復雜度方面，由于需要對每1 個partition 進行遍歷，同時每個partition 中還包含多個Geohash 編碼，查詢方法的時間復雜度為o(n2)，空間復雜度同數據入庫時相同，取決于Geohash 編碼長度。

圖7 查詢算法示意圖Fig.7 Example of query algorithm

圖8 軌跡數據時空查詢流程Fig.8 Spatio-temporal query process of trajectory data

5 實驗評價

為了測試本文提出的索引方法的查詢響應情況，基于NoSQL 的HBase 數據庫實現了數據持久化，借助HBase Java api 實現了數據的分布式查詢算法完成數據查詢。

5.1 實驗準備

實驗環(huán)境采用Hadoop 完全分布式集群環(huán)境，集群由3 個節(jié)點組成，其中1 個Master 節(jié)點部署NameNode，2 個Slave 節(jié)點部署DataNode，軟件環(huán)境：節(jié)點系統為centos7，集群環(huán)境安裝有Hadoop-2.7.1、HBase-1.3.6 和Zookeeper-3.4.14；硬件環(huán)境：每個節(jié)點擁有16 GB 內存、2 TB 硬盤和兩顆Intel E5-2620 0 @ 2.00 GHzCPU。

本文實驗的軌跡數據采用浮動車軌跡數據，來源于北京市2012 年10 月份的出租車真實數據。實驗采用3 種不同規(guī)模的數據集，分別為2 500 萬級、5 000 萬級和1 億級，其中2 500 萬級為2012 年10 月15 日1 天的數據，5 000 萬級是2012 年10 月15、16 日2 天的數據，1 億級是2012 年10 月15 日～2012 年10 月19 日的數據。

5.2 實驗設計

本部分設計了3 個實驗。實驗1 對比了本文提出的索引與其他索引在子查詢生成速度與子查詢生成個數的異同，并在不同數據規(guī)模、不同的查詢范圍下，比較了本文提出的索引方法與其他索引方法的查詢響應時間，還比較了內存消耗。由于在預分區(qū)時使用了歷史數據，實驗2 探究了使用不同規(guī)模的歷史數據對查詢響應時間的影響。實驗3 探究了不同的分區(qū)閾值對查詢響應時間與導入時間的影響。本文簡要介紹2 種對比的索引方法，其中對HGrid［6］拓展時間維度的索引方法是空間驅動類索引方法中的典型方法；ST-hash［16］索引方法是對經度、緯度和時間維進行混合編碼，Geomesa 中的Z3 索引使用了此方法，本文實現的每一維度都使用14 bit 進行編碼，再對3 個維度進行混合編碼，最后使用Base64 編碼方法將bit 數組編碼成7 位字符串，ST-hash［16］生成實例如圖9 所示。

5.2.1 索引方法比較

圖9 ST-hash 編碼方式Fig.9 Example of ST-hash encoding

隨機設定某空間范圍0.3°×0.3°，時間范圍為10 月15 日，本節(jié)實驗首先探究不同索引方式的子查詢生成時間以及子查詢生成個數，如圖10 所示。在給定的時間和空間范圍下，由于需要在二級索引上查找分區(qū)，所以本文方法子查詢生成時間最長，由于完成了對子查詢按照分區(qū)的合并，所以子查詢個數最少。本文構建索引方法與其他2種方法相同，構建的都是聚集索引。構建索引的過程就是將數據按照設計好的模型存入數據庫中，3 種方法都是以軌跡點的方式進行存儲，所以構建時間與對比的兩種方法大致相同，占用的空間情況也類似。

圖10 不同索引間對比Fig.10 Comparison between different indexes

圖11 在不同的數據規(guī)模與不同空間范圍下完成了實驗，其中的分區(qū)閾值選為5 000，實驗數據規(guī)模從2 500 萬級擴展到1 億級，空間查詢范圍由0.1°×0.1°擴展到0.3°×0.3°，時間范圍與上文保持一致，進行了3 次重復實驗將平均值繪制在圖中。由圖中的結果分析可知，本文提出的索引結構配合查詢優(yōu)化算法在不同的數據規(guī)模下均有較好的時間響應；在導入不同數據量級的軌跡數據時，查詢響應時間變化不大。

圖11 不同數據規(guī)模與空間范圍下的查詢響應時間Fig.11 Time performance of different data size and spatial scope

圖12 不同索引結構的內存代價Fig.12 Memory cost of different index structures

圖12 對比了本文方法與另外2 種方法的內存代價，實驗數據規(guī)模采用2 500 萬級，分區(qū)閾值與時空查詢范圍與上文保持一致時，內存代價比較的是執(zhí)行查詢時集群占用的內存資源最大值情況，在集群中搭建了Ganglia 分布式監(jiān)控系統監(jiān)控集群的內存使用情況。從圖中可以得出，由于本文方法需要在內存中預先緩存分區(qū)結果，所以相比較于其他2 種方法，在內存占用資源稍多；在I/O 代價方面，由于3 種數據全部存儲在HBase 數據庫中，I/O 代價可以等價為不同索引的查詢方法對HBase 數據庫的查詢次數。由圖10 可知，子查詢個數為SThash＞Extend_HGrid＞Our method，子查詢數量越多，查詢方法訪問HBase 數據庫的次數就越多，I/O 代價越高，所以本文的I/O 代價最小。

5.2.2 不同規(guī)模歷史數據對查詢響應時間的影響

由于使用歷史數據完成了預分區(qū)的生成，本節(jié)實驗探究了使用不同規(guī)模的歷史數據生成的索引結構對查詢響應時間的影響。實驗分別選取了1 天、2 天、4 天和8 天的歷史數據，利用各自生成的預分區(qū)結果分別將軌跡數據導入HBase 數據庫。選取的導入數據為2012 年10 月18 日2 500 萬量級的數據，空間查詢范圍與上文保持一致，時間范圍為10 月18 日，查詢響應時間如圖13 所示。隨著選用的歷史數據的天數增加，查詢響應時間變化不大，說明生成預分區(qū)的歷史數據天數對查詢響應時間影響不大，同時也從側面驗證了軌跡數據分布不均勻的特性在相同時間尺度下的相似性。

圖13 不同規(guī)模歷史數據預分區(qū)結果的查詢響應時間Fig.13 Time performance of different scale historical data pre-partition

5.2.3 不同的分區(qū)閾值對查詢的影響

本節(jié)實驗的合并閾值范圍設置從1 000 變化到20 000，其中包括1 000、3 000、5 000、10 000 和20 000，測試數據采用的是2012 年10 月15 日2 500萬量級的數據，隨機設定空間查詢范圍設置為［115.877 951，39.830 862 116.305 688，39.608 864］，時間范圍為10月15日，數據的導入以及查詢情況如圖14 所示。從圖中可以分析出，軌跡數據的導入速度與閾值設定的大小無關。對于不同閾值下的查詢操作，查詢響應時間呈現出先減少再穩(wěn)定的趨勢，其主要原因是當查詢閾值較小時，查詢范圍所覆蓋的分區(qū)數較多，使響應時間變慢，隨著分區(qū)閾值的增大，查詢范圍覆蓋的分區(qū)逐漸減少，響應速度變快，但隨著分區(qū)閾值的繼續(xù)增大，查詢范圍覆蓋的分區(qū)總數雖然減小，但是查詢方法還會對分區(qū)內Geohash編碼區(qū)域進行合并，所以子查詢數量變化不大，查詢響應時間趨于穩(wěn)定。

圖14 不同分區(qū)閾值的導入和查詢響應時間Fig.14 Results of different threshold experiments

6 結論

針對海量的時空軌跡數據分布不均勻的特性，本文提出了一種索引方法，并詳細地介紹了該索引的構建過程和與其相匹配的查詢算法。方法首先通過設計閾值的方法對Geohash 編碼進行合并生成分區(qū)，設計了基于HBase 的軌跡數據索引存儲模型，優(yōu)化了查詢時分區(qū)內的子查詢，有效地減少的子查詢數量。通過實驗證明，本文的索引方法在時空查詢方面優(yōu)于ST-hash 方法與擴展HGrid 的方法。下一步還將在以下幾個方面改進，首先是支持更多種類的軌跡查詢，如KNN 查詢、路徑查詢等；其次是由于構建的分區(qū)依賴于歷史抽樣數據，本文的抽樣數據與實驗數據為工作日數據，需要探究在非工作日時，構建的分區(qū)還是否有效；再者就是軌跡數據分布不均勻的特性是隨時間的變化而變化的，需要探究生成分區(qū)的有效周期，是否需要動態(tài)變化、變化頻率以及變化帶來的開銷等問題。