TerraCost: a versatile and scalable approach to computing least-cost-path surfaces for massive grid-based terrains

ABSTRACT

This paper addresses the problem of computing least-cost-path surfaces for massive grid-based terrains. Our approach follows a modular design, enabling the algorithm to make efficient use of memory, disk, and grid computing environments. We have implemented the algorithm in the context of the GRASS open source GIS system and---using our cluster management tool---in a distributed environment. We report experimental results demonstrating that the algorithm is not only of theoretical and conceptual interest but also performs well in practice. Our implementation outperforms standard solutions as dataset size increases relative to available memory and our distributed solver obtains near-linear speedup when preprocessing large terrains for multiple queries.

References

1. A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Comm. ACM, 31(9):1116--1127, Sept. 1988.
2. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
3. L. Arge. External memory data structures. In Handbook of Massive Data Sets. Kluwer, 2002. 313--357.
4. L. Arge, R. D. Barve, D. Hutchinson, O. Procopiuc, L. Toma, D. E. Vengroff, and R. Wickremesinghe. TPIE user manual and reference, edition 0.9.01a. Duke University, NC, http://www.cs.duke.edu/TPIE/, 1999.
5. L. Arge, L. Toma, and J. S. Vitter. I/O-efficient algorithms for problems on grid-based terrains. ACM J. Experimental Algorithmics, 6, 2001. Article 1.
6. L. Arge, L. Toma, and N. Zeh. I/O-efficient topological sorting of planar DAGs. In Proc. Symp. on Parallel Algorithms and Architectures, pages 85--93, 2003.
7. C. Breimann and J. Vahrenhold. External memory computational geometry revisited. In U. Meyer, P. Sanders, and J. Sibeyn, editors, Algorithms for Memory Hierarchies, volume 2625 of LNCS, chapter 6, pages 110--148. Springer, 2003.
8. Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-memory graph algorithms. In Proc. Symp. on Discrete Algorithms, pages 139--149, 1995.
9. E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.
10. R. W Floyd. Algorithm 97: Shortest path. Comm. ACM, 5(6):345, June 1962.
11. A. V. Goldberg and C. Harrelson. Computing the shortest path: A* search meets graph theory. In Proc. Symp. on Discrete Algorithms, pages 156--165, 2005.
12. A. V. Goldberg and R. F. Werneck. An efficient external memory shortest path algorithm. In Proc. Workshop on Algorithm Engineering and Experiments, pages 26--40, 2005.
13. R. Gutman. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proc. Workshop on Algorithm Engineering and Experiments, 2004. 100--111.
14. E. Köhler, R. H. Möhring, and H. Schilling. Acceleration of shortest path and constrained shortest path computation. In Proc. Workshop on Efficient and Experimental Algorithms, pages 126--138, 2005.
15. V. Kumar and E. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. In Proc. Symp. on Parallel and Distributed Processing, pages 169--177, 1996.
16. U. Lauther. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Geoinformation und Mobilität - von der Forschung zur praktischen Anwendung. Beiträge zu den Münsteraner GI-Tagen, volume 22 of IfGI Prints, pages 219--230, 2004.
17. R. H. Möhring, H. Schilling, B. Schütz, D. Wagner, and T. Willhalm. Partitioning graphs to speed up Dijkstra's algorithm. In Proc. Workshop on Efficient and Experimental Algorithms, pages 189--202, 2005.
18. J. S. Vitter. External memory algorithms and data structures: Dealing with massive data. ACM Comp. Surveys, 33(2):209--271, June 2001.
19. D. Wagner and T. Willhalm. Drawing graphs to speed up shortest-path computations. In Proc. Workshop on Algorithm Engineering and Experiments, pages 17--25, 2005.

Index Terms

• Information systems

  • Information systems applications

• Theory of computation

  • Design and analysis of algorithms