王 飛 龐 悅 周向東 陳海波

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

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

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

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

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

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

0 引 言

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

2 GeoSAX軌跡索引算法

2.1 基于Geohash算法的空間編碼

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

圖1 Geohash算法的空間編碼

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

2.2 GeoSAX表示

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

圖2 GeoSAX索引示意圖

圖3 GeoSAX索引節(jié)點示意圖

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

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

T={,…,,…,}

(1)

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

使用PAA軌跡約減為：

(2)

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

(3)

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

(4)

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

2.3 GeoSAX索引構(gòu)建與相似查詢

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

GeoSAX索引建立算法

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

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

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

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

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

6) if node 為葉子節(jié)點

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

8) node直接插入ts

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

10) 新建一個中間節(jié)點newnode

11) newnode.insert(ts)

12) for each originTS in node

13) newnode.insert(ts)

14) 刪除node節(jié)點

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

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

17) node.insert(ts)

18) else

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

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

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

(5)

2.4 GeoSAX索引在HBase中的存儲設(shè)計

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

表1 GeoSAX索引表設(shè)計

3 實驗設(shè)計

3.1 實驗數(shù)據(jù)和環(huán)境

(1) 航運數(shù)據(jù)

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

(2) 出租車數(shù)據(jù)

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

(3) 實驗環(huán)境

實驗采用由HBase-0.98.13和Hadoop-2.4.0搭建的10個節(jié)點構(gòu)成的HBase集群，其中master節(jié)點內(nèi)存32 GB，slave節(jié)點的內(nèi)存16 GB，每個節(jié)點的硬盤1 TB，操作系統(tǒng)為Ubuntu14.04，網(wǎng)絡(luò)帶寬1 000 Mbit/s。

3.2 實驗設(shè)計

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

3.3 實驗分析

(1) 航運數(shù)據(jù)索引

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

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

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

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

圖5 基數(shù)為256時索引節(jié)點分布情況

圖6 基數(shù)為256時軌跡數(shù)量分布情況

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

(2) 出租車數(shù)據(jù)索引

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

圖7中是對紐約出租車數(shù)據(jù)進行查詢，可以看出，GeoSAX和TRSTJ的查詢表現(xiàn)與航運數(shù)據(jù)是相似的。順序掃描與空間劃分無關(guān)，GeoSAX和TRSTJ均建立了相應(yīng)的索引機制，均比順序掃描要快得多。相同基數(shù)下GeoSAX的查詢性能同樣均比TRSTJ要好，如基數(shù)為8 388 608時GeoSAX查詢速度是TRSTJ的112倍，基數(shù)為16 777 216時，GeoSAX查詢速度是TRSTJ的48倍。航運數(shù)據(jù)軌跡量是百萬級，而軌跡點則有2億多，我們的查詢?nèi)匀豢梢栽诳山邮艿臅r間范圍內(nèi)給出相似查詢結(jié)果。

圖7 出租車數(shù)據(jù)上的查詢性能對比

4 結(jié) 語

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

[1] 龔旭東. 軌跡數(shù)據(jù)相似性查詢及其應(yīng)用研究[D]. 合肥: 中國科學(xué)技術(shù)大學(xué), 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]. 計算機研究與發(fā)展, 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。國家高技術(shù)研究發(fā)展計劃項目(2015AA050203)；國家自然科學(xué)基金項目(61370157)；國家電網(wǎng)公司總部科技項目(52094016000A)。王飛，碩士生，主研領(lǐng)域：軌跡索引，時間序列。龐悅，博士生。周向東，教授。陳海波，高工。

TP3

A

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