Monitoring minimum cost paths on road networks

ABSTRACT

On a road network, the minimum cost path (or min-cost path for short) from a source location to a destination is a path with the smallest travel cost among all possible paths. Despite that min-cost path queries on static networks have been well studied, the problem of monitoring min-cost paths on a road network in presence of updates is not fully explored. In this paper, we present PathMon, an efficient system for monitoring min-cost paths in dynamic road networks. PathMon addresses two important issues of the min-cost path monitoring problem, namely, (i) path invalidation that identifies min-cost paths returned to path queries affected by network changes, and (ii) path update that replaces invalid paths with new ones for those affected path queries. For (i), we introduce the notion of query scope, based on which a query scope index (QSI) is developed to identify affected path queries. For (ii), we devise a partial path computation algorithm (PPCA) to quickly recompute the updated paths. Through a comprehensive performance evaluation by simulation, QSI and PPCA are demonstrated to be effective on the path invalidation and path update issues.

References

1. R. Bellman. On a Routing Problem. Quarterly of Applied Mathematics, 16(1):87--90, 1958.
2. D. P. Bertsekas. A Simple and Fast Label Correcting Algorithm for Shortest Paths. Networks, 23:703--709, 1993.
3. E. Dijkstra. A Note on Two Problems in Connection with Graphs. Numerical Mathematics, 1959.
4. R. W. Floyd. Algorithm 97: Shortest Path. Communications of the ACM, 5(6), 1962.
5. A. Segali. Distributed network protocols. IEEE Transaction on Information Theory, 29, 1983.
6. R. Seidel. On the All-Pairs-Shortest-Path Problem. In STOC'92, pages 745--749, 1992.
7. A. O. et al. Minimum Delay Routing in Stochastic Networks. IEEE/ACM Transaction on Networking, 1(2), 1993.
8. B. D. et al. Finding Time-Dependent Shortest Paths over Large Graphs. In EDBT'08, pages 205--216.
9. C.-C. L. et al. Continuous Evaluation of Fastest Path Queries on Road Networks. In SSTD'07, pages 20--37, 2007.
10. D. F. et al. Fully Dynamic Output Bounded Single Source Shortest Path Problem. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pages 212--221, 1996.
11. E. K. et al. Finding Fastest Paths on A Road Network with Speed Patterns. In ICDE'06.
12. H. G. et al. Adaptive Fastest Path Computation on a Road Network: A Traffic Mining Approach. In VLDB'07, pages 794--805.
13. J. M. M. et al. The new routing algorithm for the ARPANet. IEEE Transaction on Communications, 28(5):711--719, 1980.
14. N. J. et al. Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation. TKDE, 10(3):409--432, 1998.
15. P. N. et al. New Dynamic Algorithms for Shortest Path Tree Computation. IEEE/ACM Transaction on Networking, 8(6):734--746, 2000.
16. R. D. et al. Generalized Best-First Search Strategies and the Optimality of A*. Journal of ACM, 32(3):505--536, 1985.
17. R. H. M. et al. Partitioning Graphs to Speedup Dijkstraąs Algorithm. In ACM Journal of Experimental Algorithmics, volume 11, pages 1--29, 2006.
18. S. J. et al. An Efficient Path Computation Model for Hierarchically Structured Topographical Road Maps. TKDE, 14(5):1029--1046, 2002.
19. S. S. et al. CCAM: A connectivity-clustered access method for networks and network computations. Transaction on Knowledge and Data Engineering, 9(1):102--119, 1997.

Index Terms

• Human-centered computing

  • Visualization

    • Visualization application domains

      • Geographic visualization

• Information systems

  • Information systems applications

    • Spatial-temporal systems