面向時間依賴路網的連續k近鄰查詢*

李佳佳，李雨現，夏秀峰，王波濤，劉向宇

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

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

1 引言

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

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

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

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

2 相關工作

2.1 時間依賴路網下kNN查詢

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

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

2.2 非時間依賴路網中的連續kNN查詢

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

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

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

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

3 問題定義

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

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

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

圖1顯示了路網結構，邊上的數字表示距離。n1,n2,…,n4代表路網中的節點，p1,p2,…,p5代表數據對象。圖2顯示了時間依賴路網下相應邊的分段線性行駛時間函數。

Fig.1 Road network圖1 路網圖

Fig.2 Travel time function圖2 行駛時間函數

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 過濾階段

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

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

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

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

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

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

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

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

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

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

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

4.2 求精階段

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

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

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

查詢點到起始節點到達時間計算公式：

查詢點到終止節點到達時間計算公式：

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

例2合并沿邊n1n2移動的查詢點q到數據對象p1行駛時間函數。首先根據式（3）可以計算出查詢點q到n1的行駛時間函數：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的函數。n1p1的第一個分段區間為[0,10]，c1、c2都不屬于該區間，所有值均不變。遍歷下一個區間[10,30]，因為只有c1在區間內，所以需要將[15.00,27.45]進行分割，合并的新函數結果為：c=2t+15,t∈[15.00,22.50]，此時，c1=30，再遍歷下一個區間[30,40]，c1、c2都屬于該區間，因此合并結果為：c=2t-27.5,t∈[22.50,27.45]。

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

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

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

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

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

Table 1 2NN result of subpath n1n2表1 子路徑n1n2的2NN結果

算法1 SPB

輸入：QPath,k,t,n。

輸出：＜Spoint,kNN＞。

4.3 算法描述

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

5 實驗

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

Table 2 Experimental parameters表2 實驗參數

（1）n值

圖4（a）顯示了不同n值對正確率（正確率=SPB算法得到的分割點個數/路徑上實際分割點的個數×100%）的影響。可以看出，隨著n值的增加，SPB算法的正確率顯著提高。這是因為隨著n值的增加候選集越來越大，不會遺漏正確的結果。圖4（b）顯示了不同n值對響應時間的影響。可以看出，隨著n值的增加，SPB算法的響應時間逐漸提高。這是因為隨著n值的增加，查詢需要擴展的節點也在增多，導致響應時間增加。為了在響應時間最小化的前提下，提高算法的正確率，綜合圖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算法的響應時間增加幅度小。這是由于查詢目標節點增加，MSB需要擴展更多的節點得到目標節點，而擴展節點增加的同時導致了響應時間的增加。SPB算法雖然也會隨著k值的增加而增加，但是該算法只對每個子路徑上的兩個節點擴展，因此增加幅度較小。

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

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

（3）數據對象（POI）密度

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

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

（4）路徑長度

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

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

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

6 結束語

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