efficient data management in support of shortest-path computation
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 management 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 network 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.
shortest path computation openstreetmap cell manager hba