欢迎访问发表云网!为您提供杂志订阅、期刊投稿咨询服务!

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

李佳佳; 李雨现; 夏秀峰; 王波涛; 刘向宇 沈阳航空航天大学计算机学院; 沈阳110136; 东北大学计算机学院; 沈阳110169
时间依赖路网  

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

简介:《计算机科学与探索》(CN:11-5602/TP)是一本有较高学术价值的大型月刊,自创刊以来,选题新奇而不失报道广度,服务大众而不失理论高度。颇受业界和广大读者的关注和好评。

注:因版权方要求,不能公开全文,如需全文,请咨询杂志社

计算机科学与探索

北大期刊 下单

关注 17人评论|0人关注
服务与支持