Workload-Aware Shortest Path Distance Querying in Road Networks

• Main Authors: Zheng, Bolong, Wan, Jingyi, Gao, Yongyong, Ma, Yong, Huang, Kai, Zhou, Xiaofang, Jensen, Christian S.
• Format: Conference Proceeding
• Language: English
• Subjects: Computational efficiency; Data engineering; Partitioning algorithms; Proposals; Query processing; Reinforcement learning; Roads
• ISSN: 2375-026X
• DOI: 10.1109/ICDE53745.2022.00223

Computing shortest-path distances in road networks is core functionality in a range of applications. To enable the efficient computation of such distance queries, existing proposals frequently apply 2-hop labeling that constructs a label for each vertex and enables the computation of a query by performing only a linear scan of labels. However, few proposals take into account the spatio-temporal characteristics of query workloads. We observe that real-world workloads exhibit (1) spatial skew, meaning that only a small subset of vertices are queried frequently, and (2) temporal locality, meaning that adjacent time intervals have similar query distributions. We propose a Workload-aware Core-Forest label index (WCF) to exploit spatial skew in workloads. In addition, we develop a Reinforcement Learning based Time Interval Partitioning (RL-TIP) algorithm that exploits temporal locality to partition workloads to achieve further performance improvements. Extensive experiments with real-world data offer insights into the performance of the proposals, showing that they achieve 62% speedup on average for query processing with less preprocessing time and space overhead when compared with the state-of-the-art proposals.