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

摘要：

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

关键词：K近邻查询、移动对象、时间依赖路网、A?算法、网格索引

所属期刊栏目：47

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金61373015,61728204

在线出版日期：2020-03-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：79-86