Efficient Shortest Distance Query Processing in Road Networks for Spatially Skewed Workloads
Jingyi Wan · 2021
Shortest distance computing in road networks is an essential component in a range of applications. As a well-adopted method, 2-hop labeling assigns each vertex a label and enables the distance computation only by a sort-merge join on the labels. However, few existing 2-hop labeling based proposals consider the spatio-temporal characteristics of dynamic query workloads. To process massive-scale shortest distance query workloads, 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) that utilizes temporal locality to further improve the query performance. Extensive experiments on real-world data demonstrate that our proposal is capable of achieving a query processing speedup of an order of magnitude with less preprocessing time and space, when compared to the state-of-the-art proposals.