Naslov
In Transit to Constant Time Shortest-Path Queries in Road Networks

Autori
Bast, Holger ; Funke, Stefan ; Matijević, Domagoj ; Sanders, Peter ; Schultes, Dominik

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

Izvornik
Proceedings of 9th Workshop on Algorithm Enginneering and Experiments / Applegate, David ; Brodal, Gerth - Philadelphia (PA) : SIAM, 2007, 46-59

Skup
9th Workshop on Algorithm Enginneering and Experiments (ALENEX'07)

Mjesto i datum
New Orleans (LA), Sjedinjene Američke Države, 06.01.2006

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
shortest paths

Sažetak
When you drive to somewhere ‘ far away’ , you will leave your current location via one of only a few ‘ important’ traffic junctions. Starting from this informal observation, we develop an algorithmic approach— transit node routing— that allows us to reduce quickest-path queries in road networks to a small number of table lookups. We present two implementations of this idea, one based on a simple grid data structure and one based on highway hierarchies. For the road map of the United States, our best query times improve over the best previously published figures by two orders of magnitude. Our results exhibit various trade-offs between average query time (5 μ s to 63 μ s), preprocessing time (59min to 1200min), and storage overhead (21 bytes/node to 244 bytes/node).

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA