Journal of Frontiers of Computer Science and Technology ›› 2023, Vol. 17 ›› Issue (5): 1210-1224.DOI: 10.3778/j.issn.1673-9418.2111064

• Big Data Technology • Previous Articles    

TD-H2H: Shortest Path Query on Time-Dependent Graphs

LI Xinling, WANG Yishu, YUAN Ye, GU Xiang, WANG Guoren   

  1. 1. School of Computer Science and Engineering, Northeastern University, Shenyang 110167, China
    2. School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, China
  • Online:2023-05-01 Published:2023-05-01

TD-H2H:时序图上的最短路径查询

李新玲,王一舒,袁野,谷香,王国仁   

  1. 1. 东北大学 计算机科学与工程学院,沈阳 110167
    2. 北京理工大学 计算机学院,北京 100081

Abstract: A shortest path query on road networks is a fundamental problem, which has been studied widely. Existing studies usually model road networks as a static graph and query the path with the shortest distance between given vertices. However, a road network has time-dependent property, so modeling the road network as a time-dependent graph is more realistic. Compared with the static graph, the time-dependent graph is larger and more complex, which increases the difficulty of time-dependent shortest path query. The time-dependent shortest path refers to the path with the shortest travel time between a source and a destination in a time-dependent graph under a given departure time. Therefore, the result of the time-dependent shortest path is impacted by the given departure time, which brings a new challenge for the query. These difficulties and challenges make the traditional shortest path algorithms not applicable to the time-dependent shortest path query. This paper employs a time-dependent graph to model the road network, and TD-H2H (time dependent-hierarchical 2-hop) index is proposed based on the tree decomposition, which can be used to quickly and accurately solve the time-dependent shortest path problem. Firstly, a time-dependent tree decomposition algorithm based on the traditional tree decomposition is presented to transform the time-dependent graph into a tree structure. Then, the index structure is quickly determined by tree decomposition, and an efficient index construction algorithm is proposed, denoted as TD-H2H. Finally, based on the TD-H2H index, an efficient time-dependent shortest path query algorithm is designed, named as TD-OAI. Experiments with existing algorithms are performed on 4 real-world datasets. Experimental results show that the query speed of the proposed algorithm is 1 to 2 orders of magnitude better than existing algorithms, and prove the effectiveness and efficiency of the proposed algorithms.

Key words: time-dependent graph, road network, tree decomposition, time-dependent index, shortest path

摘要: 道路网络上的最短路径查询是一个已经被广泛研究的基本问题。现有的研究通常将道路网络建模为静态图,查询给定节点间距离最短的路径。然而,道路网络具有时序性,将道路网络建模为时序图更符合实际情况。与静态图相比,时序图的规模更大,结构也更为复杂,增加了时序最短路径的查询难度。时序最短路径是指在给定出发时间下,时序图上源节点和目的节点之间旅行时间最短的路径。因此,时序最短路径的结果受给定出发时间影响,为时序最短路径的查询带来了新的挑战,传统的最短路径算法不适用于时序最短路径的查询。将道路网络建模为时序图,并基于树分解提出了TD-H2H索引,利用该索引可以快速准确地实现时序最短路经查询。首先,研究了时序图上的树分解问题,提出时序树分解算法,将图结构转变为树结构。然后,通过树分解快速确定索引结构,提出了高效的索引构建算法,用以构建TD-H2H索引。最后,基于TD-H2H设计了高效的最短路径查询算法TD-OAI。在4个真实公开的数据集上与现有算法进行了实验,结果表明提出算法的查询效率优于现有算法1~2个数量级,证明了提出算法的有效性和效率。

关键词: 时序图, 道路网络, 树分解, 时序索引, 最短路径