| 面向时间依赖路网的连续k近邻查询 |
| |
| 引用本文： | 李佳佳,李雨现,夏秀峰,王波涛,刘向宇.面向时间依赖路网的连续k近邻查询[J].计算机科学与探索,2019,13(5):788-799. |
| |
| 作者姓名： | 李佳佳 李雨现 夏秀峰 王波涛 刘向宇 |
| |
| 作者单位： | 沈阳航空航天大学 计算机学院,沈阳,110136;东北大学 计算机学院,沈阳,110169 |
| |
| 基金项目： | 国家自然科学基金No.61502317;辽宁省自然科学基金No.201602559~~ |
| |
| 摘 要： | 连续k近邻查询(continuous k-nearest neighor,Ck NN)定义为查找指定路径上每个点的k个最小代价数据对象。目前关于Ck NN的研究都是在欧式空间与静态路网中实现的,这些算法不能直接应用到边权值变化的时间依赖路网中。定义并解决了时间依赖路网中的Ck NN问题,利用积分的性质以及通过对权值代价函数合并的方式提出了两阶段的基于分割点的Ck NN查询算法。过滤阶段提出了计算节点到达时间的方法,再利用到达时间查询出多个候选k近邻结果;求精阶段将查询点到候选结果的权值函数合并,通过计算函数交点得到分割点,进而为查询返回若干个分割点以及相应区间内的k近邻结果。实验结果表明,与进行多次快照k近邻查询相比,所提算法在响应时间上减少了近一个数量级。
|
| 关 键 词： | 时间依赖路网 连续k近邻查询(CkNN) k近邻(kNN) |
Continuous k-Neighbor Query for Time Dependent Road Network |
| |
| LI Jiajia,LI Yuxian,XIA Xiufeng,WANG Botao,LIU Xiangyu.Continuous k-Neighbor Query for Time Dependent Road Network[J].Journal of Frontier of Computer Science and Technology,2019,13(5):788-799. |
| |
| Authors: | LI Jiajia LI Yuxian XIA Xiufeng WANG Botao LIU Xiangyu |
| |
| Affiliation: | (College of Computer,Shenyang Aerospace University,Shenyang 110136,China;College of Computer,Northeastern University,Shenyang 110169,China) |
| |
| Abstract: | 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) |
| |
| Keywords: | time-dependent road network continuous k-nearest neighbor (CkNN) queries k-nearest neighbors (kNN) |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
