TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing
Holger Bast, Stefan Funke, Domagoj Matijevic
We introduce the concept of \emph{transit nodes}, as a means for preprocessing
a road network, with given coordinates for each node and a travel time for
each edge, such that point-to-point shortest-path queries can be answered
extremely fast.
The transit nodes are a set of nodes, as small as possible, with the property
that every shortest path that is \emph{non-local} in the sense that it covers
a certain not too small euclidean distance passes through at least on of these
nodes. With such a set and precomputed distances from each node in the graph
to its few, closest transit nodes, every non-local shortest path query becomes
a simple matter of combining information from a few table lookups.
For the US road network, which has about 24 million nodes and 58 million
edges, we achieve a worst-case query processing time of about 10 microseconds
(not milliseconds) for 99\% of all queries. This improves over the best
previously reported times by two orders of magnitude.
PDF