面向時間依賴路網(wǎng)的連續(xù)k近鄰查詢*

李佳佳，李雨現(xiàn)，夏秀峰，王波濤，劉向宇

1.沈陽航空航天大學 計算機學院，沈陽 110136

2.東北大學 計算機學院，沈陽 110169

1 引言

連續(xù)k近鄰查詢（continuousk-nearest neighbor，CkNN）是快照k近鄰（k-nearest neighbor，kNN）查詢的一種變體，需要連續(xù)地為指定路徑上的移動對象返回結(jié)果集。CkNN查詢在基于位置的商業(yè)廣告、地理信息系統(tǒng)及移動數(shù)據(jù)庫等方面有著重要應用。例如，為在道路上從A到B行駛的司機實時提供離他最近的k個加油站。目前，CkNN在歐氏空間[1-4]與靜態(tài)路網(wǎng)中[5-8]已經(jīng)被廣泛研究。隨著移動終端的普及，在線地圖服務的快速進展及其在手持設備和汽車導航系統(tǒng)中的廣泛部署，使得城市路網(wǎng)的交通狀況（路段所需行駛時間）得以捕獲。對基于位置服務的研究也由傳統(tǒng)靜態(tài)路網(wǎng)逐漸轉(zhuǎn)向時間依賴路網(wǎng)，即邊權值隨著時間變化而改變的路網(wǎng)。盡管時間依賴路網(wǎng)下的kNN[9-11]、反向kNN查詢[12-13]已被解決，但目前還沒有研究時間依賴路網(wǎng)中CkNN查詢的工作。

時間依賴路網(wǎng)中CkNN查詢可通過執(zhí)行多個單次kNN查詢來解決，然而，一條路徑上存在無數(shù)個連續(xù)的點，對每個點都執(zhí)行一次kNN查詢是低效的。如果每隔單位距離或單位時間執(zhí)行一次kNN查詢，不能準確地獲得kNN變化的位置或時間，得到的結(jié)果可能會有誤差。

利用數(shù)學的手段，計算出kNN結(jié)果發(fā)生變化的分割點是靜態(tài)路網(wǎng)中解決CkNN查詢時常用的方法。由于對象在受限路網(wǎng)中移動，因此計算查詢點到數(shù)據(jù)對象的代價可將其簡化為計算查詢點到查詢點所在邊的其中一個節(jié)點的代價加上該節(jié)點到數(shù)據(jù)對象的代價。在靜態(tài)路網(wǎng)，只有查詢點到節(jié)點的代價線性改變，而節(jié)點到數(shù)據(jù)對象的代價是固定不變的。而在時間依賴路網(wǎng)中，查詢點到查詢點所在邊的其中一個節(jié)點的代價和該節(jié)點到數(shù)據(jù)對象的代價都隨著時間的變化而改變，并且該節(jié)點到數(shù)據(jù)對象的代價取決于查詢點到數(shù)據(jù)對象所經(jīng)過的每個節(jié)點的到達時間，加大了計算查詢點到數(shù)據(jù)對象的函數(shù)的難度，進而無法確定分割點的位置。

為了解決以上困難，本文利用積分的性質(zhì)以及通過對權值代價函數(shù)的合并，提出了基于分割點的連續(xù)k近鄰查詢算法（split point based,SPB）。首先，將整個查詢路徑劃分為多個子路徑，根據(jù)積分定理計算每個子路徑到達終止節(jié)點的時間，從而重新定義每個子路徑的行駛時間函數(shù)；其次，分別查找同一時刻兩個節(jié)點的k+n個數(shù)據(jù)對象，得到候選的kNN結(jié)果；最后，基于每個節(jié)點的到達時間合并查詢點到數(shù)據(jù)對象的函數(shù)，計算函數(shù)的交點，從而確定分割點，最終返回CkNN查詢結(jié)果。實驗結(jié)果表明，與進行多次快照kNN查詢相比，所提算法在響應時間上，減少了將近一個數(shù)量級。

2 相關工作

2.1 時間依賴路網(wǎng)下kNN查詢

近年來，時間依賴路網(wǎng)越來越受到專家、學者的關注，位置相關查詢的研究有很多，如最快路徑查詢[14-15]、反近鄰查詢[12-13]、路徑規(guī)劃[16-19]，本文主要關注kNN查詢，因此本節(jié)只對已有的時間依賴路網(wǎng)中的kNN查詢算法進行了介紹。

Cooke等人[20]第一次提出時間依賴路網(wǎng)。George和Shekhar等人[21]提出了一個時間聚合圖解決時間依賴路網(wǎng)中的kNN查詢，它們將時間段內(nèi)每個邊的行駛時間聚合成一個時間序列。這種方法需要大量的存儲空間并且只能提供近似的結(jié)果。Demiryurek等人[9]提出基于Dijkstra的增量網(wǎng)絡擴展方法，從查詢點開始對路網(wǎng)進行擴展。Demiryurek等人[10]又提出了一種基于 LNI（loose network index）和 TNI（tight network index）解決時間依賴kNN問題方法。LNI和TNI是基于路網(wǎng)中邊權值的上界和下界構(gòu)建的索引，能夠在查詢中縮短查找數(shù)據(jù)對象的時間。Cruz等人[11]提出TD-NE-A*（time dependent network expansion with A*search）算法，通過應用增量網(wǎng)絡擴展和修剪頂點提高查詢效率。以上研究工作只關注單次kNN的查詢效率，無法高效應用到解決CkNN查詢中。

2.2 非時間依賴路網(wǎng)中的連續(xù)kNN查詢

針對傳統(tǒng)靜態(tài)路網(wǎng)中的CkNN查詢，已有大量的研究工作，盡管這些技術不能直接應用到邊權值不斷變化的時間依賴路網(wǎng)，但可為解決時間依賴路網(wǎng)中的CkNN問題提供一些思路，本節(jié)將對這類研究工作進行介紹。

Sistla等人[22]首先確定了CkNN的重要性，并描述了這些查詢表達式的建模方法和查詢語言。Song和Roussopoulos[23]提出了利用固定上限的方法來解決連續(xù)kNN查詢，只需要指出對象可以移動的最小距離，無需查找新的kNN。他們還提出了一種雙緩沖搜索方法，可以在查詢位置被預測時使用。Feng和Watanabe[24]基于查找NN查詢必須位于路徑上的位置執(zhí)行，解決了CkNN（k=1）查詢問題。Cho等人[5]設計了安全退出算法（safe exit algorithm，SEA），在查詢路徑未知的情況下，連續(xù)監(jiān)控移動查詢點的NN查詢。

Safar和Ebrahimi[7]提出基于PINE的DAR/eDAR算法來解決CkNN查詢。該算法通過交換兩個相鄰節(jié)點的kNN表，找到分割節(jié)點，當兩個表完全相同時，就會發(fā)現(xiàn)所有的分割點。Kolahdouzan等人[8]提出基于 VN3的 IE（intersection examination）和 UBA（upper bound algorithm）方法解決CkNN查詢。IE通過定義當前kNN結(jié)果列表中每個數(shù)據(jù)對象的趨勢找到分割節(jié)點。UBA類似于Song和Roussopoulos[23]中討論的內(nèi)容：當查詢對象僅稍微移動時，它的kNN很可能保持不變。UBA通過消除對沒有任何分割節(jié)點的相鄰節(jié)點kNN的計算，提高IE的性能。Zhao等人[6]提出了VCkNN（Voronoi-based continuousknearest neighbor）算法，一種基于Voronoi圖的CkNN搜索算法。VCkNN不需要將查詢路徑劃分為段,只需要構(gòu)建候選數(shù)據(jù)對象到邊界點的距離函數(shù)，通過比較分段函數(shù)，找到分割點。

以上研究工作關注的是邊權值靜態(tài)不變的非時間依賴路網(wǎng)中的連續(xù)近鄰查詢，在時間依賴路網(wǎng)中，邊權值是個線性函數(shù)，已有算法在新的路網(wǎng)環(huán)境中不再適用，但有一些思想，如計算分割點等，可為解決時間依賴路網(wǎng)中的CkNN查詢提供思路。

3 問題定義

本章主要形式化定義了時間依賴路網(wǎng)下CkNN查詢的相關問題。

定義1（時間依賴路網(wǎng)）時間依賴路網(wǎng)GT由集合N、E和C組成，記為GT=(N,E,C)。其中N={n1,n2,…,nn}是節(jié)點的有限集合；E={(ni,nj)|ni,nj∈N,i≠j}是連接N中兩個不同節(jié)點的邊的有限集合；C={c(ni,nj)(t)|(ni,nj)∈E}，c(ni,nj)(t):[0,T]→R+，表示在t時刻從ni到nj所花費的時間，其中t∈[0,T]，T為時間周期。

在時間依賴路網(wǎng)中，權值C的常用表達模型有兩種：一種是形如y=kx+b的連續(xù)分段函數(shù)；另一種是形如y=c離散分段函數(shù)。本文采用的是前者，可以看出，y=c是y=kx+b的特例，該模型也可以應用到本文所提算法中。

圖1顯示了路網(wǎng)結(jié)構(gòu)，邊上的數(shù)字表示距離。n1,n2,…,n4代表路網(wǎng)中的節(jié)點，p1,p2,…,p5代表數(shù)據(jù)對象。圖2顯示了時間依賴路網(wǎng)下相應邊的分段線性行駛時間函數(shù)。

Fig.1 Road network圖1 路網(wǎng)圖

Fig.2 Travel time function圖2 行駛時間函數(shù)

定義2（時間依賴路網(wǎng)中的最快路徑（the fastest path in time dependent，TDFP）） 在GT中，最快路徑記為TDFP(s,d,ts)，是指在時刻ts出發(fā)從s到d所花費時間最少的路徑。

定義3（時間依賴路網(wǎng)中的kNN查詢（k-nearest neighbors in time dependent，TD-kNN））在GT中，有一組n個數(shù)據(jù)對象P={p1,p2,…,pn}，查詢點q的TD-kNN查詢是指找到具有最小時間依賴代價的k個數(shù)據(jù)對象的子集P'∈P，對于任何數(shù)據(jù)對象p'∈P'和p∈P-P'，都滿足TDFP(q,p',t)≤TDFP(q,p,t)。

定義4（查詢路徑（query path,Qpath））查詢路徑是指用戶指定的路網(wǎng)中的一條路徑，記為QPath={nj,nj+1,…,nj+n}，nj屬于路網(wǎng)GT中的集合N，相鄰節(jié)點（nj,nj+1）屬于路網(wǎng)GT中的集合E，也稱SubPath(SPath)為QPath的子路徑，記為SPathj={ns,ne}。其中ns,ne∈N，ns表示子路徑的起始節(jié)點，ne表示子路徑的終止節(jié)點。

定義5（時間依賴路網(wǎng)中的CkNN查詢（continuousk-nearest neighbors in time dependent，TD-CkNN））在路網(wǎng)GT上，給定一條查詢路徑QPath={nj,nj+1,…,nj+n}和k值，TD-CkNN返回路徑上每個點的TD-kNN結(jié)果。

定義6（行駛速度（velocity,v））行駛速度記為v(t)(ni,nj)，定義為t時刻出發(fā)，從ni到nj的速度。行駛速度的計算公式如下：

定義7（到達時間（arrival time，At））到達時間記為At(ni,nj)，表示從ni出發(fā)到達nj的時間。

4 兩階段基于分割點的TD-CkNN查詢算法

解決CkNN最樸素的算法是每隔單位距離或單位時間發(fā)起一次查詢。樸素算法隨著路徑的長度或者行駛時間的增大，計算次數(shù)越來越多，而且只能判斷出哪兩個相鄰位置或時間的kNN結(jié)果不同，不能準確地獲得kNN結(jié)果變化的位置或時間，有一定誤差。

以圖1為例，在GT中，假設指定的查詢路徑QPath={n1,n2,n3}連續(xù)查找路徑上每個點的2NN結(jié)果，如果利用樸素算法每隔一個單位距離發(fā)起一次查詢，則需要執(zhí)行251次，而且只能判斷出哪兩個相鄰位置的kNN發(fā)生變化，不能準確定位kNN變化的準確位置。為了減少盲目查找次數(shù)，首先將整個查詢路徑劃分成多個子路徑，確定同一時刻每個子路徑的候選集，對每個子路徑進行相同的操作。QPath={n1,n2,n3}可以劃分為SPath1={n1,n2}，SPath2={n2,n3}，只需要在n1的出發(fā)時刻t1對n1、n2，以及在n2的出發(fā)時刻t2對n2、n3分別執(zhí)行（k+n）NN查詢，即4次（k+n）NN查詢。

在時間依賴路網(wǎng)中，盡管邊權值不斷變化，但節(jié)點在某個時間段內(nèi)的kNN結(jié)果變化不大，相鄰兩個節(jié)點的kNN結(jié)果往往有交集。移動查詢點從子路徑起始節(jié)點到終止節(jié)點的kNN結(jié)果是兩個節(jié)點同一時刻kNN結(jié)果并集的子集。為了保證算法的正確性，將查詢路徑的每個子路徑起始節(jié)點與終止節(jié)點同一時刻的(k+n)個數(shù)據(jù)對象的并集作為子路徑的候選集。

定理1子路徑上每個點的kNN是子路徑兩個節(jié)點候選集并集的子集。

證明假設p是子路徑上某移動查詢點q的查詢結(jié)果，p不屬于起始節(jié)點與終止節(jié)點(k+n)NN集合并集P'且P'中沒有q的結(jié)果，則TDFP(q,p,t)≤TDFP(q,pj,t)，TDFP(ns,p,t)≥TDFP(ns,pj,t)（或TDFP(ne,p,t)≥TDFP(ne,pj,t)），其中pj∈P'。因為移動查詢點q在子路徑上，所以q到p一定會經(jīng)過ns（或ne），即TDFP(q,p,t)=TDFP(q,ns,t)+TDFP(ns,p,t)。假設p經(jīng)過ns（p經(jīng)過ne與此原理相同），則TDFP(q,pj,t)=TDFP(q,ns,t)+TDFP(ns,pj,t)。又因為p是q的一個結(jié)果，所以TDFP(q,p,t)≤TDFP(q,pj,t)即TDFP(ns,p,t)≤TDFP(ns,pj,t)，與TDFP(ns,p,t)≥TDFP(ns,pj,t)相矛盾。因此查詢結(jié)果是這兩個節(jié)點候選集中的子集。 □

為了可以準確地找到kNN結(jié)果變化的位置，借鑒靜態(tài)路網(wǎng)CkNN算法中分割點的思想。無論是在靜態(tài)路網(wǎng)還是時間依賴路網(wǎng)中，查詢點到數(shù)據(jù)對象的代價都是按照一定的趨勢不斷變化。而且隨著查詢點的移動，數(shù)據(jù)對象不是遠離查詢點就是接近查詢點。在時間依賴路網(wǎng)中，如果存在兩個數(shù)據(jù)對象pi、pj，查詢點q到pi的行駛時間相對增加，查詢點q到pj的行駛時間相對減少，則可能存在一個分割點，使得查詢點q到pi、pj的行駛時間相同。

為了能夠快速地找到分割點,首先需要計算查詢路徑上每個節(jié)點的到達時間，根據(jù)每個子路徑起始節(jié)點的出發(fā)時間對不可能的數(shù)據(jù)對象進行修剪，找到可能成為結(jié)果的候選集，避免不必要的計算；然后比較合并后移動查詢點到數(shù)據(jù)對象的行駛時間函數(shù)來確定分割點及對應的k個數(shù)據(jù)對象。因此，將查詢算法分為兩個階段：根據(jù)子路徑起始節(jié)點的出發(fā)時間確定候選集的過濾階段和查找分割點的求精階段。過濾階段，首先由指定的出發(fā)時間計算出到達子路徑終止節(jié)點的時間（到達該節(jié)點的時間即為該節(jié)點的出發(fā)時間），為下一個子路徑查詢做準備。然后利用TD-Dijkstra算法分別查找每個子路徑起始節(jié)點出發(fā)時刻相鄰兩個節(jié)點的（k+n）個數(shù)據(jù)對象的并集作為候選集。求精階段，合并查詢點分別到候選集中每個數(shù)據(jù)對象的行駛時間函數(shù)，判斷這些函數(shù)的交點是否是分割點（相交函數(shù)在交點處的行駛時間相同）。最后將分割點對應到路網(wǎng)中。

4.1 過濾階段

本節(jié)將解釋如何計算子路徑終止節(jié)點的到達時間，以及如何查找候選集。

之前的研究都是根據(jù)起始節(jié)點的出發(fā)時間加上出發(fā)時間對應的行駛時間函數(shù)值的和作為終止節(jié)點的到達時間。然而，在出發(fā)時間與到達時間不在同一個分段區(qū)間的情況下，這種方法求出的到達時間是不準確的。針對該問題，本文利用積分的方法解決跨時間段求解到達時間的問題。

眾所周知，速度乘以時間即為路程，反而言之路程除以速度即為到達時間。然而在時間依賴路網(wǎng)中，行駛時間隨著出發(fā)時間變化而變化，導致速度也隨出發(fā)時間改變，因此不能直接用兩點距離除以速度計算到達時間。為了解決此問題，利用速度積分的方法計算到達時間。

定理2某個時間間隔[a,b]內(nèi)對應的分段速度積分為[a,b]時間內(nèi)行駛的路程。公式如下：

證明d(路程)=v(速度)×t(時間)，路程對時間的導數(shù)是速度（即d'=v(t)），導數(shù)與積分互為逆運算，因此速度的積分為路程。 □

根據(jù)定理2可知，對出發(fā)時刻與到達時刻的速度積分可以得到在這段時間行駛的距離。每條邊的長度以及每條邊的行駛時間函數(shù)已知，由式（1）也可以計算出每條邊的分段速度函數(shù)，繼而可以根據(jù)定理1反解出到達時間，具體步驟如下：

步驟1對出發(fā)時刻，出發(fā)時刻所在分段線性速度函數(shù)區(qū)間的末尾區(qū)間的速度積分得到的長度記為d'。

步驟2將d'與該子路徑的長度d進行比較，如果（1）d'=d，說明出發(fā)時刻所在分段線性速度函數(shù)區(qū)間的末尾時間即為到達時間；（2）d'＞d，那么說明到達時間在這個區(qū)間內(nèi)，根據(jù)式（1），可以反解出At；（3）d'＜d，說明這個時間段內(nèi)行駛的路程小于余下的路程，用d減去d'的值重新設置d，再對下一個分段線性速度區(qū)間的速度進行積分，記為d'，繼續(xù)執(zhí)行步驟2，直到計算出到達時間At。

例115時刻從n1出發(fā)計算n2的到達時間。由圖1、圖2可知，利用式（1）可以計算出n1、n2的速度，結(jié)果為。首先由定理1計算出15時刻到20時刻行駛的路程，顯然，50＜100。然后計算下個區(qū)間行駛的路程，說明到達時間在[20,30]區(qū)間內(nèi)。最后將d=50，，a=20代入到式（2）中，解得b=27.45，因此27.45時刻可以到達n2。同理可以根據(jù)n2的到達時間計算出到達n3的時間。

在出發(fā)時間一定的條件下，每個節(jié)點的到達時間也是此節(jié)點的出發(fā)時間。接下來，需要根據(jù)每個子路徑起始節(jié)點的出發(fā)時間分別來計算子路徑起始節(jié)點與終止節(jié)點的k+n個數(shù)據(jù)對象。

采用了最基本的Dijkstra算法查找節(jié)點的(k+n)NN結(jié)果。最后，將子路徑上兩個節(jié)點的(k+n)NN結(jié)果合并，去掉重復的結(jié)果，作為候選集。綜合圖2，n1、n2在15時刻的3NN結(jié)果分別為R1={p1,p2,p3}，R2={p4,p5,p1}，合并的結(jié)果為R={p1,p2,p3,p4,p5}。

4.2 求精階段

目前已經(jīng)找到了子路徑起始節(jié)點與終止節(jié)點(k+n)NN的并集?，F(xiàn)在解釋如何使用這些候選集來構(gòu)建函數(shù)找到分割點。下面，首先描述怎樣合并移動查詢點到候選集數(shù)據(jù)對象的行駛時間函數(shù)，然后描述怎樣根據(jù)行駛時間函數(shù)找到分割點。

由于時間依賴路網(wǎng)的特性，在計算查詢點到數(shù)據(jù)對象的行駛時間函數(shù)時，首先要考慮查詢點到數(shù)據(jù)對象所經(jīng)過的每個節(jié)點的到達時間，以每個節(jié)點的到達時間為此節(jié)點的出發(fā)時間計算到達下一個節(jié)點的時間。在線查詢階段已經(jīng)計算出每個子路徑出發(fā)時刻對應的到達時刻，由這兩個時刻重新定義此時間段內(nèi)子路徑的行駛時間函數(shù)，公式如下：

根據(jù)行駛時間可以快速計算查詢點在移動過程中分別到兩個端點的到達時間。

查詢點到起始節(jié)點到達時間計算公式：

查詢點到終止節(jié)點到達時間計算公式：

如果查詢點經(jīng)過多個節(jié)點到達數(shù)據(jù)對象，則需要將多個邊的行駛時間函數(shù)合并成一個行駛時間函數(shù)，目的是快速找到分割點。合并函數(shù)的思想：計算第一條邊的行駛時間函數(shù)每個區(qū)間的到達時間范圍，每個區(qū)間的到達時間范圍是第二條邊的出發(fā)時間范圍。將第一條邊每個區(qū)間的到達時間范圍與第二條邊的出發(fā)時間相同的區(qū)間合并，得到兩條邊的合并函數(shù)，再將合并的邊與第三條合并，以此類推。

例2合并沿邊n1n2移動的查詢點q到數(shù)據(jù)對象p1行駛時間函數(shù)。首先根據(jù)式（3）可以計算出查詢點q到n1的行駛時間函數(shù)：c(q,n1)=t-15,t∈[15.00,27.45]。注意，當q從n1移動到某個位置，再返回到n1時的行駛時間是從n1到q行駛時間的2倍。因此c1=15.00，c2=(27.45-15.00)+27.45=39.90，然后開始遍歷n1p1的函數(shù)。n1p1的第一個分段區(qū)間為[0,10]，c1、c2都不屬于該區(qū)間，所有值均不變。遍歷下一個區(qū)間[10,30]，因為只有c1在區(qū)間內(nèi)，所以需要將[15.00,27.45]進行分割，合并的新函數(shù)結(jié)果為：c=2t+15,t∈[15.00,22.50]，此時，c1=30，再遍歷下一個區(qū)間[30,40]，c1、c2都屬于該區(qū)間，因此合并結(jié)果為：c=2t-27.5,t∈[22.50,27.45]。

然而并不是查詢點到候選集中所有數(shù)據(jù)對象都需要合并函數(shù)，以下情況不需要合并函數(shù)：（1）子路徑上的兩個節(jié)點是數(shù)據(jù)對象，如果起始節(jié)點為數(shù)據(jù)對象，那么在[Tt,At]區(qū)間內(nèi)查詢點到數(shù)據(jù)對象的行駛時間函數(shù)為c(q,p)(t)=t-Tt；如果終止節(jié)點為查詢點，那么在[Tt,At]區(qū)間內(nèi)查詢點到數(shù)據(jù)對象的行駛時間函數(shù)為c(q,p)(t)=-t+At。（2）子路徑的起始節(jié)點到數(shù)據(jù)對象的路徑包含子路徑的終止節(jié)點，則在[Tt,At]區(qū)間內(nèi)查詢點到數(shù)據(jù)對象的行駛時間函數(shù)為c(q,p)(t)=c(ne,p)(At)-t+At；因為從起始節(jié)點出發(fā)總是在固定的時間到達終止節(jié)點，所以終止節(jié)點到數(shù)據(jù)對象的行駛時間c(ne,p)(At)是一個常數(shù)，也就不需要合并ne到p的函數(shù)。（3）如果路徑只包含子路徑終止節(jié)點，則在[Tt,At]區(qū)間內(nèi)查詢點到數(shù)據(jù)對象的行駛時間函數(shù)為c(q,p)(t)=c(ne,p)(At)-t+At，與（2）同理。

例3q到p4、p5只經(jīng)過n2，因此c(q,p4)=37.45-t,t∈[15.00,27.45]，c(q,p5)=46.175-t,t∈[15.00,27.45]。

根據(jù)查詢點到每個數(shù)據(jù)對象的行駛時間函數(shù)可以計算出這些函數(shù)是否有交點。需要注意的是，并不是所有交點都是分割點，需要對每個交點進行驗證。如果兩個函數(shù)相交得到交點的值，計算兩個函數(shù)其中一個（交點處兩個函數(shù)值相同）在交點對應的行駛時間值cinter，再與其他函數(shù)在交點的行駛時間值比較，當其他函數(shù)的行駛時間值至多有k-1個小于cinter，說明該交點就是分割點。分割點的值除以子路徑的行駛時間，再乘以子路徑的長度，就是分割點在路網(wǎng)中的位置。

圖3顯示了子路徑SP1={n1,n2}上移動查詢點q到候選集R={p1,p2,p3,p4,p5}中每個數(shù)據(jù)對象的行駛時間函數(shù)。由圖3可知17.294是p3、p5兩個函數(shù)的交點，p1、p2、p4在17.294對應的函數(shù)值都小于p3、p5對應的函數(shù)值，因此舍棄17.294。經(jīng)過驗證只有17.450、21.225、22.450、25.588才是分割點。最后將分割點對應到路網(wǎng)中，結(jié)果見表1。

Fig.3 Travel time function of moving query point qto data object圖3 移動查詢點q到數(shù)據(jù)對象的行駛時間

Table 1 2NN result of subpath n1n2表1 子路徑n1n2的2NN結(jié)果

算法1 SPB

輸入：QPath,k,t,n。

輸出：＜Spoint,kNN＞。

4.3 算法描述

算法1給出了SPB算法過程，第1行將整個路徑劃分為多個子路徑，對每個子路徑進行以下相同的操作。第2行到第7行是過濾階段，分別計算每個子路徑起始節(jié)點出發(fā)時刻起始節(jié)點與終止節(jié)點的（k+n）NN結(jié)果，將兩個結(jié)果合并，得到候選集。然后用積分計算起始節(jié)點到終止節(jié)點的到達時間，為下一個路徑的（k+n）NN查詢做準備。根據(jù)積分得到的到達時間更加準確，解決了到達時間跨區(qū)間的問題。第8～16行是求精階段，第8～9行描述了合并查詢點到候選集數(shù)據(jù)對象的行駛時間函數(shù)；第10～13行描述了如何計算多個查詢點到候選集數(shù)據(jù)對象行駛時間函數(shù)的交點；第14行判斷交點是否是分割點；如果該交點是分割點，先將時間分割點對應到路網(wǎng)中如第16行所示，再返回得到路網(wǎng)分割點和對應的kNN結(jié)果，如第17行所示。

5 實驗

實驗用德國奧爾登堡的路網(wǎng)圖，進行仿真實驗，地圖包含6 105個節(jié)點，7 035條邊。電腦配置處理器Intel?CoreTMi5-3470 CPU@3.20 GHz，內(nèi)存 4 GB。本文將全天分為5個時段，[22:00,7:00],[7:00,9:00],[9:00,17:00],[17:00,19:00],[19:00,22:00]，每隔5 min對邊賦權值，得到288個權值，根據(jù)邊的權值擬合為分段線性函數(shù)。因為目前還沒有關于時間依賴路網(wǎng)中的CkNN研究，所以將本文算法與每隔一個單位距離進行TDkNN的快照查詢（multiple snapshot-query based，MSB）進行了對比。對比實驗也是基于TDDijkstra算法實現(xiàn)的。持續(xù)監(jiān)控每次查詢的100次時間戳，求其平均值。用不同的參數(shù)來評估本文提出的SPB的性能。對每組實驗，只改變一個參數(shù)其余參數(shù)設置為表2中的默認值。通過本文的實驗，測量了數(shù)據(jù)對象個數(shù)k、多余數(shù)據(jù)對象個數(shù)n、數(shù)據(jù)對象（points of interest，POI）密度、路徑長度d的影響，其中n是指比需要查詢的數(shù)據(jù)對象k多出的數(shù)據(jù)對象個數(shù)。

Table 2 Experimental parameters表2 實驗參數(shù)

（1）n值

圖4（a）顯示了不同n值對正確率（正確率=SPB算法得到的分割點個數(shù)/路徑上實際分割點的個數(shù)×100%）的影響?？梢钥闯觯S著n值的增加，SPB算法的正確率顯著提高。這是因為隨著n值的增加候選集越來越大，不會遺漏正確的結(jié)果。圖4（b）顯示了不同n值對響應時間的影響?？梢钥闯?，隨著n值的增加，SPB算法的響應時間逐漸提高。這是因為隨著n值的增加，查詢需要擴展的節(jié)點也在增多，導致響應時間增加。為了在響應時間最小化的前提下，提高算法的正確率，綜合圖4（a）和圖4（b）將n的值設為10。因為從兩個圖中可以看出當n=10時，正確率為100%，而且響應時間相對較小。

Fig.4 Effect of non SPB algorithm圖4 n值對SPB算法的影響

（2）k值

圖5（a）顯示了隨著k值的增加，兩種算法的響應時間?？梢钥闯?，MSB算法和SPB算法都隨著k值的增加而增加，但MSB算法的響應時間遠遠大于SPB響應時間，而且SPB算法的響應時間增加幅度小。這是由于查詢目標節(jié)點增加，MSB需要擴展更多的節(jié)點得到目標節(jié)點，而擴展節(jié)點增加的同時導致了響應時間的增加。SPB算法雖然也會隨著k值的增加而增加，但是該算法只對每個子路徑上的兩個節(jié)點擴展，因此增加幅度較小。

圖5（b）顯示了SPB算法的正確率。由圖5（b）可知，隨著k值的增加正確率下降。因為在n不變的情況下增大k值，只會導致k值大的候選集相對k值小的候選集選擇范圍變小，遺漏正確的數(shù)據(jù)對象，降低正確率。因此在k值增加的同時，也應該適當?shù)卦黾觧的值。

Fig.5 Effect of kon experiment圖5 k值對實驗的影響

（3）數(shù)據(jù)對象（POI）密度

Fig.6 Effect of POI density on response time圖6 POI密度對響應時間的影響

圖6表示隨著POI密度的增加，兩種算法查詢響應時間的變化趨勢。由圖6可知，隨著POI密度增加，MSB的響應時間減少，SPB算法的響應時間趨于平穩(wěn)，SPB與MSB的響應時間最多差一個數(shù)量級。這是因為遍歷節(jié)點的個數(shù)隨著密度的增大而減少，所以兩種算法的響應時間都減少。但是由于MSB算法查詢發(fā)起點比SPB多，因此MSB的響應時間比SPB的響應時間大。

（4）路徑長度

圖7表示了隨著路徑長度的增加，MSB的響應時間線性增加，SPB的響應時間幾乎平穩(wěn)，SPB優(yōu)于MSB。因為MSB算法是每隔一個距離單位發(fā)起一次查詢，所以隨著路徑的增加，響應時間呈線性增加。然而，SPB算法只對每個子路徑的兩個節(jié)點進行查詢，與路徑長度無關。

Fig.7 Effect of path length on response time圖7 路徑長度對響應時間的影響

由以上分析結(jié)果可知，本文所提的SPB算法在所有情況下都優(yōu)于MSB算法。

6 結(jié)束語

與靜態(tài)路網(wǎng)相比，時間依賴路網(wǎng)更具有現(xiàn)實意義。本文提出了解決時間依賴路網(wǎng)中CkNN查詢的算法，利用最基本的Dijkstra算法確定查詢子路徑的候選集，合并查詢點到候選集數(shù)據(jù)對象的行駛時間函數(shù)，再利用計算函數(shù)交點的方法找到路徑上的分割點和相應的kNN結(jié)果。實驗結(jié)果表明，所提SPB算法能夠準確地找到分割點，且比采用多次快照kNN查詢方法執(zhí)行速度快10倍左右。下一步將繼續(xù)研究如何利用上一次計算結(jié)果來增量計算出下一次的結(jié)果，從而進一步提高時間依賴路網(wǎng)中CkNN查詢效率。