一種面向相似查詢的軌跡索引方法

王 飛 龐 悅 周向東 陳海波

1(復旦大學計算機科學技術學院 上海 200433) 2(國網上海市電力公司 上海 200122)

一種面向相似查詢的軌跡索引方法

王 飛1龐 悅1周向東1陳海波2

1(復旦大學計算機科學技術學院 上海 200433)2(國網上海市電力公司 上海 200122)

軌跡數據具有重要的應用價值，軌跡索引技術得到廣泛的研究與關注。傳統索引方法存在節點重疊、缺乏動態劃分空間能力和丟失大量原始信息等問題，為此提出一種面向相似查詢的軌跡索引方法GeoSAX。該方法將原始軌跡分成若干等長子段并采用基于Geohash的空間編碼；對編碼后的整條軌跡設計了基于HBase存儲的索引架構；實現相似軌跡查詢。GeoSAX不僅節點間沒有重疊，還能依據數據量的大小對空間動態劃分，同時保留指定精度的軌跡信息。在真實的航運和出租車數據集上進行的對比實驗表明，與傳統方法相比GeoSAX具有更好的軌跡查詢性能。

軌跡索引 相似查詢 Geohash 空間編碼 HBase

0 引 言

近年來隨著移動設備的普及和GPS定位技術的發展，現實生活中產生了海量移動對象的軌跡數據，如船舶的航運線路，出租車接送乘客的路線等。軌跡是移動對象運動過程中在不同時刻的位置序列，因此軌跡可以看作是一種多元時間序列數據[1]。軌跡數據有著非常重要的應用價值，如可以根據風暴的移動軌跡輔助預報自然災害[2]；可以根據人們的運動軌跡挖掘出一些行為習慣從而為人們的生活提供智能的個性化服務[3]。移動對象軌跡數據的模式挖掘是當前的研究熱點之一。

軌跡的各種應用均需要底層軌跡數據庫支持快速高效的查詢功能，如最近鄰查詢、區域查詢和軌跡查詢等。對于海量軌跡數據，不可能對每個查詢請求順序掃描全部數據，在一些對時間要求很高的場景中響應時間必須足夠快，因此需要索引技術來提高海量軌跡數據的分析和挖掘效率。

軌跡索引技術得到了廣泛的研究與關注。傳統的軌跡索引通常采用R樹以及R樹的擴展方法[4-7]，一般支持點查詢和區域查詢[8]。R樹索引中的兄弟節點存在重疊，會引起多次查找的問題；為維持樹的高度平衡，索引更新代價較大；一般不具備相似軌跡查詢的能力。支持相似軌跡查詢的索引一般采用劃分空間[9-10]和提取特征[11-12]等方式。當前采用劃分空間的索引保留了移動對象的空間信息，但基本上都是固定劃分空間，實際數據的分布可能并不均勻，對于索引而言，這樣會導致查詢效率降低?；谔卣魈崛〉乃饕ㄟ^降維找到相似軌跡，但是通常無法保留原始空間信息。軌跡數據的急劇膨脹使得傳統集中式索引的查詢效率大大降低，分布式軌跡索引技術已經引起國內外學者的關注。當前分布式索引方法主要用于點查詢和區域查詢，針對相似軌跡查詢的索引研究還比較少。

針對傳統方法存在的不足，本文提出一種面向相似查詢的軌跡索引方法GeoSAX。該方法將原始軌跡分成若干等長子段，每個子段采用Geohash編碼，所有子段的Geohash編碼組成一個符號串即GeoSAX表示，相似的軌跡具有相同的表示。對于海量軌跡數據，我們設計了基于HBase存儲的索引結構，可以對相似查詢快速響應。GeoSAX不僅可以根據數據量動態劃分空間，還保留了指定精度下的原始軌跡信息。本文在真實的航運數據和紐約出租車數據上進行了充分的實驗來評價驗證本文提出的方法，實驗結果表明GeoSAX能獲得比已知基準方法更好的搜索性能。

1 相關工作

原始軌跡數據通常規模巨大，因而將軌跡序列壓縮表示非常重要。舉例來說，假設某個城市有1萬輛出租車，每5秒種釆集一次出租車的位置來追蹤其軌跡，那么一天收集到的軌跡數據就有4 GB左右[1]。分段聚集近似PAA[13]，符號聚集近似SAX[14]和可索引的符號聚集近似iSAX[15]三種時間序列表示方法計算簡單、壓縮效果良好，被廣泛使用。PAA把時間序列分成若干等長子段，各子段用段內均值表示。SAX首先將時間序列轉換成均值為0標準差為1的標準序列，假設標準化后的序列近似服從正態分布，之后對標準序列使用PAA分割，最后根據正態分布的概率區間將PAA表示的序列離散化為符號串。iSAX是Shieh等[15]在SAX基礎之上提出的一種根據數據量大小動態變化的符號化表示，用不同基數大小表示的二進制位來標記數據的密集程度。

在空間范圍中有三種類型對象：點、區域和軌跡。按照空間對象的類型，Zheng[8]等將時空查詢分為點查詢、區域查詢和軌跡查詢三種。點查詢是指查詢符合給定條件的移動對象，如查詢經過某地的移動對象。區域查詢是指查詢符指定時空區域的移動對象，如查詢某個區域內的移動對象。軌跡查詢是指查詢與給定的整條軌跡具有某種時空關系的整條軌跡，如查詢某條軌跡的相似軌跡。

面向點查詢和范圍查詢的軌跡索引主要是基于R樹以及R樹的擴展方法，分為四種：移動對象歷史位置索引，如固定網絡的R樹索引結構FNR-tree[4]；移動對象當前位置索引，如基于固定網絡的快速更新索引機制IMORS[5]；移動對象未來位置索引，如時間參數化的R樹TPR-tree[6]；移動對象過去、現在和未來的全時空位置索引，如BBx-index[7]。面向相似軌跡查詢的軌跡索引方法有多種，如基于空間劃分的軌跡索引[9-10]和基于特征提取的軌跡索引[11-12]。

基于空間劃分的軌跡索引，采用劃分空間單元格或立方體的方式對空間編碼來建立索引。Bakalov等提出軌跡索引方法TRSTJ[9]，首先使用PAA方法對軌跡降維，然后將降維后的軌跡二維空間切分成相同大小的單元格，并為每個單元格分配一個符號，最終一條軌跡被表示成一個字符串。Thach等提出TraSAX[10]，該方法對單元格的x軸使用字母編碼，y軸使用數字編碼，使得一個單元格同時由字母和數字編碼組成。

基于特征提取的軌跡索引，提取軌跡的特征并編碼來建立索引。Bashir等[11]使用PCA、譜聚類等方法提取視頻中的動作軌跡特征，并表示成字符串。Pao等[12]提取鼠標移動軌跡的步長和角度特征，并使用Isomap對軌跡進行表示。

在大數據的背景下，分布式軌跡數據庫的研究已經引起國內外學者的關注。Li等[16]結合車輛數據的實際特點，設計了基于Bigtable的存儲模型，可以查詢出租車在某段時間內的運行軌跡。Ma等[17]對海量的軌跡數據采用分布式文件系統HDFS存儲，可以檢索指定車輛的軌跡。

2 GeoSAX軌跡索引算法

2.1 基于Geohash算法的空間編碼

Geohash算法是一種常用的二維空間編碼方法，在眾多領域有著廣泛的應用[18-19]。地球經度區間范圍是[-180,180]，二分為左區間[-180,0)和右區間[0,180]，左區間編碼為0，右區間編碼為1，緯度區間同理，依次對經緯度空間進行劃分，得到Geohash編碼。如上海金茂大廈的經緯度坐標(31.235 253 6 N,121.503 402 3 E)，在二進制編碼總位數為3下得到的二進制Geohash編碼是111，在二進制編碼總位數為4下得到的二進制Geohash編碼是1110，如圖1所示，其中基數可以理解為對空間劃分的細致程度。

圖1 Geohash算法的空間編碼

iSAX離散化時會指定基數，即對正態曲線的劃分，如a=4表示將正態曲線等概率的切分為4份。基于Geohash的空間編碼同樣需要指定基數，即空間切割的精度。Geohash可以同時對經度和緯度進行切割，假設對經度和緯度編碼位數之和為t，Geohash切割的基數設置為2t。Geohash組碼時奇數位存放經度編碼，偶數位存放緯度編碼，故每次升高基數時，如果經度和緯度的編碼位數相同則經度的位數加一，如果當前經度的位數大于緯度位數則緯度位數加一。參見圖1。

2.2 GeoSAX表示

圖2展示了GeoSAX的索引結構，圖中軌跡被分為3段，初始基數均為4。當某一索引節點包含的軌跡數量超過指定閾值，該節點分裂為兩個新的索引節點，原先的索引節點作為中間節點，圖中的節點{11,01,10}分裂產生 {11,010,10}和{11,011,10}兩個新的葉子節點。圖3展示了索引節點{11,011,10}的空間劃分情況。

圖2 GeoSAX索引示意圖

圖3 GeoSAX索引節點示意圖

下面描述GeoSAX表示的生成過程。

第一步，本文采用PAA模型將原始軌跡數據從n維降到w維。給定軌跡：

T={,…,,…,}

(1)

式中：n表示軌跡長度，lngi和lati分別表示第i個軌跡點的經度和緯度。

使用PAA軌跡約減為：

(2)

式中:w表示約減后的維度，w?n，每個子段用其均值代替：

(3)

第二步，本文將PAA的表示離散化為符號，不同于SAX，這里使用基于Geohash的空間編碼單個軌跡位置進行編碼，得到：

(4)

通過Geohash編碼可以得到單個軌跡點在指定精度下的壓縮表示，進而得到整個軌跡的壓縮表示。對于壓縮表示，可以執行Geohash的反過程得到單個軌跡點在指定精度下的信息，進而得到整條軌跡在指定精度下的信息。

2.3 GeoSAX索引構建與相似查詢

GeoSAX索引是樹形結構的，第一層可以看作是多叉樹，且第一層所有節點基數相同，即對原始空間采用同樣的切分精度。從第二層開始，葉子節點根據數據的密集程度進行二分裂，則以第一層節點為根節點的子樹是二叉樹。GeoSAX索引構建因此可以看作是對多叉樹和二叉樹混合在一起的樹的構建，GeoSAX索引建立詳細過程如算法所示。

GeoSAX索引建立算法

1) 輸入：軌跡ts, 當前索引節點node，空間的初始劃分基數a，軌跡分段數w和節點分裂閾值th

2) 輸出： GeoSAX索引添加軌跡ts

3) G=GeoSAX (ts,索引參數)//獲取ts的GeoSAX表示

4) if當前節點存在GeoSAX表示為G的后繼節點

5) node=獲取GeoSAX表示為G的后繼節點

6) if node 為葉子節點

7) if node沒滿 //小于節點分裂閾值th

8) node直接插入ts

9) else//節點已滿，需要分裂

10) 新建一個中間節點newnode

11) newnode.insert(ts)

12) for each originTS in node

13) newnode.insert(ts)

14) 刪除node節點

15) 將newnode作為當前節點的后繼節點

16) else// node為中間節點

17) node.insert(ts)

18) else

19) 新建一個GeoSAX表示為G的葉子節點L

20) 葉子節點L直接插入ts

GeoSAX索引相似查詢假設相似的兩條軌跡具有相同的GeoSAX表示。GeoSAX索引是層次且沒有重疊的，因而可以遍歷索引樹找到對應的索引節點，獲取其索引的所有軌跡，分別計算這些軌跡與查詢軌跡之間的距離，返回距離最小的軌跡作為相似查詢結果。軌跡s和t的距離定義如式(5)所示，其中n表示軌跡長度，i=1表示經度，i=2表示緯度。

(5)

2.4 GeoSAX索引在HBase中的存儲設計

HBase是列存儲、高性能、可伸縮、實時讀寫的分布式數據庫，可以存儲海量數據，我們將原始數據和GeoSAX索引分別存儲在HBase上的兩張表。原始數據表中的Rowkey為軌跡編號。GeoSAX索引表中Rowkey為索引節點編號。HBase查詢速度受限于網絡帶寬，因此將原始數據表中value設置為原始軌跡序列化后的byte數組，GeoSAX索引表中value設置為節點對應的參數序列化后的byte數組。如表1所示。

表1 GeoSAX索引表設計

3 實驗設計

3.1 實驗數據和環境

(1) 航運數據

www.vesselfinder.com是一個在線免費航運船舶跟蹤網站，可以獲得全球船舶的軌跡，我們從該網站爬取40 000條船的軌跡，每條軌跡包含200個位置的經緯度坐標，位置采集間隔為5分鐘。

(2) 出租車數據

紐約出租車和轎車委員會在其網站公開了整個紐約的出租車出行記錄，包括每一趟出租車上下客的時間、經緯度坐標和出行距離等信息。我們選取13年部分出租車的軌跡，將每輛出租車每天的上下車坐標序列作為一條軌跡，共有12 759輛出租車，2 052 061條軌跡，202 288 485個軌跡點。

(3) 實驗環境

實驗采用由HBase-0.98.13和Hadoop-2.4.0搭建的10個節點構成的HBase集群，其中master節點內存32 GB，slave節點的內存16 GB，每個節點的硬盤1 TB，操作系統為Ubuntu14.04，網絡帶寬1 000 Mbit/s。

3.2 實驗設計

本文主要研究整條軌跡的相似查詢，屬于軌跡查詢，而絕大多數基于R樹的軌跡索引主要用于點查詢和區域查詢，TRSTJ[9]算法可以用于軌跡查詢，所以本文將TRSTJ作為對比算法而不考慮與基于R樹的軌跡索引作為對比。TRSTJ采用固定空間劃分的方式，而GeoSAX軌跡索引是根據數據量的大小對空間進行動態劃分的方式。為了驗證GeoSAX索引方法的有效性，我們在同樣運行環境下，分別對GeoSAX、TRSTJ和原始數據順序掃描三種方法，在不同基數在下隨機相似查詢100次，并比較他們的查詢性能。在航運數據中GeoSAX的分裂閾值設置為200，在出租車數據中GeoSAX的分裂閾值設置為1 000。

3.3 實驗分析

(1) 航運數據索引

從圖4中可以看出，順序掃描與空間劃分無關，基數對順序掃描沒有影響，不同基數下順序掃描的時間相同。GeoSAX和TRSTJ均對空間進行劃分，建立了相應的索引機制，因而均比順序掃描要快得多。

圖4 航運數據上的查詢性能對比

從圖4中還可以發現，相同基數下GeoSAX的查詢性能均比TRSTJ要好，如基數為256時GeoSAX查詢速度是TRSTJ的5倍，基數為1 024時，GeoSAX查詢速度是TRSTJ的3倍。這是因為TRSTJ對空間采取固定劃分方式，所以TRSTJ索引中數據分布很不均勻，極少數的索引節點索引了大多數的軌跡，大多數的索引節點只索引了少部分的軌跡。因而TRSTJ大部分的查詢發生在極少數的索引節點上，而這些索引節點又索引了大量軌跡，查詢需要掃描節點上索引的所有軌跡，該查詢已經退化為順序掃描，性能大大降低。以基數256為例，統計TRSTJ和GeoSAX單個索引節點索引的軌跡數量的情況。如圖5所示，對于TRSTJ中索引1～9條軌跡的索引節點，其數量占總的索引節點數量的72.68%，而GeoSAX占65.10%；TRSTJ中索引1 000條以上軌跡的索引節點，其數量占總的索引節點數量2.26%，而GeoSAX的分裂閾值為200，不存在索引1 000條以上軌跡的索引節點。從圖6可以看出，TRSTJ中索引1～9條軌跡的索引節點，其索引的軌跡數量占總軌跡數量的7.69%，而GeoSAX只占1.69%；TRSTJ中索引1 000條以上的索引節點，其索引的軌跡數量占總軌跡數量的68.57%，而GeoSAX的分裂閾值為200，不存在索引1 000條以上軌跡的索引節點。

與TRSTJ相比，GeoSAX索引節點索引軌跡的數量分布相對均勻。GeoSAX可以隨著數據量的大小動態調整索引結構，當單個節點包含的軌跡數量超過指定閾值節點則分裂，雖然增加了查詢的深度，但是在每個索引節點上查詢時間大大縮短，從而提高了整體查詢的性能。

圖5 基數為256時索引節點分布情況

圖6 基數為256時軌跡數量分布情況

此外，從圖4中還發現, 隨著基數的增長，GeoSAX和TRSTJ的性能均得到提升, 同時兩者的性能差距逐漸縮小。這是由于TRSTJ和GeoSAX的索引節點數都在增長，每個索引節點對應的軌跡數量縮小，掃描單個索引節點的時間縮短，從而提升了整體的查詢性能。但是索引基數并不能無限制擴大，因為這樣會引起索引空間膨脹，占有過大存儲空間等問題。因此，GoeSAX顯示出可以在合理的基數的情況下，獲得更好的查詢效率。

(2) 出租車數據索引

航運數據是全球的船只，而紐約出租車數據僅在紐約地區，故紐約出租車數據的初始基數要比航運數據大得多，即初始空間劃分要更加細致。

圖7中是對紐約出租車數據進行查詢，可以看出，GeoSAX和TRSTJ的查詢表現與航運數據是相似的。順序掃描與空間劃分無關，GeoSAX和TRSTJ均建立了相應的索引機制，均比順序掃描要快得多。相同基數下GeoSAX的查詢性能同樣均比TRSTJ要好，如基數為8 388 608時GeoSAX查詢速度是TRSTJ的112倍，基數為16 777 216時，GeoSAX查詢速度是TRSTJ的48倍。航運數據軌跡量是百萬級，而軌跡點則有2億多，我們的查詢仍然可以在可接受的時間范圍內給出相似查詢結果。

圖7 出租車數據上的查詢性能對比

4 結 語

本文總結了現有軌跡索引存在的問題，提出一種面向相似查詢的軌跡索引方法GeoSAX。該方法將原始軌跡分成若干等長子段，每個子段均采用基于Geohash的空間編碼，設計了基于HBase存儲的軌跡索引方法GeoSAX。索引不僅節點之間沒有重疊，還可以根據數據量的大小對空間動態劃分，并保留了指定精度下的軌跡信息。實驗表明，在相同基數下GeoSAX搜索性能均優于已知的基準索引方法，在海量數據下GeoSAX對相似軌跡查詢可以快速響應。本文提出的方法以僅包含經緯度位置信息的二元軌跡情況為例，但是可以很方便的擴展到包含速度、方向等其他信息的多元軌跡情況。下一步研究將側重于包含眾多信息的多元軌跡索引建立方法。

[1] 龔旭東. 軌跡數據相似性查詢及其應用研究[D]. 合肥: 中國科學技術大學, 2015.

[2] Sefidmazgi M G, Sayemuzzaman M, Homaifar A. Non-stationary time series clustering with application to climate systems[M]//Advance trends in soft computing. Springer, 2014:55-63.

[3] 郭黎敏, 高需, 武斌, 等. 基于停留時間的語義行為模式挖掘[J]. 計算機研究與發展, 2017(01):111-122.

[4] Frentzos E. Indexing objects moving on fixed networks[C]//International Symposium on Spatial and Temporal Databases. Springer, 2003: 289-305.

[5] Kim K, Kim S, Kim T, et al. Fast indexing and updating method for moving objects on road networks[C]//Web Information Systems Engineering Workshops. IEEE, 2003: 34-42.

[7] Lin D, Jensen C S, Ooi B C, et al. Efficient indexing of the historical, present, and future positions of moving objects[C]//Proceedings of the 6th international conference on Mobile data management. ACM, 2005:59-66.

[8] Zheng Y, Zhou X. Computing with Spatial Trajectories[M]. New York, NY:Springer Verlag, 2011.

[9] Bakalov P, Hadjieleftheriou M, Tsotras V J. Time relaxed spatiotemporal trajectory joins[C]//Proceedings of the 13th annual ACM international workshop on Geographic information systems. ACM, 2005:182-191.

[10] Thach N H, Suzuki E. A symbolic representation for trajectory data[C]//The 24th Annual Conference of the Japanese Society for Artificial Intelligence, JSAI, Nagasaki,2010:1-4.

[11] Bashir F I, Khokhar A A, Schonfeld D. Real-Time Motion Trajectory-Based Indexing and Retrieval of Video Sequences[J]. IEEE Transactions on Multimedia, 2007,9(1):58-65.

[12] Pao H K, Fadlil J, Lin H Y, et al. Trajectory analysis for user verification and recognition[J]. Knowledge-Based Systems, 2012, 34(5):81-90.

[13] Keogh E, Chakrabarti K, Pazzani M, et al. Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases[J]. Knowledge and information Systems, 2001,3(3):263-286.

[14] Lin J, Keogh E, Wei L, et al. Experiencing SAX: a novel symbolic representation of time series[J].Data Mining and knowledge discovery, 2007,15(2):107-144.

[15] Shieh J, Keogh E. iSAX: disk-aware mining and indexing of massive time series datasets[J].Data Mining and Knowledge Discovery, 2009,19(1):24-57.

[16] Li Q, Zhang T, Yu Y. Using cloud computing to process intensive floating car data for urban traffic surveillance[J].International Journal of Geographical Information Science, 2011,25(8):1303-1322.

[17] Ma Q, Yang B, Qian W, et al. Query processing of massive trajectory data based on mapreduce[C]//Proceedings of the first international workshop on Cloud data management. ACM, 2009:9-16.

[18] Jiang J, Lu H, Yang B, et al. Finding top-k local users in geo-tagged social media data[C]//Data Engineering (ICDE), 2015 IEEE 31st International Conference on. IEEE, 2015:267-278.

[19] Liu R, Buccapatnam S, Gifford W M, et al. An Unsupervised Collaborative Approach to Identifying Home and Work Locations[C]//Mobile Data Management (MDM), 2016 17th IEEE International Conference on. IEEE, 2016:310-317.

AMETHODOFTRACKINDEXFORSIMILARITYSEARCH

Wang Fei1Pang Yue1Zhou Xiangdong1Chen Haibo2

1(SchoolofComputerScience,FudanUniversity,Shanghai200433,China)2(StateGridShanghaiElectricCompany,Shanghai200122,China)

Because the tracking data have important application value, the track index technology has been widely studied and concerned. Traditional indexing methods have many problems such as node overlap, lack of dynamic partitioning of spatial capabilities and loss of a large number of original information. Therefore, we propose GeoSAX, a track index method for similarity search. In this method, the original tracking was divided into several equal segments, and spatial coding based on Geohash was adopted. We designed an indexing architecture for the whole track after encoding, which was based on HBase storage. Thus, the similarity search was realized. GeoSAX not only does not overlap between nodes, but also dynamically divides the space according to the size of the data, while preserving the track information of the specified precision. Contrast experiments on real shipping and taxi data sets show that GeoSAX has better track search performance than traditional methods.

Track index Similarity search Geohash Spatial coding HBase

2017-03-28。國家高技術研究發展計劃項目(2015AA050203)；國家自然科學基金項目(61370157)；國家電網公司總部科技項目(52094016000A)。王飛，碩士生，主研領域：軌跡索引，時間序列。龐悅，博士生。周向東，教授。陳海波，高工。

TP3

A

10.3969/j.issn.1000-386x.2017.11.001