基于旅行時間的Top-k軌跡查詢

陳子軍,楊 蕊,劉文遠,劉永山

(燕山大學 信息科學與工程學院,河北 秦皇島 066004)(河北省計算機虛擬技術與系統集成重點實驗室,河北 秦皇島066004)

1 引 言

移動設備和全球定位系統的迅速發展,使得很多基于位置的應用被大量研究,一個突出的應用就是搜索感興趣的軌跡.在空間數據庫中,軌跡查詢一般是以位置點或軌跡為基準來進行查詢,返回距離查詢點地理位置最近或與查詢軌跡最相似的軌跡.本文研究基于位置點的軌跡查詢,在以往的基于位置點的軌跡查詢研究中,都是查找在地理上接近查詢點的軌跡,而忽略了路況和旅行時間.然而,在許多實際應用中,由于路況的不確定性,地理上接近并不一定是最好的選擇,時間信息也是應該考慮的重要因素.文獻[1]研究了基于位置點與到達時間和的軌跡查詢,文中考慮了到達時間和對軌跡查詢的影響,并找出符合要求的軌跡,到達時間和是指所有查詢點到軌跡中相應點的時間之和.這種方法雖然要求到達時間和最小,考慮了時間因素的影響,但是沒有考慮軌跡上點與查詢點之間是否存在軌跡,而且沒有考慮軌跡中從點到其他點所用的時間.

圖1所示,查詢Q={q1,q2,q3},軌跡R中的點為p1,p2,p3,p4,p5,p6,p7,文獻[1]中沒有考慮查詢點和軌跡點的實際到達情況,各個查詢點相對于一條軌跡,只考慮到達時間和最小,所以得到最小的到達時間和為T(R,Q)=t(q1,p2)+t(q2,p4)+t(q3,p6).t(q1,p2),t(q2,p4)和t(q3,p6)分別為各個查詢點到軌跡R中相應點的最小時間,這里,t(qi,pj)是通過pj處的速度和qi和pj之間的歐式距離計算得到的.這種方法沒有考慮軌跡上點與查詢點之間是否存在軌跡,同時也沒考慮p2到p6所用時間.

圖1 最小的到達時間和的實例圖Fig.1 Example of the minimum sum of arrival time

如果一個人在有限的時間去一個陌生的城市旅游,為了節省時間,他不得不以最短的時間訪問他感興趣的地點,其中他感興趣的地點為查詢點,待檢索的軌跡為歷史軌跡.為了解決上述問題,本文提出利用網格索引和倒排表的軌跡查詢方法,并且提出查詢終止策略.

本文的主要貢獻如下:

1)定義了一種基于旅行時間的Top-k軌跡查詢;

2)提出有效的查詢算法和三種終止規則;

3)通過實驗驗證了所提出算法的有效性.

本文在第 2 節介紹相關工作,第 3 節給出問題定義,第 4 節介紹查詢算法,第 5 節給出實驗結果與分析,第 6 節對本論文進行總結.

2 相關工作

隨著地理定位技術和位置服務的進步,與軌跡相關的應用得到迅速的發展.軌跡相關的應用可以分為相似軌跡查詢、基于位置點的k-NN查詢、軌跡聚類[2,3]等.

相似軌跡查詢:在有關軌跡的應用中,一個很重要的操作就是軌跡相似性的查詢,即給定一條軌跡,在軌跡數據庫中查找與之相似度最高的軌跡.軌跡之間的相似度通常是通過相似度函數度量.常用的軌跡相似性查詢方法有動態時間規整算法(DTW)[4],最長公共子序列算法(LCSS)[5],序列編輯距離方法(EDR)[6].文獻[7]結合了點-段距離、預測距離和段-段距離這三種距離度量方法來進行軌跡的相似性查詢.由于問題的性質不同,這些技術不能用于解決本文的問題.

基于位置點的k-NN查詢:給定一組位置點,返回與給定的位置點距離或時間最近的k條軌跡,這k條軌跡按照距離或時間大小遞增排序.文獻[8]研究的kBestConnected Trajectories(k-BCT)查詢,對于給定的一組查詢點,返回連接查詢點的前k條最佳軌跡.文獻[9]中提出了一種k近鄰的軌跡查詢,對于給定的一組查詢點,利用生成候選集-驗證篩選的方法為用戶返回與查詢點的聚合距離最小的k條軌跡.Qi[10]等人設計了一種混合NN-based算法,它的性能高于IKNN和GH/QE算法,解決了NN-based方法內在的不足,即由于獨立運行的多個NN-based而增加的I/O成本和持續維護每個NN搜索的優先隊列而增加的CPU成本.之后他們還提出快速連續位置點的軌跡查詢[11],查詢過程中改變返回軌跡數量k和查詢點的數量m,分別用IKNN算法、GH/QE算法和SRA算法解決這個問題.由于這些工作都是針對距離提出的,而忽略了路況和旅行時間信息,所以這些技術都不能用于解決本文的問題.

基于上述的研究現狀,為了進一步完善現有的基于位置點的k-NN查詢,本文提出一種基于旅行時間的軌跡查詢,為用戶制定旅行計劃提供了參考,方便了用戶的出行.

3 網格索引

空間網格索引的基本思想是將空間區域用虛擬的橫豎線條分割成大小相等的塊,每個塊都成為一個網格(cell)或者單元格,掃描空間區域,將空間區域中的點記錄到所屬網格中,這樣一個網格索引就建成了,網格索引的結構如圖2所示.通過設置網格的邊長,可以改變網格的粒度.

倒排索引是一種根據屬性來查找記錄的索引結構,其中的每一個索引都是一種屬性和包含這種屬性的記錄,因為是逆向的由屬性查找記錄的一種索引結構,所以也稱為倒排表.

圖2 網格索引Fig.2 Gridindex圖3 網格倒排索引Fig.3 Gridinvertedindex

網格的倒排索引結構如圖3所示,其中GridId代表網格編號,本文中用網格左下角的坐標代表網格編號,每個網格對應的Inversionlists是一個軌跡列表,圖3中每條軌跡對應一個由該網格中在該軌跡上的采樣點構成的列表.

4 問題描述

給定一個軌跡數據庫D和一個包含m個位置點的查詢點集合Q={q1,q2,…,qm},空間軌跡R是由運動物體產生的軌跡,通常表示為:(t1,p1),(t2,p2),…,(tN,pN),t1

定義1.給定點p和軌跡R,若R中與p距離小于等于給定閾值α的所有點的序號在R中是連續的,則稱這些點構成的集合為R關于p的匹配點集合,記作P(R,p).如果P(R,p)不為空,則稱R經過p,即R為p的經過軌跡,并且將經過查詢點q的軌跡稱為q的查詢軌跡.

定義2.給定查詢點q∈Q,設T為q的一條查詢軌跡,tmid(T,q)為P(T,q)中所有點的中心時刻,則選取P(T,q)中時間戳與tmid(T,q)最接近的點為q在T上的近似查詢點.如果存在兩個與tmid(T,q)時間差最小的點,則隨機選取其中一個點做為q在T上的近似查詢點.

定義3.給定查詢點q,設T為q的一條查詢軌跡,p為T中的點,若R為p的經過軌跡,則對于T中任意與p相鄰的點p′,都有P(R,p′)?P(R,p)或既不存在P(R,p′)?P(R,p),且也不存在P(R,p)?P(R,p′),則稱R[p]為q的有效軌跡,稱p為R關于q的一個有效點.設Q={q1,q2,…,qm},如果對于任意qi∈Q,都有R[pyi]是q的一條有效軌跡,則稱R[py1,py2,…,pym]為Q的一條完全有效軌跡,其中,pyi為R關于qi的一個有效點.

例1.給定查詢點q,設T為q的查詢軌跡,pi-1,pi,pi+1為T中三個連續的點.

1)如果P(R,pi-1)={b,c},P(R,pi)={a,b,c,d},P(R,pi+1)={a,b,c},則有P(R,pi-1)?P(R,pi),P(R,pi+1)?P(R,pi).

2)如果P(R,pi-1)={c,d,e},P(R,pi)={a,b,c,d},P(R,pi+1)={b,c,d,e},不存在P(R,pi+1)?P(R,pi),且也不存在P(R,pi)?P(R,pi+1),同時不存在P(R,pi-1)?P(R,pi),且不存在P(R,pi)?P(R,pi-1).

根據定義3可知,上述兩種情況均可得出R[pi]為q的有效軌跡,pi為R的有效點.

定義4.單獨到達時間:給定查詢Q={q1,q2,…,qm}和Q的一條完全有效軌跡R[py1,py2,…,pym],設Tx1,Tx2,…,Txm分別為q1,q2,…,qm的查詢軌跡,py1,py2,…,pym分別為Tx1,Tx2,…,Txm中的點,且為R的有效點,即R同時經過py1,py2,…,pym,則查詢點qi通過pyi到R的單獨到達時間t(qi,R,pyi)=|tmid(Txi,qi)-timestamp(pyi)|,其中timestamp(pyi)表示pyi的時間戳.Q中所有查詢點到R[py1,py2,…,pym]的單獨到達時間之和為T(Q,R[py1,py2,…,pym])=t(q1,R,py1)+t(q2,R,py2)+…+t(qm,R,pym).

定義5.通過時間:給定查詢Q={q1,q2,…,qm}和相應的一條完全有效軌跡R[py1,py2,…,pym].tmid(R,pyi)表示P(R,pyi)中所有點的中心時刻,其中i∈[1,m].設tmax=Maxi∈[1,m]tmid(R,pyi),tmin=Mini∈[1,m]tmid(R,pyi),則Q關于R[py1,py2,…,pym]的通過時間可以表示為span(Q,R[py1,py2,…,pym]),即span(Q,R[py1,py2,…,pym])=tmax-tmin.

定義6.旅行時間:給定查詢Q={q1,q2,…,qm}和Q關于R[py1,py2,…,pym]的旅行時間Ttravel(Q,R[py1,py2,…,pym])=T(Q,R[py1,py2,…,pym])+span(Q,R[py1,py2,…,pym]).設R的完全有效軌跡集合為U,則Q關于R的旅行時間Ttravel(Q,R)=MinR[py1,py2,…,pym]∈UTtravel(Q,R[py1,py2,…,pym]).

定義7.基于旅行時間的Top-k軌跡查詢:是指從軌跡數據集D中返回k條軌跡,設這k條軌跡構成的集合為K,則有maxRi∈KTtravel(Q,Ri)≤minRj∈(D-K)Ttravel(Q,Rj).

圖4 完全有效軌跡實例圖Fig.4 Example of complete effective trajectories

例2.由圖4可知,T1,T2,T3分別為q1,q2,q3的查詢軌跡,pz1,pz2,pz3分別為T1,T2,T3的近似查詢點,py1,py2,py3為R的有效點.首先可以計算出匹配點集合P(R,py1)={p3,p4}的中心時刻tmid(R,py1)=(timestamp(p4)-timestamp(p3))12+timestamp(p3),同理,可得tmid(R,py3),所以span(Q,R[py1,py2,py3])=tmid(R,py3)-tmid(R,py1),接著計算出P(T1,q1)的中心時刻tmid(T1,q1)=(timestamp(px2)-timestamp(px1))/2+timestamp(px1),同理,可得tmid(T2,q2)和tmid(T3,q3),因此可求得t(q1,R,py1)=|tmid(T1,q1)-timestamp(py1)|,同理可得t(q2,R,py2)與t(q3,R,py3).由此,可得到{q1,q2,q3}的一條完全有效軌跡R[py1,py2,py3].

5 終止策略

本文主要是對查詢點的查詢軌跡中的點進行搜索并判斷其是否為有效點來檢索完全有效軌跡,在這個過程中,提出了三種終止規則:終止規則1、2和3.

給定查詢點q,設T為q的一條查詢軌跡,p為T中的點,把p的時間戳與tmid(T,q)的時間差記做tl(p,q),UB為當前結果集中軌跡旅行時間的最大值.

終止規則1:給定查詢點q和q的查詢軌跡T中的點p,按著時間差由小到大檢索T中的點,如果tl(p,q)>UB,則不必繼續檢索T中的剩余點.

證明:因為UB為當前結果集中軌跡旅行時間的最大值,如果tl(p,q)>UB,則經過該點及以后點的完全有效軌跡的旅行時間必大于UB,比UB大的完全有效軌跡不必繼續計算,所以不必繼續檢索T中的剩余點.

基于A*算法的思想,給出了終止規則2,下面先定義數據集的理想條件為:

給定查詢點q∈Q,設T為q的任意一條查詢軌跡.

1)T中存在一個時間戳為tmid(T,q)的點q′,且q′與q的位置相同.

2)對于Q的任意一條完全有效軌跡R[ ],若T中的點p為軌跡R的一個有效點,則R中存在一個時間戳為tmid(R,p)的點p′與p的位置相同.

3)數據集中對象的移動速度不大于最大速度v.

由此可見,若滿足理想條件,對于軌跡R,至多存在一條完全有效軌跡.

終止規則2:假設數據集滿足理想條件,給定查詢點qi和qi的查詢軌跡T中的點p,設p到其他查詢點的距離的最大值為distp,按著時間差由小到大檢索T中的點,如果有tl(p,qi)+distp/v>UB,則不必繼續檢索T中的剩余點.

證明:下面以三個查詢點為例進行證明,對于多個查詢點的證明類似.

設Q={q1,q2,q3},p1、p2和p3分別為查詢點q1、q2和q3的查詢軌跡上的點.

1)p1為兩側查詢點的查詢軌跡中的點.

如圖5(a)所示,dist(p1,q2)UB,則有t(p1,q1′)+t(p1′,p3′)+t(p3,q3′)>UB,那么必有Ttravel(Q,R[p1,p2,p3])=t(p1,q1′)+t(p2,q2′)+t(p3,q3′)+t(p1′,p3′)>UB,所以,不必繼續檢索T中的剩余點.

2)p1不是兩側查詢點的查詢軌跡中的點.

如圖5(b)所示,p1為q1的查詢軌跡中的點.設dist(p1,q2)>dist(p1,q3),所以p1到其他查詢點的距離的最大值為dist(p1,q2).證明與前面類似.

由于數據集一般情況下不能滿足理想條件,在數據集不滿足理想條件時也可以采用終止規則2,此時的查詢結果為近似結果,因此下面給出終止規則3.

終止規則3:數據集不滿足理想條件時,給定查詢點qi和qi的查詢軌跡T上的點p,按著時間差由小到大檢索T上的點,設p到其他查詢點的距離的最大值為dist(p,qj),如果有tl(p,qi)+dist(p,qj)/v>UB,則不再檢索T上的剩余點,查詢結果為近似結果.

圖5 終止規則2證明實例圖Fig.5 Example of the proof of termination rule 2

6 查詢算法

6.1 數據結構

H(q):為查詢點q的優先隊列,所存儲的點e的數據結構為(T,q,flag,key),T為e所屬的查詢軌跡,q為T所經過的查詢點,flag為擴展標識,表示時間戳的變化方向,flag為0表示向時間戳減小的方向變化,flag為1表示向時間戳增大的方向變化,設e的時間戳與中心時刻tmid(T,q)之差為tl(e,q),e到達其它查詢點的最小距離的最大值diste=Maxqi∈Q-{q}dist (e,qi).若采用終止規則1,則key=tl(e,q),若采用終止規則3,key=tl(e,q)+diste/v.key值越小,則優先級越高.

M:為全局優先隊列,數據結構與H(q)相同.

LL[q]:為q的所有有效軌跡的集合,有效軌跡的數據結構為(ID,E[q]),ID表示有效軌跡的編號,E[q]為有效軌跡在q的查詢軌跡中的有效點構成的集合.

P[q,T,flag]:記錄q的查詢軌跡T中上一次從M中出隊列的點,flag表示該點的時間戳的變化方向.

LE[e]:如果e為有效點,LE[e]為e.q利用e得到的有效軌跡集合,否則,LE[e]為空.

CList:數據結構為R(ID,E[q1],…,E[q|Q|]),ID表示R的編號,對于?q∈Q,都有E[q]為R在q的查詢軌跡中的有效點構成的集合,由R(ID,E[q1],…,E[q|Q|])可組合得到R的一條或多條完全有效軌跡,稱R(ID,E[q1],…,E[q|Q|])為一個完全有效軌跡源,CList存儲完全有效軌跡源的集合.

G:存儲旅行時間最優的k條軌跡R(ID,Emin,Tmin),ID表示R的編號,在CList中找到R,對R.E[q1],…,R.E[q|Q|]進行組合得到R的完全有效軌跡集合U,利用U計算Ttravel(Q,R),R.Tmin存儲Ttravel(Q,R)的值,R.Emin存儲旅行時間為Ttravel(Q,R)的完全有效軌跡的有效點集合(如果不唯一,隨機取其中一個).

NewEP:用于存儲更新的完全有效軌跡源,數據結構與CList相同,對于CList中的R(ID,E[q1],…,E[q|Q|]),如果R.E[qi]增加了一個有效點e,把R(ID,E[q1],…,E[q|Q|])復制到NewEP中,并修改NewEP中的R.E[qi]={e}.

NewET:用于存儲新的完全有效軌跡源,數據結構與CList相同,對于LL[qi]中增加的一條記錄R,如果LL[q1],…,LL[q|Q|]中都包含R.ID,將R(ID,E[q1],…,E[q|Q|])復制到NewET中,同時從LL[q1],…,LL[q|Q|]中刪除記錄R.

CListall:用于存儲NewEP與NewET的并集,用于計算新的完全有效軌跡的旅行時間.

6.2 算法描述

函數1.L(p)

參數:p為軌跡上的點.

返回:經過點p的軌跡集合.

算法1.TravelTimeSearch

輸入:查詢點Q={q1,q2,…,qm},軌跡數據庫D,返回軌跡個數k,最大速度v;

輸出:結果集G;

1)CList=φ;G=φ;UB=+∞;

2)M←NewPriorityQueue();//M為全局優先隊列.

3)for eachqinQ

4)H(q)←NewPriorityQueue();LL[q]= NULL;

5) for eachTin L(q)//函數1

6) 找到q在T中的近似查詢點q′和它在T中的前驅和后繼q0、q1;

7) LE[q′]←EPointtra(q0,q′);temp= LE[q′];

8) LE[q′]←EPointtra(q1,q′);

9) LE[q′]= LE[q′]∩temp;

10) if LE[q′] is not empty

11) G=ETProcess(LE[q′],LL[ ],CList,G,UB); // 調用算法2

12)q0.q=q;q0.key=tl(q0,q)+distq0/v;q0.flag=0;q0入隊列H(q);

13)q1.q=q;q1.key=tl(q1,q)+distq1/v;q1.flag=1;q1入隊列H(q);

14)M.Enqueue(H(q).Dequeue());

15) P[q,T,0]=P[q,T,1]=NULL;

16)WhileMis not empty

17)e=M.Dequeue();

18) ife.key>UBbreak;

19) else

20)e′=P[e.q,e.T,e.flag];P[e.q,e.T,e.flag]=e;LE[e′]=NULL;

21) ife′!=NULL

22) LE[e′]=EPointtra(e,e′);//算法3

23) if LE[e′] is not empty

24) G=ETProcess(LE[e′],LL[ ],CList,G,UB); // 調用算法2

25) ife.flag==0

26) 在e.T中找到e的前驅點e′;e′.q=e.q;e′.key=t(e′,e′.q)+diste′/v;e′.flag=0;e′入隊列H(e.q);

27) else ife.flag==1

28) 在e.T中找到e的后繼點e′;e′.q=e.q;e′.key=t(e′,e′.q)+diste′/v;e′.flag=1;e′入隊列H(e.q);

29)M.Enqueue(H(e.q).Dequeue());

30)G=LastPoints(CList,LL[ ],G,UB,P[ ]);//算法6

31)return G;

算法1描述了查詢的整個過程.第1-15行為搜索前的準備工作.第5-15行,處理q的每條查詢軌跡,第5行的L(q)是利用網格索引計算的，設網格邊長為α.第7-9行,查找T的近似查詢點q′的有效軌跡集合LE[q′].第16-29行,重復處理從M中出隊列的點,直到滿足終止條件3,循環結束.第20行,取出當前要判斷的點e′,并存儲點e以便于下次進行有效點的判斷.第21-22行,如果e′不為空,調用算法3,如果e′為有效點,返回e′.q的有效軌跡集合LE[e′].第23-24行,通過算法2對LE[e′]中的軌跡進行處理來獲取結果集G.第25-28行,根據e的擴展標識檢索入隊列的點.第30行,調用算法6對所有查詢軌跡檢索到的最后一個點進行處理.

算法2.ETProcess

輸入:LE[e],&LL[ ],&CList,&G;&UB;

輸出:結果集G;

1)NewEP=φ;NewET=φ;CListall=φ;TID[e]=φ;

2)for eachRin LE[e]

3) if LL[e.q]中存在R′,使得R′.ID==R.ID

4) 將e插入到LL[e.q]的R.E[e.q]中;

5) else LL[e.q]←(R.ID,{e});

6) if CList中存在R′,使得R′.ID==R.ID

7) 將e插入到CList的R′.E[e.q]中;

8) tempt=CList.get(R′.ID);

9) 用{e}替換tempt中的R′.E[e.q];

10) NewEP←tempt;

11) else

12) TID[e]←R.ID;

13)if TID[e]!=φ

14) NewET←GetCET(LL[ ],TID[e],e.q);//算法4

15)CList=CList∪NewET;

16)CListall←NewEP∪NewET;

17)G←CUpdate(CListall,G);//算法5

18)for eachqinQ

19) for eachR(ID,E[q1],…,E[q|Q|])in NewET

20) for each(ID,E[q])in LL[q]

21) if ID==R.ID

22) 從LL[q]中刪除(ID,E[q]);

23)return G;

算法2描述了更新CList、LL[ ]和G的過程.LL[ ]為當前各個查詢點的有效軌跡集合.第1行,TID[e]用于存儲LE[e]中不在CList中的有效軌跡的ID的集合,第3-5行,利用R和e更新LL[e.q].第6-10行,處理新增加有效點e的情況,第13-14行,調用算法4求解新增的完全有效軌跡源,第17行,調用算法5利用CListall對G進行更新.第18-22行,更新LL[ ],以減少重復計算.

算法3.EPointtra

輸入:e,e′;

輸出:LE[e′];

1)LE[e′]=φ;

2)for eachRin L(e′)

3) if 存在e′不是R有效點的標記 continue;

4) else if P(e′,R)?P(e,R) continue;

5) else LE[e′]←R;

6) if P(e,R)?P(e′,R)

7) 做出e不是R的有效點的標記;

8)return LE[e′];

算法3為求解e′.q利用e′得到的有效軌跡集合LE[e′].對于e與訪問過的相鄰點e′,通過比較R關于e和e′的匹配點集合,即P(e,R)和P(e′,R),來判斷e′是否為有效點.當第6行條件為真時,根據定義3可知,e不是R的有效點,否則只需要利用將來在e之后出現點與e比較即可判斷e是否為有效點,從而節省了計算時間.

算法4.GetCET

輸入:&LL[ ];TID[e];e.q;

輸出:NewET;

1)NewET=φ;

2)for eachqinQ-{e.q}

3) for eachRin LL[q]

4) s[q]←R.ID;//s[q]是q的有效軌跡ID的集合

5)S←∩q∈Q-{e.q}s[q];

6)S←S∩TID[e];//S用于存放新增完全有效軌跡ID的集合

7)for each ID in S

8) 初始化完全有效軌跡源R(ID,E[q1],…,E[q|Q|]);

9)R.ID=ID;R.E[e.q]={e};

10) for eachqinQ-{e.q}

11) 從LL[q]取出編號為ID的有效點集合E[q];

12)R.E[q]=E[q];

13) NewET←R(ID,E[q1],…,E[q|Q|]);

14)return NewET;

算法4為求解新增的完全有效軌跡源的過程.第5-6行,求出新增完全有效軌跡ID的集合S,第7-13行,利用LL[ ]和TID[e]得到新增完全有效軌跡源.

算法5.CUpdate

輸入:CListall;G;

輸出:G;

1)for eachRin CListall

2) 從R.E[q1],R.E[q2],…,R.E[q|Q|]中分別取一個有效點構成一條R的完全有效軌跡,設通過這種方式得到的R的完全有效軌跡集合為U,t=MinR[py1,py2,…,pym]∈UTtravel(Q,R[py1,py2,…,py|Q|]),其中pyi∈R.E[qi],R[ ]=argmin t(如果R[]不唯一,隨機取其中一個即可);

3) ifR∈G

4) ift

5) 用R[ ]和t更新G;

6) if G.size()==k

8) else ift

9) 用R[ ]和t更新G;

10) if G.size()==k

12)return G;

算法5利用CListall中的完全有效軌跡源更新結果G.第3-11行更新G和UB,第9行若G中軌跡個數小于k直接將R添加到G中,否則刪除G中的第k個結果后,將R插入G中.

算法6.LastPoints

輸入:&CList,&LL[ ],&G,UB, &P[ ];

輸出:G;

1)for eachqinQ

2) for eachTin L(q)

3) for(intflag=0;flag<=1;flag++)

4)e′= P[q,T,flag];

5) 在T中按flag找到e′的前驅或后繼點e;//flag=0表示前驅,否則后繼

6) LE[e′]= NULL; LE[e′]←EPointtra(e,e′);

7) if LE[e′] is not empty

8) G=ETProcess(LE[e′],LL[ ],CList,G,UB); // 調用算法2

9)return G;

算法6為對所有查詢軌跡檢索到的最后一個點進行處理.第3行,對于每個查詢點q的每條查詢軌跡T,都有flag=0和flag=1的兩個變量P[q,T,flag],第7-8行,如果LE[e′]不為空,調用算法2對G進行更新.

圖6為一個完整的查詢過程實例.

圖6 查詢實例圖Fig.6 Example of query

如圖6所示,選取查詢點Q={q1(p13),q2(p33)},設k=1.根據基于網格的倒排索引結構,可以得到q1的查詢軌跡為R1和R2,其近似查詢點分別為p13和p23,q2的查詢軌跡為R1和R3,近似查詢點分別為p16和p33.通過前驅點和后繼點可以確定p13是R1和R2的有效點,同理,可以判斷p23同時為R1和R2的有效點,p33為R1的有效點,p33和p16均為R3的有效點.由LL[q1]中的R1.E[q1]={p13,p23}與LL[q2]中R1.E[q2]={p33}可以得CListall=CList=NewET={R1(R1.ID,E[q1],E[q2])},其中E[q1]={p13,p23},E[q2]={p33},利用CListall可得完全有效軌跡R1[p13,p33]和R1[p23,p33],可以求得R1的Tmin及相應的有效點集合Emin={p13,p33},更新G,將R1.ID、Tmin和Emin添加到G,同時從LL[q1]和LL[q2]中分別刪除(R1.ID,R1.E[q1])和(R1.ID,R1.E[q2]),在準備階段,各個查詢點的單獨優先隊列的初始狀態為H(q1)={p14,p12,p22,p24},H(q2)={p32,p34,p15,p17},再由H(q1)和H(q2)出隊列點可構成M={p14,p32}.

表1中H(q)中黑色粗體點代表q的查詢軌跡中key值最小的點,M中黑色粗體點代表所有查詢軌跡中key值最小的點,標有下劃線的點為新進入優先隊列的點,標有刪除線的記錄為要刪除的記錄.表1對循環過程進行了描述.

Iteration1:M中點p14(flag=1)出隊列,因為P[q1,R1,1]為空,將p14賦值給P[q1,R1,1].p14的后繼點p15進入H(q1),同時從H(q1)中出隊列p12(flag=0)進入M中.

Iteration2、3處理過程與Iteration1相似,詳見表1.

Iteration4:M中點p35出隊列,p35的后繼點p36進入H(q2),同時從H(q2)出隊列p17進入M.由于P[q2,R3,1]=p34,因此通過判斷可得p34為R1的有效點,LE[p34]={R1},由于R1∈CList,因此有CListall=NewEP={R1(ID,{p13,p23}, {p34})},計算CListall中新的完全有效軌跡R1[p13,p34]和R1[p23,p34]的旅行時間,由算法5得t=Ttravel(Q,R1[p23,p34]),t小于G中R1.Tmin,更新G,同時更新CList后,可得CList={R1(ID,{p13,p23},{p33,p34})},重復直到符合終止規則3,搜索結束,返回結果.

表1 循環過程
Table 1 Cycle process

循環MH(q1)H(q2)LL[q1]LL[q2]CList初始p14(1),p32(0)p14(1),p12(0),p22(0),p24(1)p32(0),p34(1),p15(0),p17(1)(R1.ID,{p13,p23}),(R2.ID,{p13,p23})(R1.ID,{p33}),(R3.ID,{p33,p16})R1(ID,{p13,p23},{p33})1p14(1),p32(0),p12(0)p12(0),p22(0),p15(1),p24(1)p34(1),p17(1),p15(0)(R2.ID,{p13,p23})(R3.ID,{p33,p16})R1(ID,{p13,p23},{p33})2p32(0),p34(1),p12(0)p22(0),p15(1),p24(1)p34(1),p17(1),p15(0),p31(0)(R2.ID,{p13,p23})(R3.ID,{p33,p16})R1(ID,{p13,p23},{p33})3p34(1),p35(1),p12(0)p22(0),p15(1),p24(1)p35(1),p17(1),p15(0),p31(0)(R2.ID,{p13,p23})(R3.ID,{p33,p16})R1(ID,{p13,p23},{p33})4p35(1),p12(0),p17(1)p22(0),p15(1),p24(1)p17(1),p15(0),p31(0),p36(1)(R2.ID,{p13,p23})(R3.ID,{p33,p16})R1(ID,{p13,p23},{p33,p34})……

7 實 驗

7.1 實驗數據集

該實驗使用數據集T-Drive Data[12,13],對終止規則1和3的性能進行了比較.該數據集包含了2008年2月2日-2月8日期間內北京境內8911輛出租車的GPS軌跡,每條GPS軌跡是由一系列帶時間戳的點組成,點的信息包括出租車的ID、經度、緯度和時間信息.為了使得計算更加準確,對數據集進行預處理,由于在原始軌跡中可能會存在頻繁停頓的情況,為了使得計算更加精確,本文將停頓時間超過5分鐘的軌跡從停頓處分開,這樣可以根據停頓點將一條軌跡拆分成若干條新軌跡來進行搜索.此外,由于數據集中可能存在同一條軌跡中點數據記錄重復或超速情況,因此,如果一條軌跡中相鄰點的直線速度大于120km/h,則刪除該軌跡.重組和篩選后得到13001條GPS軌跡(2068294個點)用于實驗.后面的所有實驗數據都是通過對50組實驗的實驗結果取平均值得到,每組實驗從數據集中隨機選取|Q|個查詢點.

通過運行時間來評價算法的性能.在實驗中,改變k(返回軌跡數量)、|Q|(查詢點個數)、|Grid|(網格大小)和最大速度v,比較不同條件下終止規則1(Ter1)和3(Ter3)的性能.

7.2 網格大小|Grid|對運行時間和旅行時間的影響

如圖7(a)所示為應用Ter1時|Grid|的變化對運行時間的影響,實驗中設|Q|=3,k=2.由圖7(a)可以看出,隨著|Grid|的增大,運行時間呈現上升趨勢,|Grid|的增加使得網格變大,網格中的點也隨之增多,查詢點的查詢軌跡數量增多,要判斷的點也會增多,所以運行時間變長.

圖7 調節|Grid|的影響Fig.7 Impact of |Grid|

如圖7(b)所示為應用Ter1時|Grid|的變化對旅行時間的影響,每組實驗的旅行時間是指運行結束后,結果集中軌跡的旅行時間的平均值,實驗中設|Q|=3,k=2.隨著|Grid|的增大,旅行時間呈現下降趨勢,|Grid|的增加使得網格變大,軌跡相交的約束條件變弱,查詢點的有效軌跡增多了,產生了旅行時間更小的完全有效軌跡.

綜上,選取|Grid|=30作為實驗中網格大小的值.

7.3 最大速度v對運行時間和準確率的影響

如圖8(a)所示為v的變化對運行時間的影響.應用Ter3時,實驗中設|Q|=3,k=2,|Grid|=30,由圖8(a)可以看出,隨著v的增大,運行時間呈現上升趨勢,v的增加增大了終止條件3中的UB的值,查詢更不容易滿足終止條件3,所以運行時間變長.

圖8 調節v的影響Fig.8 Impact of v

在給定網格大小的情況下,應用Ter1得到的結果是精確的,通過對比測試Ter3的準確率.在網格大小相同的情況下,設利用Ter1得到50組查詢結果的集合為A,利用Ter3得到50組查詢結果的集合為B,因此,準確率為|A∩B|/50.隨著最大速度v的變化,準確率也會受到影響.由圖8(b)可以看出,當v>=50時,準確率基本為100%.

綜上,當v=50時,準確率和運行時間最合適,所以應用Ter3時,選取v=50作為實驗中最大速度的值.

7.4 查詢點個數|Q|對運行時間的影響

如圖9所示為應用Ter1和Ter3時|Q|的變化對運行時間的影響,應用Ter1時,實驗中設|Grid|=30,k=2;應用Ter3時,實驗中設|Grid|=30,k=2,v=50.由圖9可以看出,隨著|Q|的增大,整體呈現上升趨勢,因為|Q|的增加意味著查詢點個數的增多,此時查詢范圍變大,運行時間變長.

圖9|Q|對運行時間的影響Fig.9 Impactof|Q|圖10k對運行時間的影響Fig.10 Impactofk

7.5 軌跡的數量k對運行時間的影響

如圖10所示為應用Ter1和Ter3時k的變化對運行時間的影響,應用Ter1和Ter3時,實驗中|Grid|、k和v與7.4中相同.由圖10可以看出,隨著k的增大,整體呈現上升趨勢,因為k的增加意味著返回軌跡個數的增加,即計算量的增加,運行時間變長.

由圖9和圖10可知,應用Ter3的運行時間少于應用Ter1的運行時間.

8 結 論

本文研究了一種新的軌跡查詢方法,即基于旅行時間的top-k軌跡查詢,旨在獲取旅行時間最短的前k條軌跡.該方法有以下幾點優勢:1)考慮了兩點之間是否存在軌跡;2)考慮軌跡中從點到其他點所用時間;3)提出了有效的查詢算法,并提出了三種終止規則,提高了查詢速度.實驗表明,該算法具有良好的運行效率.

由于實驗是在軌跡數據集上進行的,軌跡的相交是利用采樣點判斷的,軌跡數據采集時采樣率的選取和實驗中網格的選取都會影響軌跡的相交情況的判斷,因此,本文的下一步工作是在路網已知的情況下,利用路網信息判斷軌跡的相交情況.