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, and with very low storage overhead.
We give the first theoretical analysis of several underlying algorithms on a non-trivial class of networks. To do this, we introduce the notion of highway dimension. Our analysis works for networks with low highway dimension and gives a unified explanation of good performance for several seemingly different algorithms.
Joint work with Ittai Abraham, Amos Fiat, and Renato Werneck
Date and Time
Wednesday October 14, 2009 4:30pm -
5:30pm
Location
Computer Science Small Auditorium (Room 105)
Event Type
Speaker
Andrew Goldberg, from Microsoft Research - Silicon Valley
Host
Robert Tarjan