Fastest Path Query Answering using Time-Dependent Hop-Labeling in Road Network
Lei Li, Sibo Wang, Xiaofang Zhou
Abstract
Finding the fastest path in the time-dependent road network is time consuming because its problem complexity is <inline-formula><tex-math notation="LaTeX">$\Omega (T(|V|\log |V|+|E|))$</tex-math></inline-formula> , where <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> is the size of the result's time-dependent function, <inline-formula><tex-math notation="LaTeX">$|V|$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$|E|$</tex-math></inline-formula> are the number of vertices and edges. There are three kinds of fastest path problems: <i>SSFP (Single-Staring Time Fastest Path)</i> that has a fixed departure time, <i>ISFP (Interval-Staring Time Fastest Path)</i> that selects the best departure time from an interval, and <i>FPP (Fastest Path Profile)</i> 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 the <i>2-hop labeling</i> approach, which is fast in answering shortest distance query in the static graph. However, it is hard to construct index for <i>SSFP</i> and <i>ISFP</i> because there are <inline-formula><tex-math notation="LaTeX">$|\mathcal {T}|$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$|\mathcal {T}|^2$</tex-math></inline-formula> possible time points and intervals, where <inline-formula><tex-math notation="LaTeX">$\mathcal {T}$</tex-math></inline-formula> is the time domain. Therefore, we first propose the <i>time-dependent hop-labeling</i> for <i>FPP</i> , then provide the specific optimizations for <i>SSFP</i> and <i>ISFP</i> query 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 technique <i>AT-Dijkstra</i> and a <i>bottom-up</i> compression 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.