Naslov
TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing

Autori
Bast, Holger ; Funke, Stefan ; Matijević, Domagoj

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
9th DIMACS Implementation Challenge --- Shortest Path / Demetrescu, Camil ; Goldberg, Andrew ; Johnson, David - , 2006

Skup
9th DIMACS Implementation Challenge --- Shortest Path

Mjesto i datum
Piscataway (NJ), Sjedinjene Američke Države, 13.11.2006. - 14.11.2006

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
shortest paths; transit nodes

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA