面向时间依赖路网的连续k近邻查询  

Continuous k-Neighbor Query for Time Dependent Road Network

作　　者：李佳佳 李雨现 夏秀峰 王波涛[2] 刘向宇 LI Jiajia;LI Yuxian;XIA Xiufeng;WANG Botao;LIU Xiangyu(College of Computer,Shenyang Aerospace University,Shenyang 110136,China;College of Computer,Northeastern University,Shenyang 110169,China)

机构地区：[1]沈阳航空航天大学计算机学院,沈阳110136 [2]东北大学计算机学院,沈阳110169

出　　处：《计算机科学与探索》2019年第5期788-799,共12页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.61502317;辽宁省自然科学基金No.201602559~~

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]