典型文献
基于缓存的时变道路网最短路径查询算法
文献摘要：
作为图论中的基本操作之一,最短路径查询已被广泛应用于路径规划、GPS导航和个性化推荐等基于道路网的相关应用中.针对道路网中在线最短路径查询所面临的计算成本高、查询速度慢等问题,现有方案通常采用缓存技术来优化其性能.考虑到道路网的边权重具有频繁变化的特性,现有工作未能有效地实现缓存数据的快速更新,忽略了缓存数据的时效性,从而导致缓存命中率不高.鉴于此,首先提出一种新的缓存存储结构,能够有效平衡最短路径的整体查询速度与缓存数据更新速度之间的关系;其次,结合路径共享能力及路径多样性设计了新的缓存存储策略,优化缓存收益,继而提高缓存命中率;最后,提出基于缓存的时变最短路径查询(cache-based time-varying shortest path query,CTSPQ)算法.在真实数据集上的实验结果验证了CTSPQ算法的有效性和可扩展性.
文献关键词：
最短路径查询;时变道路网;缓存技术;在线查询;位置服务
中图分类号：
作者姓名：
黄阳;周旭;杨志邦;余婷;张吉;曾源远;李肯立
作者机构：
湖南大学信息科学与工程学院 长沙410082;之江实验室 杭州 311100
文献出处：
引用格式：
[1]黄阳;周旭;杨志邦;余婷;张吉;曾源远;李肯立-.基于缓存的时变道路网最短路径查询算法)[J].计算机研究与发展,2022(02):376-389
A类：
时变道路网,CTSPQ
B类：
最短路径查询,路径查询算法,图论,基本操作,路径规划,GPS,个性化推荐,相关应用,计算成本,速度慢,缓存技术,边权重,缓存数据,快速更新,缓存命中率,存储结构,体查,数据更新,结合路径,共享能力,存储策略,cache,varying,shortest,path,query,真实数据,可扩展性,在线查询,位置服务
AB值：
0.276673
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
