TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing (CROSBI ID 54240)
Prilog u knjizi | izvorni znanstveni rad
Podaci o odgovornosti
Bast, Holger ; Funke, Stefan ; Matijević, Domagoj
engleski
TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing
We introduce the concept of 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 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.
Shortest paths, Transit nodes, Road maps
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
175-192.
objavljeno
Podaci o knjizi
The Shortest Path Problem: Ninth DIMACS Implementation Challenge
Demetrescu, Camil ; Goldberg, Andrew V. ; Johnson, David S.
New York (NY): American Mathematical Society (AMS)
2009.
0-8218-4383-4