  Given two locations $s$ and $t$ in a road network, a distance query returns
the minimum network distance from $s$ to $t$, while a shortest path query
computes the actual route that achieves the minimum distance. These two types
of queries find important applications in practice, and a plethora of solutions
have been proposed in past few decades. The existing solutions, however, are
optimized for either practical or asymptotic performance, but not both. In
particular, the techniques with enhanced practical efficiency are mostly
heuristic-based, and they offer unattractive worst-case guarantees in terms of
space and time. On the other hand, the methods that are worst-case efficient
often entail prohibitive preprocessing or space overheads, which render them
inapplicable for the large road networks (with millions of nodes) commonly used
in modern map applications.
  This paper presents {\em Arterial Hierarchy (AH)}, an index structure that
narrows the gap between theory and practice in answering shortest path and
distance queries on road networks. On the theoretical side, we show that, under
a realistic assumption, AH answers any distance query in $\tilde{O}(\log \r)$
time, where $\r = d_{max}/d_{min}$, and $d_{max}$ (resp.\ $d_{min}$) is the
largest (resp.\ smallest) $L_\infty$ distance between any two nodes in the road
network. In addition, any shortest path query can be answered in $\tilde{O}(k +
\log \r)$ time, where $k$ is the number of nodes on the shortest path. On the
practical side, we experimentally evaluate AH on a large set of real road
networks with up to twenty million nodes, and we demonstrate that (i) AH
outperforms the state of the art in terms of query time, and (ii) its space and
pre-computation overheads are moderate.
