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

• 作者: 刘向宇 夏秀峰 李佳佳 李雨现 王波涛
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 时间依赖路网 连续k近邻查询(CkNN) k近邻(kNN)
• 年，卷（期）: 2019,（5）
• 所属期刊栏目: 数据库技术
• 页码范围: 788-799
• 页数: 12页
• 分类号: TP311
• 字数: 9882字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1807050

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	夏秀峰	沈阳航空航天大学计算机学院	103	517	11.0	17.0
2	王波涛	东北大学计算机学院	12	82	4.0	8.0
3	刘向宇	沈阳航空航天大学计算机学院	11	19	1.0	4.0
4	李佳佳	沈阳航空航天大学计算机学院	10	31	3.0	5.0
5	李雨现	沈阳航空航天大学计算机学院	1	1	1.0	1.0