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

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

(1.復(fù)旦大學(xué) 計算機科學(xué)技術(shù)學(xué)院,上海 200433; 2.國網(wǎng)上海市電力公司,上海 200122)

0 概述

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

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

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

1 相關(guān)工作

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

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

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

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

2 多元軌跡符號化索引MTSAX

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

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

2.2 多維空間編碼GeoWord

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

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

圖1 GeoWord編碼示意圖

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

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

算法1GeoWord算法

輸出第i個軌跡點GeoWord編碼

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

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

3. 獲取基數(shù)aij對應(yīng)的所有分割點cuts[]

7.end for

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

2.3 多元軌跡符號化表示

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

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

圖2 MTSAX索引結(jié)構(gòu)示意圖

圖3 MTSAX索引節(jié)點空間劃分示意圖

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

給定多元軌跡:

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

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

(1)

其中,n表示軌跡長度,m表示軌跡變量的數(shù)目,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)經(jīng)過GeoWord編碼得到的表示,1≤i≤w,w個GeoWord編碼{g1,g2,…,gi,…,gw}組成一個MTSAX表達。

2.4 MTSAX索引構(gòu)建方法

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

算法2MTSAX索引建立

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

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

1.獲取ts的MTSAX表示G

2.if當(dāng)前索引節(jié)點存在MTSAX表示為G的后繼節(jié)點

3. 獲取MTSAX表示為G的后繼節(jié)點node

4. if node 為葉子節(jié)點

5. if node存儲的軌跡數(shù)量小于節(jié)點分裂閾值th

6 node直接插入ts

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

8. 新建中間節(jié)點newnode

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

10. 刪除node節(jié)點

11. 將newnode作為當(dāng)前節(jié)點的后繼節(jié)點

12. else// node為中間節(jié)點

13. node遞歸插入ts

14.else

15. 新建MTSAX表示為G的葉子節(jié)點newLeaf

16. 葉子節(jié)點newLeaf直接插入ts

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

(5)

圖4 GeoWord對切分變量的選擇

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

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

(6)

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

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集

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

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

3.2 對比方法

對比方法如下:

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

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

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

3.3 結(jié)果分析

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

3.3.1 航運數(shù)據(jù)上的查詢性能對比

查詢性能對比過程如下:

1)MTSAX和順序掃描的對比

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

圖5 航運數(shù)據(jù)上的查詢性能對比

方法基數(shù)為2基數(shù)為4基數(shù)為8基數(shù)為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中可以看出,相同基數(shù)下MTSAX的查詢性能均比TRSTJ要好,如基數(shù)為2時MTSAX查詢速度是TRSTJ的17.6倍,基數(shù)為4時MTSAX查詢速度是TRSTJ的13.9倍。這是TRSTJ對空間采取固定劃分方式,導(dǎo)致TRSTJ索引中數(shù)據(jù)分布很不均勻,極少數(shù)的索引節(jié)點索引了大多數(shù)的軌跡,大多數(shù)的索引節(jié)點只索引了少部分的軌跡。因此,TRSTJ大部分的查詢發(fā)生在極少數(shù)的索引節(jié)點上,而這些索引節(jié)點又索引了大量軌跡,查詢需要掃描節(jié)點上索引的所有軌跡,該查詢已經(jīng)退化為順序掃描,性能大大降低。

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

3)MTSAX和ADD的對比

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

4)MTSAX和LBS的對比

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

3.3.2 GeoLife數(shù)據(jù)集上的查詢性能對比

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

圖6 GeoLife數(shù)據(jù)集上的查詢性能對比

方法基數(shù)為2基數(shù)為4基數(shù)為8基數(shù)為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 結(jié)束語

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

[1] 龔旭東.軌跡數(shù)據(jù)相似性查詢及其應(yīng)用研究[D].合肥:中國科學(xué)技術(shù)大學(xué),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距離的多元時間序列索引結(jié)構(gòu)[J].軟件學(xué)報,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.