ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2022, Vol. 59 ›› Issue (2): 376-389.doi: 10.7544/issn1000-1239.20210892

所属专题: 2022空间数据智能专题

• 人工智能 • 上一篇    下一篇

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

黄阳1,周旭1,杨志邦1,余婷2,张吉2,曾源远1,李肯立1   

  1. 1(湖南大学信息科学与工程学院 长沙 410082);2(之江实验室 杭州 311100) (hy19@hnu.edu.cn)
  • 出版日期: 2022-02-01
  • 基金资助: 
    国家自然科学基金项目(62172146,61802032,61772182,62172157);之江实验室开放课题(2021KD0AB02);湖南省自然科学基金项目(2020JJ4220,2020JJ5083);湖南省科技创新计划项目(2020RC2032)

Cache-Based Shortest Path Query Algorithm for Time-Varying Road Networks

Huang Yang1, Zhou Xu1, Yang Zhibang1, Yu Ting2, Zhang Ji2, Zeng Yuanyuan1, Li Kenli1   

  1. 1(College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082);2(Zhejiang Lab, Hangzhou 311100)
  • Online: 2022-02-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (62172146, 61802032, 61772182, 62172157), Zhejiang Lab Open Project (2021KD0AB02), the Natural Science Foundation of Hunan Province (2020JJ4220, 2020JJ5083), and the Science and Technology Innovation Program of Hunan Province (2020RC2032).

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

关键词: 最短路径查询, 时变道路网, 缓存技术, 在线查询, 位置服务

Abstract: As one of the fundamental operations in graph theory, the shortest path query has been extensively applied to the related applications based on road networks, including GPS navigation and personalized recommendation. In view of the high computational cost and slow query speed faced by the use of servers in the road network to query the shortest path online, the existing solutions usually utilize caching technology to optimize their performance. Considering that the edge weight of the road network has the characteristics of frequent changes, the existing related work failed to effectively realize the rapid update of cached data, then ignored the timeliness of the shortest path in the cache, which led to a decrease in the cache hit ratio. In view of this, we first propose a new cache storage structure that effectively balances the relationship between the overall query speed of the shortest path and the cache data update speed; Secondly, we propose a cache storage strategy that combines path sharing abilities and path diversity to optimize cache revenue and improve cache hit ratio; Finally, we propose a cache-based time-varying shortest path query (CTSPQ) algorithm based on the storage structure to improve the speed of querying the shortest path in the cache. A great deal of experiments on real data sets prove the effectiveness and scalability of the proposed techniques.

Key words: shortest path query, time-varying road network, caching technology, online query, location-based services

中图分类号: