一種基于語義軌跡的相似性連接查詢算法

高祎晴 潘 曉* 吳 雷,2

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

0 引 言

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

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

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

圖1 軌跡相似性示例

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

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

(2) 通過空間、文本兩方面因素對于最終軌跡相似性貢獻權重的調整，得出空間和文本相似性的閾值范圍，便于進行剪枝。

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

1 相關工作

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

本文在空間距離方面使用DTW進行計算，在文本方面用Jaccard系數進行計算[16],運用范圍查詢相關技術并通過一系列定理來進行軌跡相似性計算，將空間網格化劃分進而進行范圍查詢剪枝，提高算法的效率。

2 問題的形式化定義

2.1 基本定義

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

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

如圖1所示，軌跡t1由三個軌跡點p11、p12、p13組成，因此軌跡t1的長度是3；在軌跡t1的p11軌跡點那一時刻，軌跡t2、t3分別位于p21、p31軌跡點處；對于軌跡t1的關鍵字集合就是組成軌跡t1的各個軌跡點所帶的關鍵字集合，即{coffee，cinema，shop，library，swim}。

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

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

(1)

由式(1)知兩個軌跡間距離越近，軌跡的空間相似性就越大。由于DTW算法不要求軌跡等長也可完成軌跡點的動態匹配，因此本文采用DTW計算任意兩條軌跡之間的空間距離。

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

(2)

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

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

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

(3)

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

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

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

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

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

2.2 相關定理

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

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

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

LB_SS=(φ+α-1)/α

(4)

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

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

(5)

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

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

(6)

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

Wmin=MINks×LB_TT

(7)

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

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

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

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

同樣，對于空間相似度下限和文本相似度下限來說，也可以用另一種方式說明，即空間最大距離下限和最小相同文本數，因此同理可以證明，當軌跡t′與t的相同文本數小于最小相同文本數或者軌跡t′與t的空間距離大于空間軌跡最大距離的下限時，就將軌跡t′剪枝掉。

證畢。

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

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

UB_SS=φ/α

(8)

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

SD_UBmin=dmax(1-φ/α)

(9)

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

證畢。

3 算法設計

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

3.1 距離介紹

根據最大距離下限做范圍查詢，可以對軌跡進行一些剪枝。

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

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

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

證畢。

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

r1=SD_UBmin/n′

(10)

式中：n′是軌跡t和軌跡t′中軌跡長度較大的軌跡長度。

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

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

因此軌跡上軌跡點完全在定理4指定范圍之內的軌跡一定屬于結果集。

證畢。

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

r2=SD_LBmax/n′

(11)

式中：n′是軌跡t和軌跡t′中軌跡長度較大的軌跡長度數。

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

證明：參照緊湊的最小距離上限證明方法，同時根據DTW計算規律可以得到完全在緊湊的最大距離下限所給定的范圍之內的，一定是軌跡t的候選結果軌跡。

證畢。

3.2 基本步驟

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

下面對于候選結構求精步驟進行詳細介紹：

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

(12)

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

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

圖2 驗證例圖

對于圖2來說，此時查詢軌跡是由p11、p12、p13組成的軌跡1，驗證軌跡是由p21、p22、p23所組成的軌跡2，圖中較小的圈就是我們定理4所指定的范圍；由于p21在定理4所指定的范圍中，所以我們計算p21到p11之間的距離，根據這個距離我們就可以更新查詢軌跡上p12、p13點所對應的范圍，即如圖2所示外面較大的圈。緊接著判斷是否在新一次的范圍查詢中查詢到所有驗證軌跡2的軌跡點，可以得到軌跡對(1,2)在最終的結果集中。

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

(13)

3.3 具體流程

具體算法如下：

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

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

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

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

3. for在定理3所指定的范圍的每一個軌跡點對象Xi

4. 將存入Map map1

5. for在map1中的每一個軌跡點對象Xi

6. if(map1中t′的軌跡點個數<軌跡t′的個數)

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

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

9. for candk中每一個軌跡點對象Xi

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

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

12. for cand中每一個軌跡點對象Xi

13. if(Xi所在軌跡t′的軌跡點數==查詢軌跡t軌跡點數)

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

15. 計算SD_UBmin=dTminmax；

16. 計算r1=SD_UBmin/n′；

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

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

19. if(map2中Xi對應軌跡編號t′的軌跡點數==此時map1中t′的軌跡點個數)

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

21. else

22. 進一步驗證map1,map2中剩余軌跡否為結果集；

23. else if(Xi所在軌跡的軌跡點對象個數>Ri的軌跡點對象個數)

24. 更新SD_UBmin，r1，重復執行11-21行；

25. ReturnA；

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

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

在算法中可以將定理3指定的范圍改變為定理5指定的范圍，同樣執行范圍查詢。但是在進行最小文本數剪枝之前，需要增加一個驗證算法，驗證部分在定理5指定范圍內的軌跡是否為備選結果集。該驗證算法與上述驗證算法相同。

因此，還有另外一種算法去解決這一問題，即把上述算法的2-4行改變為：

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

r2=SD_LBmax/n′；

3. for在定理5所指定的范圍的每一個軌跡點對象Xi

4. if(Xi所在軌跡的軌跡點對象個數==Ri的軌跡點對象個數)

5. 將存入Map map1中

6. if(map1中Xi對應軌跡編號t′的軌跡點數=0)

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

8. else

9. 驗證該軌跡是否備選軌跡；

對于算法部分，本文提出了兩種解決問題的算法。由于不同的數據集會有不同的數據分布，這兩種算法也會有不同的運行效率。同時對于相同的數據集可能也有運行時間上面的不同。

給定一條查詢軌跡t,有n個軌跡點。

2. 取map2中的軌跡對應的任一軌跡點對象Yi

5. 根據d,對棧nbs進行從大到小排序，取棧頂d記為sd；

8. for(更新范圍內的每個軌跡點)

9. 重復執行3-7行；

10. 記錄棧內軌跡出現的次數N,和棧頂軌跡出現的次數N′;

11. if(棧頂對應的軌跡的軌跡點個數==N′)

12. 將棧頂對應的軌跡和查詢軌跡組成軌跡對加入結果集中

13. else

14. 從磁盤中取出相應的軌跡信息，進行計算驗證

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

16. 將該軌跡和查詢軌跡組成軌跡對加入結果集中;

18. else

19. 重復執行4-14行。

4 運行示例

給定一個例子來詳細介紹算法的流程。如圖3所示，整個的矩形空間是本文算法的查詢范圍，其中每個點都是軌跡點。

圖3 軌跡相似性示例

由圖3可知，在整個進行空間中，有5條軌跡，軌跡的詳細信息如表3所示。

表3 圖3中軌跡信息

表4為上述運行過程的運行示例表。通過對于每次訪問區域的更新，得到備選軌跡集和結果集的更新，最終得到滿足用戶要求的軌跡對結果集合。

表4 運行示例表

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

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

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

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

5 結 語

隨著移動互聯網的高速發展和移動定位設備的廣泛普及，基于位置的地理信息服務逐漸滲透進人們生活的方方面面。隨之而來的對于基數龐大的軌跡數據研究成為熱點。本文研究軌跡相似性，在一般的空間相似性研究的基礎上，加入了對于軌跡文本相似性的考慮，使得對于軌跡相似性的研究更為全面，未來這一算法可以推廣到旅游路線推薦的應用開發中。