李征宇，趙卓峰

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

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

1 相關(guān)工作

現(xiàn)有的軌跡數(shù)據(jù)索引按構(gòu)造方法也可分為兩類：數(shù)據(jù)驅(qū)動方法與空間驅(qū)動方法［6］。

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

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

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

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

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

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

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

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

區(qū)別于只利用Geohash 編碼構(gòu)建的時(shí)空數(shù)據(jù)索引方法，本文索引方法的核心是利用歷史軌跡數(shù)據(jù)提前得到軌跡數(shù)據(jù)的分布規(guī)律，在索引構(gòu)建的過程利用此規(guī)律，將Geohash 編碼分區(qū)按歷史數(shù)據(jù)分布進(jìn)行合并，即通過閾值的方法對其進(jìn)行合并，這樣在查詢時(shí)本文方法的子查詢數(shù)量將會小于只利用Geohash 編碼的索引方法，并在查詢時(shí)對分區(qū)子查詢進(jìn)行分割，避免擴(kuò)大查詢區(qū)域。通過這2 種方式，有效地減少子查詢個(gè)數(shù)，提升查詢效率，并適當(dāng)?shù)钠胶饬巳蝿?wù)規(guī)模。本文索引的構(gòu)建過程如圖2所示。

圖2 索引構(gòu)建過程Fig.2 Process of building index

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

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

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

圖3 兩日數(shù)據(jù)分布對比Fig.3 Comparison of two-day data distribution

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

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

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

表1 中給出了分區(qū)劃分結(jié)果示例，表結(jié)構(gòu)體現(xiàn)出了分區(qū)號與Geohash 組的映射關(guān)系，1 個(gè)分區(qū)中包含1 個(gè)或多個(gè)同一編碼長度的Geohash 編碼，每個(gè)Geohash 編碼都對應(yīng)1 個(gè)分區(qū)號。分區(qū)閾值設(shè)定為5 000，其中Partition Id 代表的是分區(qū)的自增序號，Partition Number 表示的是分區(qū)內(nèi)的數(shù)據(jù)量，Included Geohash 表示的是分區(qū)內(nèi)包含的Geohash編碼。

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

2.2 輔助二級索引

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

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

表2 二級索引結(jié)構(gòu)Table2 Secondary index structure

3 基于HBase 的軌跡數(shù)據(jù)索引存儲模型

與許多軌跡管理系統(tǒng)類似，如文獻(xiàn)［15］中提出的垂直存儲模式，本文方法也是利用數(shù)據(jù)庫中1 行存取1 個(gè)軌跡點(diǎn)數(shù)據(jù)，每1 個(gè)軌跡點(diǎn)數(shù)據(jù)包括如下幾個(gè)屬性。

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

（2）空間屬性：包括本軌跡點(diǎn)的經(jīng)度、緯度。

（3）時(shí)間屬性：軌跡點(diǎn)的產(chǎn)生時(shí)間。

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

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

表3 數(shù)據(jù)存儲模型Table 3 Data storage model

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

圖6 軌跡數(shù)據(jù)入庫流程Fig.6 Process of importing trajectory data into HBase

4 軌跡數(shù)據(jù)時(shí)空查詢

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

如圖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 個(gè)子查詢，即01［ws1070，ws1071］和01［ws1074］，相較于擴(kuò)展的HGrid 方法，在總體查詢數(shù)據(jù)不變的情況下，子查詢個(gè)數(shù)由3 個(gè)減少為2 個(gè)；對于QueryWindow2，即整個(gè)區(qū)域都為查詢范圍，依據(jù)本文設(shè)計(jì)的查詢方法QueryWindow2 可生成4 個(gè)子查詢，為01［ws1070，ws1071，ws1072，ws1073，ws1074］、02［w s1075］、03［ws1076，ws1077，ws1078，ws1079］和04［ws107b，ws107c，ws107d，ws107e，ws107f，ws107g］，相較于擴(kuò)展的HGrid 方法，在總掃描數(shù)據(jù)不變的情況下，子查詢個(gè)數(shù)由16 個(gè)減少為4 個(gè)，查詢效率可以得到顯著提升。圖8 給出了軌跡時(shí)空查詢的詳細(xì)分解與執(zhí)行過程，在時(shí)間復(fù)雜度方面，由于需要對每1 個(gè)partition 進(jìn)行遍歷，同時(shí)每個(gè)partition 中還包含多個(gè)Geohash 編碼，查詢方法的時(shí)間復(fù)雜度為o(n2)，空間復(fù)雜度同數(shù)據(jù)入庫時(shí)相同，取決于Geohash 編碼長度。

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

圖8 軌跡數(shù)據(jù)時(shí)空查詢流程Fig.8 Spatio-temporal query process of trajectory data

5 實(shí)驗(yàn)評價(jià)

為了測試本文提出的索引方法的查詢響應(yīng)情況，基于NoSQL 的HBase 數(shù)據(jù)庫實(shí)現(xiàn)了數(shù)據(jù)持久化，借助HBase Java api 實(shí)現(xiàn)了數(shù)據(jù)的分布式查詢算法完成數(shù)據(jù)查詢。

5.1 實(shí)驗(yàn)準(zhǔn)備

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

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

5.2 實(shí)驗(yàn)設(shè)計(jì)

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

5.2.1 索引方法比較

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

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

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

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

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

圖12 不同索引結(jié)構(gòu)的內(nèi)存代價(jià)Fig.12 Memory cost of different index structures

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

5.2.2 不同規(guī)模歷史數(shù)據(jù)對查詢響應(yīng)時(shí)間的影響

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

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

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

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

圖14 不同分區(qū)閾值的導(dǎo)入和查詢響應(yīng)時(shí)間Fig.14 Results of different threshold experiments

6 結(jié)論

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