基于旅行時(shí)間的Top-k軌跡查詢

2019-07-09 11:43:50陳子軍劉文遠(yuǎn)劉永山

小型微型計(jì)算機(jī)系統(tǒng) 2019年7期

陳子軍,楊蕊,劉文遠(yuǎn),劉永山

(燕山大學(xué) 信息科學(xué)與工程學(xué)院,河北秦皇島 066004)(河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室,河北秦皇島066004)

1 引言

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

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

圖1 最小的到達(dá)時(shí)間和的實(shí)例圖Fig.1 Example of the minimum sum of arrival time

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

本文的主要貢獻(xiàn)如下:

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

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

3)通過實(shí)驗(yàn)驗(yàn)證了所提出算法的有效性.

本文在第 2 節(jié)介紹相關(guān)工作,第 3 節(jié)給出問題定義,第 4 節(jié)介紹查詢算法,第 5 節(jié)給出實(shí)驗(yàn)結(jié)果與分析,第 6 節(jié)對(duì)本論文進(jìn)行總結(jié).

2 相關(guān)工作

隨著地理定位技術(shù)和位置服務(wù)的進(jìn)步,與軌跡相關(guān)的應(yīng)用得到迅速的發(fā)展.軌跡相關(guān)的應(yīng)用可以分為相似軌跡查詢、基于位置點(diǎn)的k-NN查詢、軌跡聚類[2,3]等.

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

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

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

3 網(wǎng)格索引

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

倒排索引是一種根據(jù)屬性來查找記錄的索引結(jié)構(gòu),其中的每一個(gè)索引都是一種屬性和包含這種屬性的記錄,因?yàn)槭悄嫦虻挠蓪傩圆檎矣涗浀囊环N索引結(jié)構(gòu),所以也稱為倒排表.

圖2 網(wǎng)格索引Fig.2 Gridindex圖3 網(wǎng)格倒排索引Fig.3 Gridinvertedindex

網(wǎng)格的倒排索引結(jié)構(gòu)如圖3所示,其中GridId代表網(wǎng)格編號(hào),本文中用網(wǎng)格左下角的坐標(biāo)代表網(wǎng)格編號(hào),每個(gè)網(wǎng)格對(duì)應(yīng)的Inversionlists是一個(gè)軌跡列表,圖3中每條軌跡對(duì)應(yīng)一個(gè)由該網(wǎng)格中在該軌跡上的采樣點(diǎn)構(gòu)成的列表.

4 問題描述

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

定義1.給定點(diǎn)p和軌跡R,若R中與p距離小于等于給定閾值α的所有點(diǎn)的序號(hào)在R中是連續(xù)的,則稱這些點(diǎn)構(gòu)成的集合為R關(guān)于p的匹配點(diǎn)集合,記作P(R,p).如果P(R,p)不為空,則稱R經(jīng)過p,即R為p的經(jīng)過軌跡,并且將經(jīng)過查詢點(diǎn)q的軌跡稱為q的查詢軌跡.

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

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

例1.給定查詢點(diǎn)q,設(shè)T為q的查詢軌跡,pi-1,pi,pi+1為T中三個(gè)連續(xù)的點(diǎn).

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),同時(shí)不存在P(R,pi-1)?P(R,pi),且不存在P(R,pi)?P(R,pi-1).

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

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

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

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

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

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

例2.由圖4可知,T1,T2,T3分別為q1,q2,q3的查詢軌跡,pz1,pz2,pz3分別為T1,T2,T3的近似查詢點(diǎn),py1,py2,py3為R的有效點(diǎn).首先可以計(jì)算出匹配點(diǎn)集合P(R,py1)={p3,p4}的中心時(shí)刻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),接著計(jì)算出P(T1,q1)的中心時(shí)刻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 終止策略

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

給定查詢點(diǎn)q,設(shè)T為q的一條查詢軌跡,p為T中的點(diǎn),把p的時(shí)間戳與tmid(T,q)的時(shí)間差記做tl(p,q),UB為當(dāng)前結(jié)果集中軌跡旅行時(shí)間的最大值.

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

證明:因?yàn)閁B為當(dāng)前結(jié)果集中軌跡旅行時(shí)間的最大值,如果tl(p,q)>UB,則經(jīng)過該點(diǎn)及以后點(diǎn)的完全有效軌跡的旅行時(shí)間必大于UB,比UB大的完全有效軌跡不必繼續(xù)計(jì)算,所以不必繼續(xù)檢索T中的剩余點(diǎn).

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

給定查詢點(diǎn)q∈Q,設(shè)T為q的任意一條查詢軌跡.

1)T中存在一個(gè)時(shí)間戳為tmid(T,q)的點(diǎn)q′,且q′與q的位置相同.

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

3)數(shù)據(jù)集中對(duì)象的移動(dòng)速度不大于最大速度v.

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

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

證明:下面以三個(gè)查詢點(diǎn)為例進(jìn)行證明,對(duì)于多個(gè)查詢點(diǎn)的證明類似.

設(shè)Q={q1,q2,q3},p1、p2和p3分別為查詢點(diǎn)q1、q2和q3的查詢軌跡上的點(diǎn).

1)p1為兩側(cè)查詢點(diǎn)的查詢軌跡中的點(diǎn).

如圖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,所以,不必繼續(xù)檢索T中的剩余點(diǎn).

2)p1不是兩側(cè)查詢點(diǎn)的查詢軌跡中的點(diǎn).

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

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

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

圖5 終止規(guī)則2證明實(shí)例圖Fig.5 Example of the proof of termination rule 2

6 查詢算法

6.1 數(shù)據(jù)結(jié)構(gòu)

H(q):為查詢點(diǎn)q的優(yōu)先隊(duì)列,所存儲(chǔ)的點(diǎn)e的數(shù)據(jù)結(jié)構(gòu)為(T,q,flag,key),T為e所屬的查詢軌跡,q為T所經(jīng)過的查詢點(diǎn),flag為擴(kuò)展標(biāo)識(shí),表示時(shí)間戳的變化方向,flag為0表示向時(shí)間戳減小的方向變化,flag為1表示向時(shí)間戳增大的方向變化,設(shè)e的時(shí)間戳與中心時(shí)刻tmid(T,q)之差為tl(e,q),e到達(dá)其它查詢點(diǎn)的最小距離的最大值diste=Maxqi∈Q-{q}dist (e,qi).若采用終止規(guī)則1,則key=tl(e,q),若采用終止規(guī)則3,key=tl(e,q)+diste/v.key值越小,則優(yōu)先級(jí)越高.

M:為全局優(yōu)先隊(duì)列,數(shù)據(jù)結(jié)構(gòu)與H(q)相同.

LL[q]:為q的所有有效軌跡的集合,有效軌跡的數(shù)據(jù)結(jié)構(gòu)為(ID,E[q]),ID表示有效軌跡的編號(hào),E[q]為有效軌跡在q的查詢軌跡中的有效點(diǎn)構(gòu)成的集合.

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

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

CList:數(shù)據(jù)結(jié)構(gòu)為R(ID,E[q1],…,E[q|Q|]),ID表示R的編號(hào),對(duì)于?q∈Q,都有E[q]為R在q的查詢軌跡中的有效點(diǎn)構(gòu)成的集合,由R(ID,E[q1],…,E[q|Q|])可組合得到R的一條或多條完全有效軌跡,稱R(ID,E[q1],…,E[q|Q|])為一個(gè)完全有效軌跡源,CList存儲(chǔ)完全有效軌跡源的集合.

G:存儲(chǔ)旅行時(shí)間最優(yōu)的k條軌跡R(ID,Emin,Tmin),ID表示R的編號(hào),在CList中找到R,對(duì)R.E[q1],…,R.E[q|Q|]進(jìn)行組合得到R的完全有效軌跡集合U,利用U計(jì)算Ttravel(Q,R),R.Tmin存儲(chǔ)Ttravel(Q,R)的值,R.Emin存儲(chǔ)旅行時(shí)間為Ttravel(Q,R)的完全有效軌跡的有效點(diǎn)集合(如果不唯一,隨機(jī)取其中一個(gè)).

NewEP:用于存儲(chǔ)更新的完全有效軌跡源,數(shù)據(jù)結(jié)構(gòu)與CList相同,對(duì)于CList中的R(ID,E[q1],…,E[q|Q|]),如果R.E[qi]增加了一個(gè)有效點(diǎn)e,把R(ID,E[q1],…,E[q|Q|])復(fù)制到NewEP中,并修改NewEP中的R.E[qi]={e}.

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

CListall:用于存儲(chǔ)NewEP與NewET的并集,用于計(jì)算新的完全有效軌跡的旅行時(shí)間.

6.2 算法描述

函數(shù)1.L(p)

參數(shù):p為軌跡上的點(diǎn).

返回:經(jīng)過點(diǎn)p的軌跡集合.

算法1.TravelTimeSearch

輸入:查詢點(diǎn)Q={q1,q2,…,qm},軌跡數(shù)據(jù)庫D,返回軌跡個(gè)數(shù)k,最大速度v;

輸出:結(jié)果集G;

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

2)M←NewPriorityQueue();//M為全局優(yōu)先隊(duì)列.

3)for eachqinQ

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

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

6) 找到q在T中的近似查詢點(diǎn)q′和它在T中的前驅(qū)和后繼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); // 調(diào)用算法2

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

13)q1.q=q;q1.key=tl(q1,q)+distq1/v;q1.flag=1;q1入隊(duì)列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); // 調(diào)用算法2

25) ife.flag==0

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

27) else ife.flag==1

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

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

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

31)return G;

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

算法2.ETProcess

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

輸出:結(jié)果集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[ ]為當(dāng)前各個(gè)查詢點(diǎn)的有效軌跡集合.第1行,TID[e]用于存儲(chǔ)LE[e]中不在CList中的有效軌跡的ID的集合,第3-5行,利用R和e更新LL[e.q].第6-10行,處理新增加有效點(diǎn)e的情況,第13-14行,調(diào)用算法4求解新增的完全有效軌跡源,第17行,調(diào)用算法5利用CListall對(duì)G進(jìn)行更新.第18-22行,更新LL[ ],以減少重復(fù)計(jì)算.

算法3.EPointtra

輸入:e,e′;

輸出:LE[e′];

1)LE[e′]=φ;

2)for eachRin L(e′)

3) if 存在e′不是R有效點(diǎn)的標(biāo)記 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的有效點(diǎn)的標(biāo)記;

8)return LE[e′];

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

算法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]取出編號(hào)為ID的有效點(diǎn)集合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|]中分別取一個(gè)有效點(diǎn)構(gòu)成一條R的完全有效軌跡,設(shè)通過這種方式得到的R的完全有效軌跡集合為U,t=MinR[py1,py2,…,pym]∈UTtravel(Q,R[py1,py2,…,py|Q|]),其中pyi∈R.E[qi],R[ ]=argmin t(如果R[]不唯一,隨機(jī)取其中一個(gè)即可);

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中的完全有效軌跡源更新結(jié)果G.第3-11行更新G和UB,第9行若G中軌跡個(gè)數(shù)小于k直接將R添加到G中,否則刪除G中的第k個(gè)結(jié)果后,將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′的前驅(qū)或后繼點(diǎn)e;//flag=0表示前驅(qū),否則后繼

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); // 調(diào)用算法2

9)return G;

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

圖6為一個(gè)完整的查詢過程實(shí)例.

圖6 查詢實(shí)例圖Fig.6 Example of query

如圖6所示,選取查詢點(diǎn)Q={q1(p13),q2(p33)},設(shè)k=1.根據(jù)基于網(wǎng)格的倒排索引結(jié)構(gòu),可以得到q1的查詢軌跡為R1和R2,其近似查詢點(diǎn)分別為p13和p23,q2的查詢軌跡為R1和R3,近似查詢點(diǎn)分別為p16和p33.通過前驅(qū)點(diǎn)和后繼點(diǎn)可以確定p13是R1和R2的有效點(diǎn),同理,可以判斷p23同時(shí)為R1和R2的有效點(diǎn),p33為R1的有效點(diǎn),p33和p16均為R3的有效點(diǎn).由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及相應(yīng)的有效點(diǎn)集合Emin={p13,p33},更新G,將R1.ID、Tmin和Emin添加到G,同時(shí)從LL[q1]和LL[q2]中分別刪除(R1.ID,R1.E[q1])和(R1.ID,R1.E[q2]),在準(zhǔn)備階段,各個(gè)查詢點(diǎn)的單獨(dú)優(yōu)先隊(duì)列的初始狀態(tài)為H(q1)={p14,p12,p22,p24},H(q2)={p32,p34,p15,p17},再由H(q1)和H(q2)出隊(duì)列點(diǎn)可構(gòu)成M={p14,p32}.

表1中H(q)中黑色粗體點(diǎn)代表q的查詢軌跡中key值最小的點(diǎn),M中黑色粗體點(diǎn)代表所有查詢軌跡中key值最小的點(diǎn),標(biāo)有下劃線的點(diǎn)為新進(jìn)入優(yōu)先隊(duì)列的點(diǎn),標(biāo)有刪除線的記錄為要?jiǎng)h除的記錄.表1對(duì)循環(huán)過程進(jìn)行了描述.

Iteration1:M中點(diǎn)p14(flag=1)出隊(duì)列,因?yàn)镻[q1,R1,1]為空,將p14賦值給P[q1,R1,1].p14的后繼點(diǎn)p15進(jìn)入H(q1),同時(shí)從H(q1)中出隊(duì)列p12(flag=0)進(jìn)入M中.

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

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

表1 循環(huán)過程
Table 1 Cycle process

循環(huán)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 實(shí) 驗(yàn)

7.1 實(shí)驗(yàn)數(shù)據(jù)集

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

通過運(yùn)行時(shí)間來評(píng)價(jià)算法的性能.在實(shí)驗(yàn)中,改變k(返回軌跡數(shù)量)、|Q|(查詢點(diǎn)個(gè)數(shù))、|Grid|(網(wǎng)格大小)和最大速度v,比較不同條件下終止規(guī)則1(Ter1)和3(Ter3)的性能.

7.2 網(wǎng)格大小|Grid|對(duì)運(yùn)行時(shí)間和旅行時(shí)間的影響

圖7 調(diào)節(jié)|Grid|的影響Fig.7 Impact of |Grid|

綜上,選取|Grid|=30作為實(shí)驗(yàn)中網(wǎng)格大小的值.

7.3 最大速度v對(duì)運(yùn)行時(shí)間和準(zhǔn)確率的影響

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

圖8 調(diào)節(jié)v的影響Fig.8 Impact of v

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

綜上,當(dāng)v=50時(shí),準(zhǔn)確率和運(yùn)行時(shí)間最合適,所以應(yīng)用Ter3時(shí),選取v=50作為實(shí)驗(yàn)中最大速度的值.

7.4 查詢點(diǎn)個(gè)數(shù)|Q|對(duì)運(yùn)行時(shí)間的影響

圖9|Q|對(duì)運(yùn)行時(shí)間的影響Fig.9 Impactof|Q|圖10k對(duì)運(yùn)行時(shí)間的影響Fig.10 Impactofk

7.5 軌跡的數(shù)量k對(duì)運(yùn)行時(shí)間的影響

如圖10所示為應(yīng)用Ter1和Ter3時(shí)k的變化對(duì)運(yùn)行時(shí)間的影響,應(yīng)用Ter1和Ter3時(shí),實(shí)驗(yàn)中|Grid|、k和v與7.4中相同.由圖10可以看出,隨著k的增大,整體呈現(xiàn)上升趨勢,因?yàn)閗的增加意味著返回軌跡個(gè)數(shù)的增加,即計(jì)算量的增加,運(yùn)行時(shí)間變長.

由圖9和圖10可知,應(yīng)用Ter3的運(yùn)行時(shí)間少于應(yīng)用Ter1的運(yùn)行時(shí)間.

8 結(jié) 論

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

由于實(shí)驗(yàn)是在軌跡數(shù)據(jù)集上進(jìn)行的,軌跡的相交是利用采樣點(diǎn)判斷的,軌跡數(shù)據(jù)采集時(shí)采樣率的選取和實(shí)驗(yàn)中網(wǎng)格的選取都會(huì)影響軌跡的相交情況的判斷,因此,本文的下一步工作是在路網(wǎng)已知的情況下,利用路網(wǎng)信息判斷軌跡的相交情況.