# Highway Dimension: From Practice to Theory and Back

## Andrew V. Goldberg, Microsoft Research

Computing driving directions has motivated many shortest path
heuristics that answer queries on continental-scale networks, with tens
of millions of intersections, in real time. The underlying algorithms
are intuitive, but until recently there was no theoretical explanation
of their performance. We review some of these algorithms and give the
first theoretical analysis for them on a non-trivial class of
networks.

For our analysis, we introduce the notion of highway dimension. The
analysis works for networks with low highway dimension and gives a
unified explanation of algorithms' good performance. Our analysis
explores an unexpected relationship to VC-dimension and learning theory
and applies the latter to graph algorithm design.

We also propose a new algorithm that achieves a better theoretical
time bound and is in the spirit of labeling algorithms for approximate
shortest paths from the distributed computing literature. Our
experiments show that an implementation of this algorithm is extremely
fast in practice, validating the theoretical prediction.

(Joint work with Ittai Abraham, Amos Fiat, and Renato Werneck.)