计算机科学与探索2019，Vol.13Issue(5)：788-799,12.DOI:10.3778/j.issn.1673-9418.1807050
面向时间依赖路网的连续k近邻查询*
Continuous k-Neighbor Query for Time Dependent Road Network*
摘要
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.关键词
时间依赖路网/连续k近邻查询(CkNN)/k近邻(kNN)Key words
time-dependent road network/ continuous k-nearest neighbor (CkNN) queries/ k-nearest neighbors (kNN)分类
信息技术与安全科学引用本文复制引用
李佳佳,李雨现,夏秀峰,王波涛,刘向宇..面向时间依赖路网的连续k近邻查询*[J].计算机科学与探索,2019,13(5):788-799,12.基金项目
The Foundation for Production and Research Cooperation Project of Jiangsu Province under Grant No. BY2015019-30 (江苏省产学研合作项目基金). （江苏省产学研合作项目基金）
