基于缓存的时变道路网最短路径查询算法

作     者：黄阳 周旭 杨志邦 余婷 张吉 曾源远 李肯立 Huang Yang;Zhou Xu;Yang Zhibang;Yu Ting;Zhang Ji;Zeng Yuanyuan;Li Kenli

作者机构：湖南大学信息科学与工程学院长沙410082 之江实验室杭州311100 

基　　金：国家自然科学基金项目(62172146,61802032,61772182,62172157) 之江实验室开放课题(2021KD0AB02) 湖南省自然科学基金项目(2020JJ4220,2020JJ5083) 湖南省科技创新计划项目(2020RC2032) 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2022年第59卷第2期

页      码：376-389页

摘      要：作为图论中的基本操作之一,最短路径查询已被广泛应用于路径规划、GPS导航和个性化推荐等基于道路网的相关应用中.针对道路网中在线最短路径查询所面临的计算成本高、查询速度慢等问题,现有方案通常采用缓存技术来优化其性能.考虑到道路网的边权重具有频繁变化的特性,现有工作未能有效地实现缓存数据的快速更新,忽略了缓存数据的时效性,从而导致缓存命中率不高.鉴于此,首先提出一种新的缓存存储结构,能够有效平衡最短路径的整体查询速度与缓存数据更新速度之间的关系;其次,结合路径共享能力及路径多样性设计了新的缓存存储策略,优化缓存收益,继而提高缓存命中率;最后,提出基于缓存的时变最短路径查询(cache-based time-varying shortest path query,CTSPQ)算法.在真实数据集上的实验结果验证了CTSPQ算法的有效性和可扩展性.

主 题 词：最短路径查询 时变道路网 缓存技术 在线查询 位置服务 

学科分类：0810[工学-土木类] 08[工学] 0701[理学-数学类] 081201[081201] 0823[工学-农业工程类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.7544/issn1000-1239.20210892

馆 藏 号：203107178...