基于軌跡大數(shù)據(jù)時(shí)空分布的索引與查詢(xún)方法

李征宇，趙卓峰

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

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

1 相關(guān)工作

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

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

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

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

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

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

圖1 Geohash 立方體查詢(xún)示例Fig.1 Example of Geohash cube query

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

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

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

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

圖3 從宏觀(guān)的角度展示出在不同日期上的數(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ù)的平均值，可以觀(guān)察到這5 天的每個(gè)Geohash 中的數(shù)據(jù)量波動(dòng)不大，屬于同一數(shù)量級(jí)，所以使用了Geohash 的平均值表示每個(gè)Geohash 網(wǎng)格的數(shù)據(jù)特征。

圖3 兩日數(shù)據(jù)分布對(duì)比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)格中沒(méi)有數(shù)據(jù)，則跳過(guò)這一網(wǎng)格；如果將當(dāng)前Geohash 網(wǎng)格中的數(shù)據(jù)加入后，分區(qū)中的總數(shù)據(jù)量大于所設(shè)定的閾值，即分區(qū)結(jié)束，下一條數(shù)據(jù)開(kāi)始新的分區(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ū)號(hào)與Geohash 組的映射關(guān)系，1 個(gè)分區(qū)中包含1 個(gè)或多個(gè)同一編碼長(zhǎng)度的Geohash 編碼，每個(gè)Geohash 編碼都對(duì)應(yīng)1 個(gè)分區(qū)號(hào)。分區(qū)閾值設(shè)定為5 000，其中Partition Id 代表的是分區(qū)的自增序號(hào)，Partition Number 表示的是分區(qū)內(nèi)的數(shù)據(jù)量，Included Geohash 表示的是分區(qū)內(nèi)包含的Geohash編碼。

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

2.2 輔助二級(jí)索引

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如圖7 所示，01、02、03、04 為分區(qū)號(hào)，例如分區(qū)01=｛ws1070，ws1071，ws1072，ws1073，ws1074｝，QueryWindow1 和QueryWindow2 分別為查詢(xún)窗口。對(duì)于QueryWindow1 來(lái)說(shuō)，QueryWindow1 覆蓋的Geohash 編碼同屬于01 分區(qū)，其中包括ws1070、ws1071 和ws1074，由于ws1070 和ws1071相鄰，所以QueryWindow1 可以生成2 個(gè)子查詢(xún)，即01［ws1070，ws1071］和01［ws1074］，相較于擴(kuò)展的HGrid 方法，在總體查詢(xún)數(shù)據(jù)不變的情況下，子查詢(xún)個(gè)數(shù)由3 個(gè)減少為2 個(gè)；對(duì)于QueryWindow2，即整個(gè)區(qū)域都為查詢(xún)范圍，依據(jù)本文設(shè)計(jì)的查詢(xún)方法QueryWindow2 可生成4 個(gè)子查詢(xún)，為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ù)不變的情況下，子查詢(xún)個(gè)數(shù)由16 個(gè)減少為4 個(gè)，查詢(xún)效率可以得到顯著提升。圖8 給出了軌跡時(shí)空查詢(xún)的詳細(xì)分解與執(zhí)行過(guò)程，在時(shí)間復(fù)雜度方面，由于需要對(duì)每1 個(gè)partition 進(jìn)行遍歷，同時(shí)每個(gè)partition 中還包含多個(gè)Geohash 編碼，查詢(xún)方法的時(shí)間復(fù)雜度為o(n2)，空間復(fù)雜度同數(shù)據(jù)入庫(kù)時(shí)相同，取決于Geohash 編碼長(zhǎng)度。

圖7 查詢(xún)算法示意圖Fig.7 Example of query algorithm

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

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

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

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 硬盤(pán)和兩顆Intel E5-2620 0 @ 2.00 GHzCPU。

本文實(shí)驗(yàn)的軌跡數(shù)據(jù)采用浮動(dòng)車(chē)軌跡數(shù)據(jù)，來(lái)源于北京市2012 年10 月份的出租車(chē)真實(shí)數(shù)據(jù)。實(shí)驗(yàn)采用3 種不同規(guī)模的數(shù)據(jù)集，分別為2 500 萬(wàn)級(jí)、5 000 萬(wàn)級(jí)和1 億級(jí)，其中2 500 萬(wàn)級(jí)為2012 年10 月15 日1 天的數(shù)據(jù)，5 000 萬(wàn)級(jí)是2012 年10 月15、16 日2 天的數(shù)據(jù)，1 億級(jí)是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 對(duì)比了本文提出的索引與其他索引在子查詢(xún)生成速度與子查詢(xún)生成個(gè)數(shù)的異同，并在不同數(shù)據(jù)規(guī)模、不同的查詢(xún)范圍下，比較了本文提出的索引方法與其他索引方法的查詢(xún)響應(yīng)時(shí)間，還比較了內(nèi)存消耗。由于在預(yù)分區(qū)時(shí)使用了歷史數(shù)據(jù)，實(shí)驗(yàn)2 探究了使用不同規(guī)模的歷史數(shù)據(jù)對(duì)查詢(xún)響應(yīng)時(shí)間的影響。實(shí)驗(yàn)3 探究了不同的分區(qū)閾值對(duì)查詢(xún)響應(yīng)時(shí)間與導(dǎo)入時(shí)間的影響。本文簡(jiǎn)要介紹2 種對(duì)比的索引方法，其中對(duì)HGrid［6］拓展時(shí)間維度的索引方法是空間驅(qū)動(dòng)類(lèi)索引方法中的典型方法；ST-hash［16］索引方法是對(duì)經(jīng)度、緯度和時(shí)間維進(jìn)行混合編碼，Geomesa 中的Z3 索引使用了此方法，本文實(shí)現(xiàn)的每一維度都使用14 bit 進(jìn)行編碼，再對(duì)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)首先探究不同索引方式的子查詢(xún)生成時(shí)間以及子查詢(xún)生成個(gè)數(shù)，如圖10 所示。在給定的時(shí)間和空間范圍下，由于需要在二級(jí)索引上查找分區(qū)，所以本文方法子查詢(xún)生成時(shí)間最長(zhǎng)，由于完成了對(duì)子查詢(xún)按照分區(qū)的合并，所以子查詢(xún)個(gè)數(shù)最少。本文構(gòu)建索引方法與其他2種方法相同，構(gòu)建的都是聚集索引。構(gòu)建索引的過(guò)程就是將數(shù)據(jù)按照設(shè)計(jì)好的模型存入數(shù)據(jù)庫(kù)中，3 種方法都是以軌跡點(diǎn)的方式進(jìn)行存儲(chǔ)，所以構(gòu)建時(shí)間與對(duì)比的兩種方法大致相同，占用的空間情況也類(lèi)似。

圖10 不同索引間對(duì)比Fig.10 Comparison between different indexes

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

圖11 不同數(shù)據(jù)規(guī)模與空間范圍下的查詢(xún)響應(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 對(duì)比了本文方法與另外2 種方法的內(nèi)存代價(jià)，實(shí)驗(yàn)數(shù)據(jù)規(guī)模采用2 500 萬(wàn)級(jí)，分區(qū)閾值與時(shí)空查詢(xún)范圍與上文保持一致時(shí)，內(nèi)存代價(jià)比較的是執(zhí)行查詢(xún)時(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ù)全部存儲(chǔ)在HBase 數(shù)據(jù)庫(kù)中，I/O 代價(jià)可以等價(jià)為不同索引的查詢(xún)方法對(duì)HBase 數(shù)據(jù)庫(kù)的查詢(xún)次數(shù)。由圖10 可知，子查詢(xún)個(gè)數(shù)為SThash＞Extend_HGrid＞Our method，子查詢(xún)數(shù)量越多，查詢(xún)方法訪(fǎng)問(wèn)HBase 數(shù)據(jù)庫(kù)的次數(shù)就越多，I/O 代價(jià)越高，所以本文的I/O 代價(jià)最小。

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

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

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

5.2.3 不同的分區(qū)閾值對(duì)查詢(xún)的影響

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

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

6 結(jié)論

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