Efficient Data Management in Support of Shortest-Path Computation Full text

Alexandros Efentakis, Dieter Pfoser, Agnes Voisard
4th ACM SIGSPATIAL International Workshop on Computational Transportation Science
Abstract. While many efficient proposals exist for solving the single-pair shortest-path problem, a solution that sees the algorithmic solution in combination with efficient data management has received considerably smaller attention. This work proposes a data manage- ment approach for efficient shortest path computation that exploits road network hierarchies and allow us to minimize the portion of the network that is kept in main memory. The proposed approach is insensitive to network changes as it does not rely on any pre-computation, but only on given road net- work properties. In that we specifically target large road networks that exhibit a high degree of change (e.g., OpenStreetMap). Extensive experimental evaluation shows that the presented solution is both efficient and scalable and provides competitive shortest-path computation performance without requiring a preprocessing stage for the road network graph.