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

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

0 概述

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

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

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

1 相關(guān)工作

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

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

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

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

2 多元軌跡符號(hào)化索引MTSAX

2.1 一元時(shí)間序列索引方法iSAX

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

2.2 多維空間編碼GeoWord

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

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

圖1 GeoWord編碼示意圖

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

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

算法1GeoWord算法

輸出第i個(gè)軌跡點(diǎn)GeoWord編碼

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

2.for j from 1 to m//對(duì)m個(gè)變量依次編碼

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

7.end for

8.return gi//第i個(gè)軌跡點(diǎn)GeoWord編碼

2.3 多元軌跡符號(hào)化表示

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

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

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

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

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

給定多元軌跡:

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

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

(1)

其中,n表示軌跡長(zhǎng)度,m表示軌跡變量的數(shù)目,pij表示第i個(gè)軌跡點(diǎn)的第j個(gè)變量,1≤i≤n,1≤j≤m。

使用PAA軌跡約減為:

(2)

每個(gè)子段用其均值代替為:

(3)

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

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

(4)

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

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

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

算法2MTSAX索引建立

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

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

1.獲取ts的MTSAX表示G

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

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

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

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

6 node直接插入ts

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

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

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

10. 刪除node節(jié)點(diǎn)

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

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

13. node遞歸插入ts

14.else

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

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

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

(5)

圖4 GeoWord對(duì)切分變量的選擇

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

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

(6)

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

3.2 對(duì)比方法

對(duì)比方法如下:

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

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

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

3.3 結(jié)果分析

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

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

查詢性能對(duì)比過(guò)程如下:

1)MTSAX和順序掃描的對(duì)比

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

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

方法基數(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的對(duì)比

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

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

3)MTSAX和ADD的對(duì)比

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

4)MTSAX和LBS的對(duì)比

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

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

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

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

方法基數(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é)束語(yǔ)

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

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