时间依赖路网上的移动对象K近邻查询算法

• 作者: 张彤 秦小麟
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: K近邻查询 移动对象 时间依赖路网 A?算法 网格索引
• 年，卷（期）: 2020,（1）
• 所属期刊栏目: 数据库&大数据&数据科学
• 页码范围: 79-86
• 页数: 8页
• 分类号: TP311
• 字数: 9871字
• 语种: 中文
• DOI: 10.11896/jsjkx.181102231

摘要

随着基于位置服务的广泛应用,时间依赖路网上的对象查询逐渐成为研究热点.以往研究大多只针对时间依赖路网上的静态对象(如加油站、餐厅等),未考虑到移动对象(如出租车)的情况,而移动对象的查询在日常生活中有着非常广泛的应用场景.因此,文中提出了一种针对时间依赖路网上的移动对象K近邻查询算法TD-MOKNN,该算法分为预处理阶段和查询阶段.在预处理阶段,通过建立路网和网格索引,提出了一种新的移动对象到路网的映射方法,解除了以往研究假设移动对象恰好在路网顶点上的限制;在查询阶段,采用启发式搜索,借助倒排网格索引计算了一种新的高效启发值,通过预处理信息和启发值设计了高效K近邻查询算法,并给出了算法的正确性证明和时间复杂度分析.实验验证了所提算法的有效性,相比现有算法,TD-MOKNN算法在遍历顶点数和响应时间上分别减少了55.91％和54.57％,查询效率平均提升了55.2％.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	秦小麟	南京航空航天大学计算机科学与技术学院	175	1597	20.0	30.0
2	张彤	南京航空航天大学计算机科学与技术学院	7	3	1.0	1.0