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

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)