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

王 飛 龐 悅 周向東 陳海波

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

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

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

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

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

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

0 引 言

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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ū)間同理，依次對(duì)經(jīng)緯度空間進(jìn)行劃分，得到Geohash編碼。如上海金茂大廈的經(jīng)緯度坐標(biāo)(31.235 253 6 N,121.503 402 3 E)，在二進(jìn)制編碼總位數(shù)為3下得到的二進(jìn)制Geohash編碼是111，在二進(jìn)制編碼總位數(shù)為4下得到的二進(jìn)制Geohash編碼是1110，如圖1所示，其中基數(shù)可以理解為對(duì)空間劃分的細(xì)致程度。

圖1 Geohash算法的空間編碼

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

2.2 GeoSAX表示

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

圖2 GeoSAX索引示意圖

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

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

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

T={,…,,…,}

(1)

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

使用PAA軌跡約減為：

(2)

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

(3)

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

(4)

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

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

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

GeoSAX索引建立算法

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

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

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

4) if當(dāng)前節(jié)點(diǎn)存在GeoSAX表示為G的后繼節(jié)點(diǎn)

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

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

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

8) node直接插入ts

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

10) 新建一個(gè)中間節(jié)點(diǎn)newnode

11) newnode.insert(ts)

12) for each originTS in node

13) newnode.insert(ts)

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

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

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

17) node.insert(ts)

18) else

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

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

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

(5)

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

(3) 實(shí)驗(yàn)環(huán)境

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

3.2 實(shí)驗(yàn)設(shè)計(jì)

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

3.3 實(shí)驗(yàn)分析

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

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

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

從圖4中還可以發(fā)現(xiàn)，相同基數(shù)下GeoSAX的查詢性能均比TRSTJ要好，如基數(shù)為256時(shí)GeoSAX查詢速度是TRSTJ的5倍，基數(shù)為1 024時(shí)，GeoSAX查詢速度是TRSTJ的3倍。這是因?yàn)門RSTJ對(duì)空間采取固定劃分方式，所以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)退化為順序掃描，性能大大降低。以基數(shù)256為例，統(tǒng)計(jì)TRSTJ和GeoSAX單個(gè)索引節(jié)點(diǎn)索引的軌跡數(shù)量的情況。如圖5所示，對(duì)于TRSTJ中索引1～9條軌跡的索引節(jié)點(diǎn)，其數(shù)量占總的索引節(jié)點(diǎn)數(shù)量的72.68%，而GeoSAX占65.10%；TRSTJ中索引1 000條以上軌跡的索引節(jié)點(diǎn)，其數(shù)量占總的索引節(jié)點(diǎn)數(shù)量2.26%，而GeoSAX的分裂閾值為200，不存在索引1 000條以上軌跡的索引節(jié)點(diǎn)。從圖6可以看出，TRSTJ中索引1～9條軌跡的索引節(jié)點(diǎn)，其索引的軌跡數(shù)量占總軌跡數(shù)量的7.69%，而GeoSAX只占1.69%；TRSTJ中索引1 000條以上的索引節(jié)點(diǎn)，其索引的軌跡數(shù)量占總軌跡數(shù)量的68.57%，而GeoSAX的分裂閾值為200，不存在索引1 000條以上軌跡的索引節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

4 結(jié) 語

本文總結(jié)了現(xiàn)有軌跡索引存在的問題，提出一種面向相似查詢的軌跡索引方法GeoSAX。該方法將原始軌跡分成若干等長子段，每個(gè)子段均采用基于Geohash的空間編碼，設(shè)計(jì)了基于HBase存儲(chǔ)的軌跡索引方法GeoSAX。索引不僅節(jié)點(diǎn)之間沒有重疊，還可以根據(jù)數(shù)據(jù)量的大小對(duì)空間動(dòng)態(tài)劃分，并保留了指定精度下的軌跡信息。實(shí)驗(yàn)表明，在相同基數(shù)下GeoSAX搜索性能均優(yōu)于已知的基準(zhǔn)索引方法，在海量數(shù)據(jù)下GeoSAX對(duì)相似軌跡查詢可以快速響應(yīng)。本文提出的方法以僅包含經(jīng)緯度位置信息的二元軌跡情況為例，但是可以很方便的擴(kuò)展到包含速度、方向等其他信息的多元軌跡情況。下一步研究將側(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] 郭黎敏, 高需, 武斌, 等. 基于停留時(shí)間的語義行為模式挖掘[J]. 計(jì)算機(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ā)展計(jì)劃項(xiàng)目(2015AA050203)；國家自然科學(xué)基金項(xiàng)目(61370157)；國家電網(wǎng)公司總部科技項(xiàng)目(52094016000A)。王飛，碩士生，主研領(lǐng)域：軌跡索引，時(shí)間序列。龐悅，博士生。周向東，教授。陳海波，高工。

TP3

A

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