Abstract
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.
Original language | English |
---|---|
Title of host publication | Proceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022 |
Number of pages | 13 |
Publisher | IEEE |
Publication date | 2022 |
Pages | 2372-2384 |
ISBN (Electronic) | 9781665408837 |
DOIs | |
Publication status | Published - 2022 |
Event | 38th IEEE International Conference on Data Engineering, ICDE 2022 - Virtual, Online, Malaysia Duration: 9 May 2022 → 12 May 2022 |
Conference
Conference | 38th IEEE International Conference on Data Engineering, ICDE 2022 |
---|---|
Country/Territory | Malaysia |
City | Virtual, Online |
Period | 09/05/2022 → 12/05/2022 |
Series | Proceedings - International Conference on Data Engineering |
---|---|
Volume | 2022-May |
ISSN | 1084-4627 |
Bibliographical note
Publisher Copyright:© 2022 IEEE.