高祎晴 潘 曉* 吳 雷,2

1(石家莊鐵道大學(xué)經(jīng)濟(jì)管理學(xué)院 河北 石家莊 050043)2(燕山大學(xué)信息科學(xué)與工程學(xué)院 河北 秦皇島 066004)

0 引 言

隨著全球定位系統(tǒng)和無(wú)線通信系統(tǒng)的發(fā)展，配備GPS的移動(dòng)設(shè)備不斷涌現(xiàn)(例如車輛導(dǎo)航系統(tǒng)和智能手機(jī))，基于地圖的在線服務(wù)不斷擴(kuò)散(例如Google Maps2和MapQuest3)，軌跡數(shù)據(jù)在當(dāng)下的大數(shù)據(jù)時(shí)代扮演著越來(lái)越重要的角色。常見的軌跡數(shù)據(jù)[5]，除了GPS設(shè)備采集到的人或車輛等運(yùn)動(dòng)物體的移動(dòng)路線以外，還包括傳感器采集到的數(shù)值隨時(shí)間的變化情況，比如某個(gè)監(jiān)控對(duì)象的溫度和濕度變化曲線也可以認(rèn)為是溫度和濕度所構(gòu)成的二維空間中的一條軌跡。因此可以說(shuō)軌跡無(wú)處不在，這些豐富的軌跡數(shù)據(jù)資源也帶來(lái)了對(duì)于軌跡數(shù)據(jù)研究的巨大需求。目前對(duì)于軌跡數(shù)據(jù)的研究，大部分集中于對(duì)于軌跡數(shù)據(jù)的查詢和清洗[14]，受現(xiàn)有存儲(chǔ)能力和計(jì)算能力的限制，非常有必要對(duì)軌跡規(guī)模進(jìn)行縮減。那么當(dāng)軌跡集合中的部分軌跡表現(xiàn)相似，那么便可以刪掉其他相似軌跡只留其一條。因此對(duì)于軌跡相似性查詢的研究成為了一個(gè)熱點(diǎn)問題。即用戶給定一個(gè)相似值，就可以在一個(gè)軌跡數(shù)據(jù)集中查找出滿足用戶要求相似性的軌跡對(duì)，并返回給用戶[9]。

空間相似性查詢是軌跡相似性查詢中較為普遍的一種操作方式，基于空間角度對(duì)軌跡進(jìn)行相似性的衡量，根據(jù)用戶給定的相似性閾值，對(duì)于查詢軌跡集中的軌跡進(jìn)行相似性度量，找出滿足用戶要求的空間相似性閾值的軌跡對(duì)，并且返回給用戶。目前越來(lái)越多的應(yīng)用中出現(xiàn)了地理位置與文本信息交融的現(xiàn)象[8]。一方面,越來(lái)越多的場(chǎng)所,例如商店、飯店、游樂場(chǎng)等,都附加了與其地理位置相關(guān)的文本描述信息;另一方面,文本信息也通過(guò)地名、街道、地址等特征與地理信息相關(guān)聯(lián)。所以如果僅考慮空間這一方面的相似性，可能對(duì)于軌跡相似性衡量較為片面。因此，本文在相似性的度量方面融入了文本信息的考慮，綜合了空間和文本兩方面對(duì)于軌跡的相似性進(jìn)行衡量[12]。例如，當(dāng)A用戶在A省找到與其相似性滿足要求的軌跡t時(shí)，如果軌跡t的用戶出現(xiàn)在B省，恰好A用戶也想去B省，那么當(dāng)給其推薦軌跡時(shí)，就可以參考軌跡t的用戶在B省的軌跡推薦給用戶A。在衡量相似性時(shí)，如果只考慮空間方面也就是距離問題，就顯得不夠嚴(yán)謹(jǐn)[4]。針對(duì)根據(jù)相似性向用戶推薦可行路線，除了考慮距離問題即空間方面外，也應(yīng)該考慮關(guān)鍵字的問題，由此推薦的軌跡能夠更加符合用戶的要求[7]。

以圖1為例，在所調(diào)查的空間中有三條軌跡t1{p11,p12,p13}、t2{p21,p22,p23}、t3{p31,p32,p33}，假設(shè)t1為查詢軌跡，t2、t3為被查詢軌跡。當(dāng)只考慮空間因素時(shí)，可以輕易地得到t2相較t3與t1更為相似。但是當(dāng)考慮空間和文本兩個(gè)方面時(shí)，根據(jù)表1中軌跡的詳細(xì)信息，軌跡t3和t1的相似性要大于軌跡t2與t1的相似性，所以會(huì)更容易滿足用戶的要求。因此，對(duì)于兩條軌跡相似性的度量，除了考慮軌跡間的距離外，還要看關(guān)鍵字的匹配程度。

圖1 軌跡相似性示例

之前的研究者針對(duì)相似性研究方面提出了許多索引技術(shù)和查詢算法[6]。本文通過(guò)對(duì)空間相似性和文本相似性賦予不同的權(quán)重，找到空間方面的邊界值，或者是文本方面的邊界值。根據(jù)這個(gè)邊界值在空間和文本方面進(jìn)行范圍查詢，通過(guò)計(jì)算出來(lái)的范圍去除一些不必要的軌跡，進(jìn)而縮小查詢范圍；同時(shí)也可以提前提取一些確定的結(jié)果集軌跡對(duì)，提升算法的效率。同時(shí)將查詢空間網(wǎng)格化，在網(wǎng)格上進(jìn)行范圍查詢，可以有效提高查詢效率。對(duì)于范圍查詢到的軌跡點(diǎn)進(jìn)行一系列操作，就可以得到滿足用戶要求的結(jié)果[11]。本文貢獻(xiàn)如下：

(1) 在研究軌跡空間相似性的基礎(chǔ)上，增加了對(duì)于文本相似性的考慮。

(2) 通過(guò)空間、文本兩方面因素對(duì)于最終軌跡相似性貢獻(xiàn)權(quán)重的調(diào)整，得出空間和文本相似性的閾值范圍，便于進(jìn)行剪枝。

(3) 對(duì)于空間進(jìn)行網(wǎng)格化處理，在空間網(wǎng)格上根據(jù)滿足要求的范圍進(jìn)行范圍查找，提高效率。

1 相關(guān)工作

文獻(xiàn)[1]研究了道路網(wǎng)絡(luò)中行駛車輛的軌跡相似性查詢(TS-Join)。該文為了實(shí)現(xiàn)在大量的軌跡上高效的軌跡相似性查詢，提出了空間修剪技術(shù)并考慮并行處理能力。文獻(xiàn)[3]解決了用于大量移動(dòng)軌跡的有效相似性查詢問題。與以前方法不同的是，該文認(rèn)為在許多基于位置的服務(wù)應(yīng)用中，軌跡已按原樣在其原生空間中編入了索引。在這個(gè)前提下，在變換的空間中使用專用索引，便于處理常見的時(shí)間和空間方面軌跡相似性查詢。同時(shí)該文介紹一種從經(jīng)典的弗雷歇距離中改編新穎的距離，可以自然地延伸來(lái)支持利用上下限對(duì)于在原生空間中的移動(dòng)對(duì)象數(shù)據(jù)庫(kù)進(jìn)行索引。文獻(xiàn)[2]研究空間關(guān)鍵詞范圍搜索問題，這對(duì)于理解大量數(shù)據(jù)軌跡至關(guān)重要。為了進(jìn)行有效的條件搜索，提出了一個(gè)被稱為IOC-Tree的基于倒排樹和八叉樹技術(shù)的空間網(wǎng)格索引結(jié)構(gòu)對(duì)空間、時(shí)間和文本進(jìn)行有效的剪枝。

本文在空間距離方面使用DTW進(jìn)行計(jì)算，在文本方面用Jaccard系數(shù)進(jìn)行計(jì)算[16],運(yùn)用范圍查詢相關(guān)技術(shù)并通過(guò)一系列定理來(lái)進(jìn)行軌跡相似性計(jì)算，將空間網(wǎng)格化劃分進(jìn)而進(jìn)行范圍查詢剪枝，提高算法的效率。

2 問題的形式化定義

2.1 基本定義

空間軌跡上任意軌跡點(diǎn)對(duì)象均包含地理位置和文本關(guān)鍵字集合，對(duì)于任意一個(gè)軌跡點(diǎn)對(duì)象pi都是包含地理位置和文本關(guān)鍵字集合的軌跡點(diǎn)對(duì)象。每一個(gè)軌跡點(diǎn)對(duì)象的存儲(chǔ)形式pi(x,y,K,Rid)，空間文本信息記為K，K={a1,a2，…,an},ai是文本關(guān)鍵字[10]。x、y分別為軌跡點(diǎn)對(duì)象的經(jīng)緯度，Rid為軌跡點(diǎn)對(duì)象所在的軌跡編號(hào)。對(duì)于軌跡集合中的任意一條軌跡都由n個(gè)軌跡點(diǎn)對(duì)象組成，記為R(p1,p2，…，pn)[13]。

定義1(空間文本軌跡) 空間文本軌跡R由點(diǎn)p1，p2，…，pi，…，pn組成，其中每個(gè)點(diǎn)pi=(xi，yi，tmi)，表示對(duì)象在時(shí)刻tmi位于(xi,yi)位置，其中tm1

如圖1所示，軌跡t1由三個(gè)軌跡點(diǎn)p11、p12、p13組成，因此軌跡t1的長(zhǎng)度是3；在軌跡t1的p11軌跡點(diǎn)那一時(shí)刻，軌跡t2、t3分別位于p21、p31軌跡點(diǎn)處；對(duì)于軌跡t1的關(guān)鍵字集合就是組成軌跡t1的各個(gè)軌跡點(diǎn)所帶的關(guān)鍵字集合，即{coffee，cinema，shop，library，swim}。

給定一條軌跡t,軌跡集合中任意一條軌跡t′與軌跡t的空間相似度、文本相似度和空間文本相似度的定義如下：

定義2(軌跡空間相似度) 任意兩個(gè)軌跡在空間中的相似程度記為SIMs(t，t′)用兩條軌跡間的空間距離表示。設(shè)dmax表示空間中任意兩條軌跡之間的最遠(yuǎn)距離，則空間中任意兩條軌跡t和t′的相似度定義為：

(1)

由式(1)知兩個(gè)軌跡間距離越近，軌跡的空間相似性就越大。由于DTW算法不要求軌跡等長(zhǎng)也可完成軌跡點(diǎn)的動(dòng)態(tài)匹配，因此本文采用DTW計(jì)算任意兩條軌跡之間的空間距離。

定義3(軌跡文本相似度) 任意兩個(gè)軌跡的文本相似性，記為SIMT(t，t′)。即文本集合的相似度，用Jaccard系數(shù)計(jì)算獲得。

(2)

由式(2)可知，兩個(gè)軌跡之間文本集的交集的元素個(gè)數(shù)越多，SIMT(t，t′)的值越大，文本相似性就越大。

定義4(軌跡空間文本相似度) 結(jié)合定義2和定義3，任意兩個(gè)軌跡之間的相似性定義為：

SIM(t,t′)=αSIMS(t,t′)+(1-α)SIMT(t,t′)

(3)

式中：α(α∈[0,1])是一個(gè)可調(diào)節(jié)參數(shù)，用以調(diào)節(jié)計(jì)算空間文本相似性時(shí)空間因素與文本因素之間的相對(duì)重要程度。SIM(t，t′)的值越大，兩條軌跡之間的空間文本相似度就越大。

表2給出圖1中軌跡t1與軌跡t2的空間距離。

表2 軌跡t1和t2之間的DTW距離

由表2可知軌跡t1和軌跡t2之間的距離為1.33，根據(jù)同樣的方法計(jì)算其他軌跡對(duì)之間的距離，可得dmax=5.66，根據(jù)定義1可得軌跡t1和t2的空間相似度為0.77；根據(jù)表1可知t1與t2的文本并集個(gè)數(shù)為7，文本交集個(gè)數(shù)為1，根據(jù)定義3可得t1與t2的軌跡文本相似度為0.143。若給定的α值為0.5，根據(jù)定義4可得最終t1與t2的空間文本相似度為0.46。

本文的問題描述如下：給定一個(gè)軌跡的集合P和一個(gè)閾值ψ，軌跡相似性查詢是從一個(gè)軌跡集合中找出任意兩條軌跡的相似性大于給定閾值ψ的軌跡對(duì)集合。

2.2 相關(guān)定理

由于軌跡數(shù)量十分龐大，為提高查詢效率，需要先將一部分完全不可能存在在結(jié)果集中的軌跡剪枝掉。通過(guò)觀察式(3)發(fā)現(xiàn)，在軌跡相似度閾值確定的情況下，如果兩條軌跡文本相似度(空間相似度)取最大值(即1)，則空間相似度(文本相似度)將取最小值。對(duì)于任意一條軌跡t，如果其他軌跡到該軌跡的空間相似性(文本相似性)小于這個(gè)最小值，則這些軌跡一定不在查詢軌跡t的相似性結(jié)果集中。因此，相似度下限如定理1。

定理1(相似度下限) 給定軌跡空間文本相似度ψ和參數(shù)α，對(duì)于任意一條軌跡t的空間相似度下限和文本相似度下限分別為：

(1) 空間相似度下限LB_SS：對(duì)于軌跡集合中另外任意一條軌跡t′，若兩者的文本相似度取最大值1，則根據(jù)式(4)可以計(jì)算出空間相似度下限，表示為：

LB_SS=(φ+α-1)/α

(4)

由于空間相似度與空間距離成反比。根據(jù)空間相似度下限，可以得到空間兩條軌跡之間最大距離下限，即SD_LBmax。根據(jù)定義2可以計(jì)算出空間兩條軌跡之間最大距離的下限：

SD_LBmax=dmax[(1-φ)/α]

(5)

(2) 文本相似度下限LB_ST：對(duì)于軌跡集合中另外任意一條軌跡t′，若兩者的空間相似度取最大值1，則根據(jù)式(3)可得文本相似度下限，如下：

LB_ST=(φ-α)/(1-α)

(6)

根據(jù)文本相似度下限，設(shè)MINks是軌跡上包含的最小文本數(shù)，可得兩條軌跡之間的最小相同文本數(shù)Wmin：

Wmin=MINks×LB_TT

(7)

由于在軌跡集合中任意兩條軌跡的并集集合數(shù)都大于MINks,因此MINks是兩條軌跡并集集合數(shù)的下限，根據(jù)定義3，在文本相似度取最小值時(shí)，由此下限乘以文本相似度下限，得到相同文本數(shù)是最小值。

若其他任何軌跡t′與t的空間相似度小于LB_SS，則軌跡t′不會(huì)存在于軌跡t的相似軌跡集合中。

證明：對(duì)于空間相似度下限來(lái)講，已知軌跡集合R，用戶要求的空間文本相似度為ψ，給定一條軌跡t，其他任何軌跡t′與t的文本相似度取最大值1；對(duì)于R中任意軌跡對(duì)象Ri,SIMT(Ri,t)≤1，SIMS(Ri,t)

同理可證，對(duì)于給定的一條軌跡t，其他任何軌跡t′與t文本相似性小于LB_TT，則軌跡t′不會(huì)存在于軌跡t的相似軌跡集合中，被剪枝。

同樣，對(duì)于空間相似度下限和文本相似度下限來(lái)說(shuō)，也可以用另一種方式說(shuō)明，即空間最大距離下限和最小相同文本數(shù)，因此同理可以證明，當(dāng)軌跡t′與t的相同文本數(shù)小于最小相同文本數(shù)或者軌跡t′與t的空間距離大于空間軌跡最大距離的下限時(shí)，就將軌跡t′剪枝掉。

證畢。

與之相反，在軌跡相似度閾值確定的情況下，式(4)中如果兩條軌跡文本相似度取最小值(即0)，則空間相似度將取最大值。對(duì)于任意一條軌跡t，如果其他軌跡t′到t的空間相似性大于這個(gè)最大值，則t′一定在t的相似性結(jié)果中。由此，空間相似度上限形式化如定理2。

定理2(空間相似度上限) 給定軌跡相似度閾值ψ，一條軌跡t，如果其他任何軌跡t′與t的空間相似度大于UB_SS，則軌跡t′一定存在于軌跡t的相似軌跡集合中。表示為：

UB_SS=φ/α

(8)

由于空間相似度與空間距離成反比，則根據(jù)定義2，可得空間軌跡最小距離的上限為：

SD_UBmin=dmax(1-φ/α)

(9)

證明：對(duì)于空間相似度上限而言，已知軌跡集合R，用戶要求的空間文本相似度為ψ，給定一條軌跡t，其他任何軌跡t′與t的文本相似度取最大值0；對(duì)于用戶給定軌跡集合R中的任意軌跡對(duì)象Ri，都有SIMT(Ri,t)≥0；因?yàn)閁B_SS是在SIMT(Ri,t)=0情況下計(jì)算出的結(jié)果，所以如果要滿足用戶的相似度φ，不管Ri和t之間的文本相似度值取何值，若SIMS(Ri,t)≥UB_SS，則SIM(Ri,t)=αSIMS(Ri,t)+(1-α)SIMT(Ri,t)≥φ，一定滿足用戶要求。

證畢。

3 算法設(shè)計(jì)

在定理1和定理2中，分別獲得了任意兩條軌跡的空間距離的最大距離下限SD_LBmax和最小距離上限SD_UBmin。根據(jù)最小距離上限SD_UBmin，得到緊湊的最小距離上限。軌跡t′中若有任意點(diǎn)的位置在最大距離下限之外，則軌跡t′被剪枝；軌跡t′上的所有點(diǎn)都在緊湊的最小距離上限內(nèi)，則軌跡t′一定是查詢結(jié)果之一；否則我們通過(guò)逐步上調(diào)SD_UBmin，進(jìn)而調(diào)整緊湊的最小距離上限，對(duì)軌跡t′做進(jìn)一步的驗(yàn)證。同樣算法根據(jù)最大距離下限SD_LBmax，也可得到緊湊的最大距離上限。通過(guò)這個(gè)距離，可對(duì)算法進(jìn)行一些改變，得到另外一種解決問題的方式，算法部分會(huì)給出具體介紹。

3.1 距離介紹

根據(jù)最大距離下限做范圍查詢，可以對(duì)軌跡進(jìn)行一些剪枝。

定理3給定軌跡t和任意一條軌跡t′，若以t中的每一個(gè)位置點(diǎn)為圓心，以SD_LBmax為半徑做范圍查詢，若軌跡t′中存在任意一個(gè)點(diǎn)在范圍查詢之外，則軌跡t′被剪枝。

證明：假設(shè)給定一條查詢軌跡t，有n個(gè)軌跡點(diǎn)；軌跡集合中的任意一條軌跡t′，有m個(gè)軌跡點(diǎn)；此時(shí)定理3所指定的范圍的半徑是SD_LBmax，當(dāng)把兩個(gè)軌跡之間的最大距離上限用在單點(diǎn)上時(shí)，對(duì)于每一個(gè)單點(diǎn)來(lái)說(shuō)，如果在這個(gè)范圍之外，根據(jù)DTW計(jì)算兩條軌跡之間的規(guī)律，經(jīng)過(guò)層層迭代，我們可以知道最終距離總是會(huì)加上一個(gè)SD_LBmax。因此，只要有一個(gè)軌跡點(diǎn)在定理3所指定的范圍之外，那么軌跡t′和軌跡t的距離就會(huì)大于SD_LBmax。在定理1中我們已經(jīng)證明了如果兩條軌跡之間的距離大于SD_LBmax，那么就可以直接被剪枝。

因此只要有一個(gè)軌跡點(diǎn)在定理3所指定的范圍之外，一定不是備選軌跡，將其剪枝掉。

證畢。

(1) 緊湊的最小距離上限：可以將最小距離下限SD_UBmin通過(guò)式(10)變得更緊湊些。

r1=SD_UBmin/n′

(10)

式中：n′是軌跡t和軌跡t′中軌跡長(zhǎng)度較大的軌跡長(zhǎng)度。

定理4給定軌跡t和任意一條軌跡t′，若以t中的每一個(gè)位置點(diǎn)為圓心，以r1為半徑做范圍查詢，若軌跡t′中所有點(diǎn)在范圍查詢之內(nèi)，則軌跡t′一定在軌跡t的結(jié)果集合中。

證明：假設(shè)給定一條查詢軌跡t，有n個(gè)軌跡點(diǎn)；對(duì)于軌跡集合中的任意一條軌跡t′，假設(shè)有m個(gè)軌跡點(diǎn)；當(dāng)n=m時(shí)，定理4所指定的范圍大小為SD_UBmin/n，若軌跡t′上的所有軌跡點(diǎn)都在定理4指定的范圍之內(nèi)，根據(jù)DTW計(jì)算兩條軌跡距離的規(guī)律，對(duì)于最終兩條軌跡之間起決定作用的各個(gè)對(duì)應(yīng)軌跡點(diǎn)之間的距離，由于軌跡t′的所有軌跡點(diǎn)都在軌跡t的定理4所指定的范圍中，所以各個(gè)對(duì)應(yīng)軌跡點(diǎn)之間的距離都是小于SD_UBmin/n，當(dāng)有一個(gè)對(duì)應(yīng)的軌跡點(diǎn)之間的距離小于SD_UBmin/n，再往下推算兩條軌跡之間距離時(shí)，就可以知道在這個(gè)對(duì)應(yīng)下一層是由一個(gè)小于SD_UBmin/n的數(shù)加上下一層的對(duì)應(yīng)軌跡點(diǎn)之間的距離，同樣因?yàn)橄乱粚訉?duì)應(yīng)軌跡點(diǎn)依然是小于SD_UBmin/n，因此經(jīng)過(guò)一層層的推算，可以得到最終軌跡t′到軌跡t的距離小于SD_UBmin/n；當(dāng)m>n時(shí)，此時(shí)定理4指定的范圍大小是SD_UBmin/m，同樣根據(jù)DTW計(jì)算兩條軌跡距離的規(guī)律，兩條軌跡點(diǎn)相同的部分參照兩條軌跡點(diǎn)相同的情況給出，即兩條軌跡點(diǎn)相同的部分計(jì)算出一個(gè)最終值小于SD_UBmin×n/m，考慮較長(zhǎng)軌跡的剩余部分，容易知道最終兩條軌跡之間的距離小于SD_UBmin；當(dāng)mn的證明給出。

因此軌跡上軌跡點(diǎn)完全在定理4指定范圍之內(nèi)的軌跡一定屬于結(jié)果集。

證畢。

(2) 緊湊的最大距離下限：根據(jù)最小距離下限SD_LBmax，可以通過(guò)下式變得更緊湊些。

r2=SD_LBmax/n′

(11)

式中：n′是軌跡t和軌跡t′中軌跡長(zhǎng)度較大的軌跡長(zhǎng)度數(shù)。

定理5給定軌跡t和任意一條軌跡t′，若以t中的每一個(gè)位置點(diǎn)為圓心，以r2為半徑做范圍查詢，若軌跡t′中所有點(diǎn)在范圍查詢之內(nèi)，則軌跡t′一定是軌跡t的備選結(jié)果集合。

證明：參照緊湊的最小距離上限證明方法，同時(shí)根據(jù)DTW計(jì)算規(guī)律可以得到完全在緊湊的最大距離下限所給定的范圍之內(nèi)的，一定是軌跡t的候選結(jié)果軌跡。

證畢。

3.2 基本步驟

算法分為三個(gè)步驟：第一步，剪枝。給定軌跡t，先在軌跡t上每一個(gè)位置點(diǎn)上執(zhí)行定理3所指定的范圍查詢。如果對(duì)于軌跡集合中任意一條軌跡t′，有任意軌跡點(diǎn)位于范圍查詢之外，則軌跡t′被剪枝并形成初步相似軌跡候選集candk。candk中任意的軌跡t′，如果與軌跡t的相同文本數(shù)小于Wmin，則從candk中去除t′。如此，完全在最大范圍下限范圍查詢內(nèi)且滿足最小相同文本數(shù)要求的軌跡組成了相似軌跡候選集cand。第二步，確定結(jié)果集。對(duì)于在軌跡t上每一個(gè)位置點(diǎn)上執(zhí)行定理4指定的范圍查詢，如果對(duì)于cand中的任意軌跡t′的所有位置點(diǎn)都在此范圍內(nèi)，則從cand中去掉t′并返回結(jié)果(t,t′)。第三步，候選結(jié)果集求精。對(duì)于cand中剩余軌跡，調(diào)整定理4所指定的范圍，重新進(jìn)行范圍查詢，如果對(duì)于軌跡t′所有軌跡點(diǎn)在調(diào)整范圍過(guò)程中被訪問到，則從cand中去掉t′并返回(t,t′)；重復(fù)上述操作直至調(diào)整范圍的半徑大于SD_UBmin。若cand中依然存在沒有被完全訪問到的軌跡，取出該軌跡的具體信息，驗(yàn)證其是否為結(jié)果。

下面對(duì)于候選結(jié)構(gòu)求精步驟進(jìn)行詳細(xì)介紹：

r′=(SD_UBmin-sd)/(n-1)

(12)

再次進(jìn)行定理4所指定的范圍查詢，對(duì)于范圍查詢中訪問到的軌跡點(diǎn)，判斷是否為t′上的軌跡點(diǎn)，如果t′上的軌跡點(diǎn)被訪問完全，那么返回(t,t′)；否則計(jì)算訪問到的各個(gè)點(diǎn)與在查詢軌跡t上對(duì)應(yīng)的軌跡點(diǎn)之間的距離，在這些距離中取最大值更新sd，進(jìn)而更新r′，重復(fù)進(jìn)行上述步驟，直至r′大于或者等于SD_UBmin。

如果在上述停止條件出現(xiàn)之后，cand中依然存在軌跡點(diǎn)，那么取出軌跡點(diǎn)所在軌跡的具體信息，計(jì)算其與查詢軌跡t的空間文本相似度判斷是否符合用戶要求，如果符合就納入結(jié)果集，否則就剪枝掉。接下來(lái)用圖2來(lái)解釋我們的驗(yàn)證算法。

圖2 驗(yàn)證例圖

對(duì)于圖2來(lái)說(shuō)，此時(shí)查詢軌跡是由p11、p12、p13組成的軌跡1，驗(yàn)證軌跡是由p21、p22、p23所組成的軌跡2，圖中較小的圈就是我們定理4所指定的范圍；由于p21在定理4所指定的范圍中，所以我們計(jì)算p21到p11之間的距離，根據(jù)這個(gè)距離我們就可以更新查詢軌跡上p12、p13點(diǎn)所對(duì)應(yīng)的范圍，即如圖2所示外面較大的圈。緊接著判斷是否在新一次的范圍查詢中查詢到所有驗(yàn)證軌跡2的軌跡點(diǎn)，可以得到軌跡對(duì)(1,2)在最終的結(jié)果集中。

本文通過(guò)對(duì)于空間(文本)相似度取最大或最小值，從而得到文本(空間)的最小或最大值，在計(jì)算的過(guò)程中，對(duì)于φ和α的取值，會(huì)有大小的沖突。因此在算法中，對(duì)于最小距離上限的計(jì)算，將本文相似性從0的取值更新至當(dāng)前備選軌跡集合中文本相似度的最小值，證明可參考定理2中的證明過(guò)程，結(jié)論依然成立。那么此時(shí)SD_UBmin的計(jì)算公式如下：

(13)

3.3 具體流程

具體算法如下：

Input：用戶要求的相似性φ，參數(shù)值α，軌跡集合R

Output：滿足用戶相似性要求的軌跡集集合A

1. for軌跡集合R中的每一條軌跡Ri

2. 計(jì)算SD_LBmax=dmax[(1-φ)/α]；

3. for在定理3所指定的范圍的每一個(gè)軌跡點(diǎn)對(duì)象Xi

4. 將存入Map map1

5. for在map1中的每一個(gè)軌跡點(diǎn)對(duì)象Xi

6. if(map1中t′的軌跡點(diǎn)個(gè)數(shù)<軌跡t′的個(gè)數(shù))

7. 剪枝掉軌跡t′，形成candk；

8. 計(jì)算LB_ST=(φ-α)/(1-α)Wmin=W*LB_ST

9. for candk中每一個(gè)軌跡點(diǎn)對(duì)象Xi

10. if(Xi所在軌跡t′與Ri的相同文本數(shù)

11. 剪枝掉t′，形成cand；

12. for cand中每一個(gè)軌跡點(diǎn)對(duì)象Xi

13. if(Xi所在軌跡t′的軌跡點(diǎn)數(shù)==查詢軌跡t軌跡點(diǎn)數(shù))

14. 計(jì)算cand中軌跡的文本最小值記為SIMTmin；

15. 計(jì)算SD_UBmin=dTminmax；

16. 計(jì)算r1=SD_UBmin/n′；

17. if(Xi在定理4所指定范圍內(nèi))

18. 將存入Map map2，并從map1中去除該信息；

19. if(map2中Xi對(duì)應(yīng)軌跡編號(hào)t′的軌跡點(diǎn)數(shù)==此時(shí)map1中t′的軌跡點(diǎn)個(gè)數(shù))

20. 將(t,t′)加入結(jié)果集A中；

21. else

22. 進(jìn)一步驗(yàn)證map1,map2中剩余軌跡否為結(jié)果集；

23. else if(Xi所在軌跡的軌跡點(diǎn)對(duì)象個(gè)數(shù)>Ri的軌跡點(diǎn)對(duì)象個(gè)數(shù))

24. 更新SD_UBmin，r1，重復(fù)執(zhí)行11-21行；

25. ReturnA；

對(duì)于用戶給定軌跡集合中的每一條軌跡Ri，首先計(jì)算SD_LBmax,(1-2行)。對(duì)于查詢軌跡t構(gòu)造定理3所指定的范圍，進(jìn)行范圍查詢，對(duì)于訪問到的軌跡點(diǎn)Xi，將存入到map1中(3-4行)。通過(guò)判斷此時(shí)map1中t′的軌跡點(diǎn)個(gè)數(shù)是否等于軌跡t′本身的軌跡長(zhǎng)度，進(jìn)而判斷軌跡t′上是否有軌跡點(diǎn)在查詢范圍之外，如果有，將軌跡t’剪枝掉，形成candk(5-7行)；計(jì)算Wmin，對(duì)于candk中的每一個(gè)軌跡點(diǎn)Xi所在的軌跡t′,判斷Xi軌跡點(diǎn)所在的軌跡與查詢軌跡Ri的相同文本數(shù)是否小于Wmin。如果小于，將Xi軌跡點(diǎn)所在的軌跡剪枝掉,形成cand(8-11行)。

對(duì)于cand中的每一個(gè)軌跡點(diǎn)Xi，判斷Xi所在的軌跡t′的軌跡點(diǎn)個(gè)數(shù)是否等于查詢軌跡的軌跡點(diǎn)個(gè)數(shù)。如果相等，計(jì)算cand中軌跡的文本相似性的最小值SIMTmin和SD_UBmin，之后計(jì)算緊湊的最小距離上限r(nóng)1；對(duì)于查詢軌跡Ri構(gòu)造定理4所指定的范圍，進(jìn)行范圍查詢(13-16行)。判斷Xi軌跡點(diǎn)是否被訪問到。如果被訪問到了，將存入Map map2中，并將相應(yīng)的信息從map1中去除(17-18行)。在Xi已經(jīng)存放到map1或者map2中后，判斷此時(shí)map2中t′的軌跡點(diǎn)個(gè)數(shù)是否等于軌跡t′本身的軌跡點(diǎn)個(gè)數(shù)。如果t′的軌跡點(diǎn)個(gè)數(shù)等于軌跡t′本身的軌跡點(diǎn)個(gè)數(shù)，那么將(t，t′)加入結(jié)果集A中(19-20行)；如果不相等，那么根據(jù)我們的驗(yàn)證算法對(duì)于map1和map2中剩余軌跡進(jìn)行驗(yàn)證(21-22行)。如果Xi所在的軌跡t′的軌跡點(diǎn)個(gè)數(shù)不等于查詢軌跡的軌跡點(diǎn)個(gè)數(shù)，那么重新計(jì)算r1，重復(fù)進(jìn)行11-21行的操作(23-24行)。

在算法中可以將定理3指定的范圍改變?yōu)槎ɡ?指定的范圍，同樣執(zhí)行范圍查詢。但是在進(jìn)行最小文本數(shù)剪枝之前，需要增加一個(gè)驗(yàn)證算法，驗(yàn)證部分在定理5指定范圍內(nèi)的軌跡是否為備選結(jié)果集。該驗(yàn)證算法與上述驗(yàn)證算法相同。

因此，還有另外一種算法去解決這一問題，即把上述算法的2-4行改變?yōu)椋?/p>

2. 計(jì)算SD_LBmax=dmax[(1-φ)/α]

r2=SD_LBmax/n′；

3. for在定理5所指定的范圍的每一個(gè)軌跡點(diǎn)對(duì)象Xi

4. if(Xi所在軌跡的軌跡點(diǎn)對(duì)象個(gè)數(shù)==Ri的軌跡點(diǎn)對(duì)象個(gè)數(shù))

5. 將存入Map map1中

6. if(map1中Xi對(duì)應(yīng)軌跡編號(hào)t′的軌跡點(diǎn)數(shù)=0)

7. 將軌跡t′從map1中剪枝掉；

8. else

9. 驗(yàn)證該軌跡是否備選軌跡；

對(duì)于算法部分，本文提出了兩種解決問題的算法。由于不同的數(shù)據(jù)集會(huì)有不同的數(shù)據(jù)分布，這兩種算法也會(huì)有不同的運(yùn)行效率。同時(shí)對(duì)于相同的數(shù)據(jù)集可能也有運(yùn)行時(shí)間上面的不同。

給定一條查詢軌跡t,有n個(gè)軌跡點(diǎn)。

2. 取map2中的軌跡對(duì)應(yīng)的任一軌跡點(diǎn)對(duì)象Yi

5. 根據(jù)d,對(duì)棧nbs進(jìn)行從大到小排序，取棧頂d記為sd；

8. for(更新范圍內(nèi)的每個(gè)軌跡點(diǎn))

9. 重復(fù)執(zhí)行3-7行；

10. 記錄棧內(nèi)軌跡出現(xiàn)的次數(shù)N,和棧頂軌跡出現(xiàn)的次數(shù)N′;

11. if(棧頂對(duì)應(yīng)的軌跡的軌跡點(diǎn)個(gè)數(shù)==N′)

12. 將棧頂對(duì)應(yīng)的軌跡和查詢軌跡組成軌跡對(duì)加入結(jié)果集中

13. else

14. 從磁盤中取出相應(yīng)的軌跡信息，進(jìn)行計(jì)算驗(yàn)證

15. if(nbs中其他軌跡的軌跡點(diǎn)==N)

16. 將該軌跡和查詢軌跡組成軌跡對(duì)加入結(jié)果集中;

18. else

19. 重復(fù)執(zhí)行4-14行。

4 運(yùn)行示例

給定一個(gè)例子來(lái)詳細(xì)介紹算法的流程。如圖3所示，整個(gè)的矩形空間是本文算法的查詢范圍，其中每個(gè)點(diǎn)都是軌跡點(diǎn)。

圖3 軌跡相似性示例

由圖3可知，在整個(gè)進(jìn)行空間中，有5條軌跡，軌跡的詳細(xì)信息如表3所示。

表3 圖3中軌跡信息

表4為上述運(yùn)行過(guò)程的運(yùn)行示例表。通過(guò)對(duì)于每次訪問區(qū)域的更新，得到備選軌跡集和結(jié)果集的更新，最終得到滿足用戶要求的軌跡對(duì)結(jié)果集合。

表4 運(yùn)行示例表

第一步，給定用戶要求的相似性φ=0.9，α=0.5；給定一條查詢軌跡t1(p11，p12，p13)；計(jì)算出SD_LBmax=3.39；進(jìn)而根據(jù)查詢軌跡的軌跡點(diǎn)得到定理3所指定的區(qū)域，即圖3中大圈所含區(qū)域。根據(jù)訪問空間中軌跡點(diǎn)的位置信息，對(duì)每一個(gè)軌跡點(diǎn)判斷是否在定理3所指定的范圍內(nèi)，經(jīng)過(guò)判斷，此時(shí)map1中有<<5,4>,<2,3>,<4,3>>，構(gòu)成初步的備選軌跡集合candk。

第二步，計(jì)算出Wmin=5，candk中的軌跡5與軌跡1的相同文本數(shù)為2，小于5，剪枝掉軌跡5。此時(shí)map1中有<<2,3>,<4,3>>，構(gòu)成最終的軌跡備選集合。進(jìn)而得到目前軌跡集合中最小的文本相似度為0.83。

第三步，計(jì)算出SD_UBmin=0.54，r1=0.18，進(jìn)而得到定理4所指定的范圍。對(duì)于cand中的每一個(gè)軌跡點(diǎn)，判斷該軌跡點(diǎn)是否在定理4所指定的范圍內(nèi)。以p21為例，根據(jù)p21軌跡點(diǎn)的位置，易知p21不在定理4所在指定的范圍之內(nèi)，不可將該點(diǎn)加入map2，所以map2中存入<<4,1>>。重復(fù)上述的判斷，可得最終map2中為<<4,3>,<2,1>>，map1中為<<2,2>>。根據(jù)map2中的軌跡信息可知，軌跡4在map2中的軌跡點(diǎn)數(shù)等于自身的軌跡點(diǎn)個(gè)數(shù)，即軌跡4完全在定理4所指定的范圍之內(nèi)，因此將(1,4)納入結(jié)果集A。

因此最終滿足用戶要求的結(jié)果集中有{(1,4),(1,2)}。

5 結(jié) 語(yǔ)

隨著移動(dòng)互聯(lián)網(wǎng)的高速發(fā)展和移動(dòng)定位設(shè)備的廣泛普及，基于位置的地理信息服務(wù)逐漸滲透進(jìn)人們生活的方方面面。隨之而來(lái)的對(duì)于基數(shù)龐大的軌跡數(shù)據(jù)研究成為熱點(diǎn)。本文研究軌跡相似性，在一般的空間相似性研究的基礎(chǔ)上，加入了對(duì)于軌跡文本相似性的考慮，使得對(duì)于軌跡相似性的研究更為全面，未來(lái)這一算法可以推廣到旅游路線推薦的應(yīng)用開發(fā)中。