Fastest Path Query Answering using Time-Dependent Hop-Labeling in Road Network

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, and
FPP (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 the
2-hop labeling
approach, which is fast in answering shortest distance query in the static graph. However, it is hard to construct index for
SSFP
and
ISFP
because there are
$|\mathcal {T}|$
and
$|\mathcal {T}|^2$
possible time points and intervals, where
$\mathcal {T}$
is the time domain. Therefore, we first propose the
time-dependent hop-labeling
for
FPP
, then provide the specific optimizations for
SSFP
and
ISFP
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
AT-Dijkstra
and a
bottom-up
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.