面向时间依赖路网的连续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查询效率。