Abstract: Continuous k-nearest neighbor (CkNN) queries are defined as finding the minimum cost data objects for each point on a specified path. The current studies on continuous k-nearest neighbor queries focus on Euclidean space and static network. However, these algorithms cannot be directly applied to time-dependent road network with varying edge weights. This paper defines and solves the problem of CkNN queries for a specified path in time dependent road network. A two-stage split point-based CkNN queries algorithm is proposed by using the nature of the integral and merging weighted function. In the filter stage, this paper proposes a method that calculates the arrival time of a node and then searches multiple candidate k-nearest neighbors (kNN) results according to the arrival time. In the refinement stage, the weighted functions of the query point to the candidate sets are merged, and the intersection point of the functions is calculated to obtain the split point. And then the result of split points and kNN in the corresponding range are returned. Experimental results show that the proposed algorithm is reduced by nearly one order compared to multiple snapshot k-nearest neighbor queries in response time aspect.

Key words: time-dependent road network, continuous k-nearest neighbor (CkNN) queries, k-nearest neighbors (kNN)

摘要： 连续k近邻查询（continuous k-nearest neighor，CkNN）定义为查找指定路径上每个点的k个最小代价数据对象。目前关于CkNN的研究都是在欧式空间与静态路网中实现的，这些算法不能直接应用到边权值变化的时间依赖路网中。定义并解决了时间依赖路网中的CkNN问题，利用积分的性质以及通过对权值代价函数合并的方式提出了两阶段的基于分割点的CkNN查询算法。过滤阶段提出了计算节点到达时间的方法，再利用到达时间查询出多个候选k近邻结果；求精阶段将查询点到候选结果的权值函数合并，通过计算函数交点得到分割点，进而为查询返回若干个分割点以及相应区间内的k近邻结果。实验结果表明，与进行多次快照k近邻查询相比，所提算法在响应时间上减少了近一个数量级。

关键词: 时间依赖路网, 连续k近邻查询（CkNN）, k近邻（kNN）