Fastest Path Query Answering using Time-Dependent Hop-Labeling in Road Network
Lei Li, Sibo Wang, Xiaofang Zhou · IEEE Transactions on Knowledge and Data Engineering · 2020
Finding the fastest path in the time-dependent road network is time consuming because its problem complexity is$\Omega (T(|V|\log |V|+|E|))$, where$T$is the size of the result's time-dependent function,$|V|$and$|E|$are the number of vertices and edges. There are three kinds of fastest path problems:SSFP (Single-Staring Time Fastest Path)that has a fixed departure time,ISFP (Interval-Staring Time Fastest Path)that selects the best departure time from an interval, andFPP (Fastest Path Profile)that returns the travel time of the entire time domain. In this paper, we aim to answer these three queries in time-dependent road network faster by extending the2-hop labelingapproach, which is fast in answering shortest distance query in the static graph. However, it is hard to construct index forSSFPandISFPbecause there are$|\mathcal {T}|$and$|\mathcal {T}|^2$possible time points and intervals, where$\mathcal {T}$is the time domain. Therefore, we first propose thetime-dependent hop-labelingforFPP, then provide the specific optimizations forSSFPandISFPquery answering. Moreover, it is both time and space consuming to build an index in a large time-dependent graph, so we partition road network into smaller sub-graphs and build indexes within and between the partitions. Furthermore, we propose an online approximation techniqueAT-Dijkstraand abottom-upcompression method to further reduce the label size, save construction time and speedup query answering. Experiments on real world road network show that our approach outperforms the state-of-art fastest path index approaches and can speed up the query answering by hundreds of times.