Ultrafast Shortest-Path Queries via Transit Nodes.

H Bast, S Funke, D Matijevic�- The Shortest Path Problem, 2006 - books.google.com
The Shortest Path Problem, 2006books.google.com
We introduce the concept of transit nodes as a means for preprocessing a road network
such that point-to-point shortest-path queries can be answered extremely fast. We assume
the road network to be given as a graph, with coordinates for each node and a travel time for
each edge. The transit nodes are a set of nodes, as small as possible, with the property that
every non-local shortest path passes through at least one of these nodes. A path is called
non-local if its source and target are at least a certain minimal euclidean distance apart. We�…
Abstract
We introduce the concept of transit nodes as a means for preprocessing a road network such that point-to-point shortest-path queries can be answered extremely fast. We assume the road network to be given as a graph, with coordinates for each node and a travel time for each edge. The transit nodes are a set of nodes, as small as possible, with the property that every non-local shortest path passes through at least one of these nodes. A path is called non-local if its source and target are at least a certain minimal euclidean distance apart. We precompute the lengths of the shortest paths between each pair of transit nodes, and between each node in the graph and its few, closest transit nodes. Then every non-local shortest path query becomes a simple matter of combining information from a few table lookups. For the US road network, with about 24 million nodes and 29 million undirected edges, we achieve a worst-case query processing time of about 10 microseconds (not milliseconds) for 99% of all queries, namely the non-local ones. This improves over the best previously reported times by two orders of magnitude.
books.google.com
Showing the best result for this search. See all results