Highway Dimension: From Practice to Theory and Back



Andrew Goldberg

Monday November 22 , 2010
4:00 PM,
5130 Upson Hall



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