MTSAX:一種新的多元軌跡索引方法

王 飛,龐 悅,周向東,陳海波

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

0 概述

隨著傳感器、無線通信網絡以及GPS定位等技術的飛速發展,各種基于位置的應用產生了海量軌跡數據,如導航地圖上的出行記錄、跑步軟件上的歷史線路等。軌跡是一種位置相關的時間序列[1]。由于實際應用中移動對象往往同時包含多種信息,如速度和運動方向等,因此多元軌跡數據在導航規劃、位置服務等領域[2-3]具有非常重要的應用價值,得到了越來越多的研究與關注。

為了提高海量多元軌跡數據的分析和挖掘效率,軌跡數據的索引技術是關鍵。學術界對軌跡索引技術進行了大量研究,以往工作主要在面向點查詢和范圍查詢[4]的軌跡索引研究[5-8]。近年來出現的面向相似軌跡查詢的方法中,基于空間劃分的索引[9]通常對原始空間采取固定劃分的方式;基于特征壓縮的索引通常會丟失大量原始空間信息[10];基于度量空間的索引[11]運用三角不等式等下界過濾技術提高查詢效率,但該類索引仍難以克服高維數據索引面臨的“維災問題”。

本文提出一種新的多元軌跡索引方法MTSAX。對單個軌跡點設計基于Geohash的GeoWord編碼,根據經度、緯度、速度等數據的密集程度和數據的重要性進行動態編碼,保留指定精度下的軌跡信息。將每條軌跡分成若干等長子段來壓縮原始軌跡,每個子段采用GeoWord編碼,所有子段的GeoWord編碼組成的符號串代表一條軌跡,即用MTSAX表示。對于MTSAX表示的整條軌跡,設計了基于一元時間序列索引iSAX技術的多元軌跡索引結構,實現一種新的軌跡索引MTSAX。

1 相關工作

文獻[4]提出軌跡查詢的3種類型:點查詢,范圍查詢和軌跡相似查詢。面向點查詢和范圍查詢的軌跡索引又可劃分為移動物體的歷史位置索引[5]、當前位置索引[6]、未來位置索引[7]和全時空位置索引[8]。軌跡相似查詢有多種方式,常見的面向相似軌跡查詢的索引方法如下:

1)基于空間劃分的軌跡索引。該類方法通常采用劃分空間單元格的方式對原始空間進行編碼,借助空間編碼建立索引。文獻[9]提出軌跡索引方法TRSTJ,首先使用PAA[12]方法將原始軌跡分段表示,然后將PAA表示的軌跡空間切分成相同大小的單元格,并為每個單元格分配一個符號,最終一條軌跡被表示成一個字符串。

2)基于特征壓縮的軌跡索引。該類方法提取軌跡的特征并編碼,借助特征編碼建立索引。文獻[10]提出一種多元時間序列索引方法,該方法將多元時間序列以多變量求和的方式轉化為一元時間序列,使用PAA方法把一元時間序列變成N維向量,最后使用R樹來索引該N維向量。

3)基于度量空間的軌跡索引。該類方法先選擇若干參考點,定義某種距離,再計算所有軌跡相對于參考點的距離,最后在查詢時通過這些參考點過濾掉不符合要求的軌跡。文獻[11]提出一種基于參考點距離的方法,建立了多元時間序列索引LBS,在飛行數據集上進行相似性查詢。

2 多元軌跡符號化索引MTSAX

2.1 一元時間序列索引方法iSAX

文獻[12]在分段聚集近似PAA[12]和符號化聚集近似SAX[13]的基礎之上,提出一種可索引的符號化聚集近似方法iSAX[14],可以索引海量一元時間序列,支持時間序列相似性查詢。iSAX假設原始時間序列服從高斯分布,并將原始時間序列轉換成均值為0標準差為1的標準時間序列。iSAX采用PAA方法將時間序列分成若干等長子段,然后根據正態分布的概率區間將均值表示的序列離散化為符號串,最后將符號化表示的時間序列進行樹狀索引。iSAX可以根據時間序列的分布情況采用不同的離散化基數來動態編碼。

2.2 多維空間編碼GeoWord

Geohash是一種二維空間編碼,對經緯度交替編碼,缺乏靈活性。多元軌跡不僅包含移動物體在運動過程中的經緯度位置,還包含速度、方向等信息;不同變量的重要性一般也不同,例如在軌跡中經緯度位置通常比速度、方向更加重要。因此,本文提出一種基于Geohash的多維空間編碼GeoWord,可以對經緯度位置和速度、方向等附加信息同時編碼,并考慮了不同變量數據的密集程度及重要性。

GeoWord算法需要給定單個軌跡點的多元信息和對應的離散化基數。離散化基數用于將PAA得到的連續值離散化為指定精度的編碼,對于經度、緯度這樣的空間位置可以看做是對空間切分的精度。GeoWord可以采用等切分獲得分割點,也可以通過對數據進行采樣估計獲得分割點。圖1以等切分為例展示了GeoWord編碼,初始切分中的GeoWord編碼為021212,其中,02、12、12分別由經度、緯度和速度3個變量的編碼組成,上標表示該變量的離散化基數。

圖1 GeoWord編碼示意圖

GeoWord可以選擇不同變量進一步離散化,如圖1中在初始切分的基礎上可以對經度、緯度和速度進行切分。切分變量的選擇依賴于不同變量數據的密集程度和變量本身的重要性,切分的目的是為了更好地索引軌跡,關于切分變量的選擇策略見2.3節MTSAX索引構建方法中的節點分裂介紹。

GeoWord編碼可以得到單個多元軌跡點在指定精度下的壓縮表示,從而得到整條軌跡的壓縮表示;對于壓縮表示,執行GeoWord的逆過程可以得到單個多元軌跡點在指定精度下的信息,從而得到整條軌跡在指定精度下的信息。

算法1GeoWord算法

輸出第i個軌跡點GeoWord編碼

1.gi=null//保存GeoWord編碼

2.for j from 1 to m//對m個變量依次編碼

3. 獲取基數aij對應的所有分割點cuts[]

7.end for

8.return gi//第i個軌跡點GeoWord編碼

2.3 多元軌跡符號化表示

如圖2所示為MTSAX的索引結構,圖3中軌跡被分為3段,各變量初始基數均為2。當某一索引節點包含的軌跡數量超過指定閾值,該節點分裂為2個新的索引節點,原先的索引節點作為中間節點,圖2中的節點{121202,021212,120202}分裂產下面描述MTSAX表示的生成過程。

生{121202,022412,120202}和{121202,023412,120202}2個新的葉子節點。圖3所示為索引節點{121202,022412,120202}的空間劃分情況。

圖2 MTSAX索引結構示意圖

圖3 MTSAX索引節點空間劃分示意圖

步驟1本文采用PAA模型將原始多元軌跡數據從n維降到w維。

給定多元軌跡:

T0= {(p11,p12,…,p1m),…,(pi1,pi2,…,pij,…,

pim),…,(pn1,pn2,…,pnm)}

(1)

其中,n表示軌跡長度,m表示軌跡變量的數目,pij表示第i個軌跡點的第j個變量,1≤i≤n,1≤j≤m。

使用PAA軌跡約減為:

(2)

每個子段用其均值代替為:

(3)

步驟2本文將多元軌跡的PAA表示離散化為符號,使用GeoWord算法對單個多元軌跡位置編碼,得到:

T2={g1,g2,…,gi,…,gw}

(4)

其中,gi為(pi1,pi2,…,pij,…,pim)經過GeoWord編碼得到的表示,1≤i≤w,w個GeoWord編碼{g1,g2,…,gi,…,gw}組成一個MTSAX表達。

2.4 MTSAX索引構建方法

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

算法2MTSAX索引建立

輸入需要插入的多元軌跡ts

輸出MTSAX索引插入多元軌跡ts

1.獲取ts的MTSAX表示G

2.if當前索引節點存在MTSAX表示為G的后繼節點

3. 獲取MTSAX表示為G的后繼節點node

4. if node 為葉子節點

5. if node存儲的軌跡數量小于節點分裂閾值th

6 node直接插入ts

7. else//葉子節點索引的軌跡已滿,需要分裂

8. 新建中間節點newnode

9. newnode遞歸插入ts和node索引的所有軌跡

10. 刪除node節點

11. 將newnode作為當前節點的后繼節點

12. else// node為中間節點

13. node遞歸插入ts

14.else

15. 新建MTSAX表示為G的葉子節點newLeaf

16. 葉子節點newLeaf直接插入ts

MTSAX索引采用二分裂的方式,因此,分裂過程中可以升高某子段的某個變量的基數,將原先葉子節點索引的軌跡分配到2個新的葉子節點。節點分裂后還可能有新的數據插入,所以從概率上選擇最可能均分數據的某子段的某個變量升高基數。依次計算要分裂的葉子節點索引的所有軌跡數據在w個子段的m個變量的均值μ和標準差σ,若某子段的某個變量的均值越靠近升高基數后得到的新分割點a,同時對應的標準差越大,那么從概率上就越可能在新的分割點均勻地分配數據;考慮到各變量的量綱不同,需要除以其最大值max歸一化;考慮不同變量本身的重要性weight,這樣在相似性查詢中可以更加傾向重要性更大的變量。通過求解式(5)可以尋找最可能均分數據的分裂子段和分裂變量。圖4所示為每段包含2個變量的三段軌跡數據從基數2升高到基數4的情況,求解得到在第2段的第2個變量分裂能夠從概率上最均勻的分配數據。

(5)

圖4 GeoWord對切分變量的選擇

2.5 基于MTSAX的多元軌跡相似軌跡查詢

MTSAX索引相似查詢假設相似的兩條多元軌跡具有相同的MTSAX表示,查詢的結果是與查詢軌跡距離最近的軌跡。MTSAX索引是層次且沒有重疊的,可以遍歷索引樹找到對應的索引節點,獲取其索引的所有軌跡,分別計算這些軌跡與查詢軌跡之間的距離,返回距離最小的軌跡。使用式(6)計算軌跡s和t之間的距離,計算過程中考慮了不同變量的重要性,距離越小越相似。

(6)

其中,m表示軌跡的變量數目,n表示軌跡中包含的軌跡點數目,sij和tij分別表示軌跡s和t在第i個變量的第j個軌跡點,wi表示第i個變量的權重。

3 實驗結果與分析

3.1 數據集

航運數據:從全球免費在線航運船舶跟蹤網站www.vesselfinder.com爬取40 000條船的軌跡,每條軌跡有200個軌跡點,每個軌跡點包含經緯度坐標和航速3項信息。

GeoLife數據集:GeoLife數據集[15]是一個關于被廣泛使用的軌跡數據集,有18 670條軌跡,24 876 978個軌跡點,軌跡總距離為1 292 951 km。軌跡由用戶步行、騎自行車、乘坐公交車、出租車等多種出行方式產生,每個軌跡點包含經度、緯度和海拔3項信息。

3.2 對比方法

對比方法如下:

1)在基于空間劃分的軌跡索引中,選擇文獻[9]提出采用固定空間劃分的TRSTJ作為對比方法。

2)在基于空間劃分的軌跡索引中,選擇文獻[10]提出的基于多變量加和的軌跡索引方法,將其簡記為ADD。ADD的處理過程與本文方法處理步驟類似,主要區別在于ADD對原始的多元軌跡采用多變量加和的方式,而MTSAX采用GeoWord編碼。

3)在基于度量空間的軌跡索引中,選擇文獻[11]提出的基于參考點距離的LBS作為對比方法。

3.3 結果分析

為驗證MTSAX索引方法的有效性,本文在相同初始基數下分別對MTSAX、TRSTJ、ADD、LBS和原始數據順序掃描5種方法隨機查詢100次,通過平均查詢時間比較這些方法的查詢性能。

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

查詢性能對比過程如下:

1)MTSAX和順序掃描的對比

從圖5和表1中可以看出,順序掃描與空間劃分無關,基數對順序掃描沒有影響,不同基數下順序掃描的時間相同。MTSAX、TRSTJ、ADD和LBS建立了相應的索引機制,因而均比順序掃描要快。

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

方法基數為2基數為4基數為8基數為16MTSAX257.27148.4796.4022.77TRSTJ4 534.682 063.50279.6091.93ADD346.60267.30246.40233.50LBS916.35916.35916.35916.35順序掃描7 693.737 693.737 693.737 693.73

2)MTSAX和TRSTJ的對比

從圖5和表1中可以看出,相同基數下MTSAX的查詢性能均比TRSTJ要好,如基數為2時MTSAX查詢速度是TRSTJ的17.6倍,基數為4時MTSAX查詢速度是TRSTJ的13.9倍。這是TRSTJ對空間采取固定劃分方式,導致TRSTJ索引中數據分布很不均勻,極少數的索引節點索引了大多數的軌跡,大多數的索引節點只索引了少部分的軌跡。因此,TRSTJ大部分的查詢發生在極少數的索引節點上,而這些索引節點又索引了大量軌跡,查詢需要掃描節點上索引的所有軌跡,該查詢已經退化為順序掃描,性能大大降低。

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

3)MTSAX和ADD的對比

從圖5和表1中可以發現,在相同基數下MTSAX效果均比ADD方法要好。這是因為ADD方法將多個變量加和,不同變量數據的變化被抵消,索引節點存放了很多不相似的軌跡,查詢時間變長。

4)MTSAX和LBS的對比

LBS采用基于度量空間的方法,與空間劃分無關,因此在不同初始空間基數下結果相同。由于時間序列的高維特性,基于度量空間的方法會面臨維災問題,當維度超過15時索引性能會隨著維度的膨脹明顯下降,而實驗中每條軌跡包含200個軌跡點,遠遠大于15。此外,LBS將整條軌跡分成多個子段,查詢整條軌跡需要將多個子段拼接在一起,降低了查詢效率。

3.3.2 GeoLife數據集上的查詢性能對比

圖6與表2是在GeoLife數據集上進行查詢得到的性能對比,可以看出,MTSAX、TRSTJ、ADD、LBS和順序掃描5種方法的查詢表現與航運數據是相似的。順序掃描與空間劃分無關,MTSAX、TRSTJ、ADD、LBS均建立了相應的索引機制,均比順序掃描要快。在相同基數下,MTSAX的查詢性能表現最佳。如基數為2時MTSAX查詢速度是TRSTJ的13.9倍、ADD方法的1.3倍、LBS方法的11.2倍、順序掃描的26.2倍;基數為4時MTSAX查詢速度是TRSTJ的8.5倍、ADD方法的1.3倍、LBS方法的11.9倍、順序掃描的27.8倍。

圖6 GeoLife數據集上的查詢性能對比

方法基數為2基數為4基數為8基數為16MTSAX67.3863.3455.6244.26TRSTJ935.78539.93468.6662.66ADD89.0583.7782.9078.93LBS752.36752.36752.36752.36順序掃描1 762.901 762.901 762.901 762.90

4 結束語

針對現有軌跡索引方法存在的問題,本文提出一種多元軌跡符號化索引MTSAX。該方法針對單個多元軌跡點設計了一種基于Geohash的新編碼GeoWord,在iSAX索引框架的基礎上,給出了移動對象歷史軌跡索引方法MTSAX。實驗結果表明,在相同基數下MTSAX搜索性能均優于已知的基準索引方法,在海量數據下MTSAX對近似查詢可以快速響應。下一步將側重于建立分布式軌跡索引,提升索引建立的速度。

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

[2] HECTOR G,HAN Jiawei,LI Xiaolei,et al.Adaptive fastest path computation on a road network:a traffic mining approach[C]//Proceedings of the 33rd International Conference on Very Large Data Bases.Washington D.C.,USA:IEEE Press,2007:794-805.

[3] GORJI S M,MOHAMMAD S,ABDOLLAH H.Non-stationary time series clustering with application to climate systems[M].Berlin,Germany:Springer,2014.

[4] ZHENG Yu,ZHOU Xiaofang.Computing with spatial trajectories[M].Berlin,Germany:Springer,2011.

[5] ELIAS F.Indexing objects moving on fixed networks[C]//Proceedings of International Symposium on Spatial and Temporal Databases.Washington D.C.,USA:IEEE Press,2003:289-305.

[6] KIM K S,KIM S W,KIM T W,et al.Fast indexing and updating method for moving objects on road networks[C]//Proceedings of Web Information Systems Engineering Workshops.Washington D.C.,USA:IEEE Press,2003:34-42.

[7] SALTENIS S,JENSEN C S,LEUTENEGGER S T.Indexing the positions of continuously moving objects[C]//Proceedings of 2000 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2000:331-342.

[8] LIN Dan,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.Washington D.C.,USA:IEEE Press,2005:59-66.

[9] PETKO B,MARIOS H,TSOTRAS V J.Time relaxed spatiotemporal trajectory joins[C]//Proceedings of the 13th Annual ACM International Workshop on Geographic Information Systems.New York,USA:ACM Press,2005:182-191.

[10] 李正欣,張鳳鳴,李克武,等.一種支持DTW距離的多元時間序列索引結構[J].軟件學報,2014,25(3):560-575.

[11] KANISHKA B,ZHU Qiang,OZA N C,et al.Fast and flexible multivariate time series subsequence search[C]//Proceedings of 2010 IEEE International Conference on Data Mining.Washington D.C.,USA:IEEE Press,2010:48-57.

[12] EAMONN K,KAUSHIK C,MICHAEL P,et al.Dimensionality reduction for fast similarity search in large time series databases[J].Knowledge and Information Systems,2001,3(3):263-286.

[13] JUNEJO I N,AL A Z.Using SAX representation for human action recognition[J].Journal of Visual Communication and Image Representation,2012,23(6):853-861.

[14] JIN S,EAMONN K.iSAX:disk-aware mining and indexing of massive time series datasets[J].Data Mining and Knowledge Discovery,2009,19(1):24-57.

[15] ZHENG Yu,ZHANG Lizhu,XIE Xing,et al.Mining interesting locations and travel sequences from GPS trajectories[C]//Proceedings of the 18th International Conference on World Wide Web.Washington D.C.,USA:IEEE Press,2009:791-800.