A New Dynamic Graph Data Structure for Large-Scale Transportation Networks

We present a new graph data structure specifically suited for large-scale dynamic transportation networks. Our graph structure provides simultaneously three unique features: compactness, agility and dynamicity. All previously known graph structures were lacking support in at least one of the aforementioned features and/or could not be efficiently applied in large-scale dynamic transportation networks. We demonstrate the practicality of our new graph structure by conducting an experimental study for shortest route planning in large-scale European road networks with a few dozen millions of nodes and edges. Using classical shortest path routing algorithms, we can easily achieve point-to-point query times in the order of milliseconds, while our new graph structure can be updated in just a few microseconds after a node or edge insertion or deletion.