Double Hierarchical Labeling Shortest Distance Querying in Time-dependent Road Networks
Authors:
- 1 April 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2077-2089
Abstract
A shortest distance query is a fundamental operation of various real-time response applications in time-dependent road networks. Unfortunately, existing methods (e.g., G-treelike, 2-hop labeling-like) are prohibitively expensive in terms of space/time. To this end, we propose a novel Double Hierarchical Labeling (DHL) index, which consists of a Hierarchical Graph Partition (HGP) tree and a hierarchical border labeling list. For HGP-tree, we first use a hierarchical graph partitioning to split the entire road network into hierarchical subgraphs and then index these subgraphs by a balanced tree. To preserve all connectivity information between border vertices of subgraphs, a Time-based Distance Inverted File (TDIF) is constructed for each leaf node of the HGP-tree. For the hierarchical labeling list, we construct it only for border vertices and use it to speed up query processing. Moreover, a label propagation update is proposed to manage label updating when weights change. Finally, we propose a phase-aware search algorithm for different search situations between given query vertices to guarantee query efficiency. Extensive experiments are conducted to demonstrate the superiority of the proposed proposals on query processing and index maintenance.Keywords
Funding Information
- National Science Foundation
- Renmin University of China
- Natural Science Foundation of Hebei Province
This publication has 27 references indexed in Scilit:
- G-Tree: An Efficient and Scalable Index for Spatial Search on Road NetworksIEEE Transactions on Knowledge and Data Engineering, 2015
- IS-LabelProceedings of the VLDB Endowment, 2013
- TEDI2011
- BidirectionalA* search on time‐dependent road networksNetworks, 2011
- Online Computation of Fastest Path in Time-Dependent Spatial Networks2011
- Time-Dependent SHARC-RoutingAlgorithmica, 2009
- Scalable network distance browsing in spatial databases2008
- Query Processing in Spatial Network Databases2003
- Reachability and Distance Queries via 2-Hop LabelsSIAM Journal on Computing, 2003
- A note on two problems in connexion with graphsNumerische Mathematik, 1959