More Web Proxy on the site http://driver.im/

research-article

Terracost: Computing least-cost-path surfaces for massive grid terrains

Authors:

Jan Vahrenhold,

Rajiv WickremesingheAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 12

Article No.: 1.9, Pages 1 - 31

https://doi.org/10.1145/1227161.1370600

Published: 12 June 2008 Publication History

Abstract

This paper addresses the problem of computing least-cost-path surfaces for massive grid terrains. Consider a grid terrain T and let C be a cost grid for T such that every point in C stores a value that represents the cost of traversing the corresponding point in T. Given C and a set of sources S ∈ T, a least-cost-path grid Δ for T is a grid such that every point in Δ represents the distance to the source in S that can be reached with minimal cost. We present a scalable approach to computing least-cost-path grids. Our algorithm, terracost, is derived from our previous work on I/O-efficient shortest paths on grids and uses O(sort(n)) I/Os, where sort(n) is the complexity of sorting n items of data in the I/O-model of Aggarwal and Vitter. We present the design, the analysis, and an experimental study of terracost. An added benefit of the algorithm underlying terracost is that it naturally lends itself to parallelization. We have implemented terracost in a distributed environment using our cluster management tool and report on experiments that show that it obtains speedup near-linear with the size of the cluster. To the best of our knowledge, this is the first experimental evaluation of a multiple-source least-cost-path algorithm in the external memory setting.

References

[1]

Aggarwal, A. and Vitter, J. S. 1988. The input/output complexity of sorting and related problems. Communications of the ACM 31, 9 (Sept.), 1116--1127.]]

Digital Library

[2]

Agarwal, P. K., Arge, L., and Danner, A. 2006. From point cloud to grid dem: A scalable approach. In Progress in Spatial Data Handling: Proceedings of the 12th International Symposium on Spatial Data Handling. Springer, Berlin. 771--788.]]

[3]

Ajwani, D., Meyer, U., and Osipov, V. 2007. Improved external memory BFS implementations. In Proceedings of the 8th Workshop on Algorithm Engineering and Experimentation, 3--12.]]

[4]

Ajwani, D., Dementiev, R., and Meyer, U. 2006. A computational study of external memory BFS algorithms. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms. 601--610.]]

Digital Library

[5]

Arge, L. 2002. External memory data structures. In Handbook of Massive Data Sets. Kluwer, Boston, MA. 313--357.]]

Digital Library

[6]

Arge, L. 2003. The Buffer Tree: A technique for designing batched external data structures. Algorithmica 37, 1 (June), 1--24.]]

Digital Library

[7]

Arge, L. and Toma, L. 2004. Simplified external-memory algorithms for planar DAGs. In Algorithm Theory -- SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, T. Hagerup and J. Katajainen, Eds. Lecture Notes in Computer Science, vol. 3111. Springer, Berlin. 493--503.]]

[8]

Arge, L., Toma, L., and Vitter, J. S. 2001. I/O-efficient algorithms for problems on grid-based terrains. ACM Journal of Experimental Algorithmics 6, Article 1. 19 pp. An extended abstract appeared in the Proceedings of the 2nd Workshop on Algorithm Engineering and Experiments, 2000.]]

Digital Library

[9]

Arge, L., Meyer, U., Toma, L., and Zeh, N. 2003a. On external-memory planar depth first search. Journal of Graph Algorithms and Applications 7, 2, 105--129. An extended abstract appeared in the Proceedings of the 7th International Workshops of Algorithms and Data Structures, 2001.]]

Digital Library

[10]

Arge, L., Toma, L., and Zeh, N. 2003b. I/O-efficient topological sorting of planar DAGs. In Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures. 85--93.]]

Digital Library

[11]

Arge, L., Brodal, G. S., and Toma, L. 2004. On external memory MST, SSSP and multi-way planar graph separation. Journal of Algorithms 53, 2 (Nov.), 186--206. An extended abstract appeared in the Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, 2000.]]

Digital Library

[12]

Arge, L., Barve, R. D., Danner, A., Hutchinson, D., Molhave, T., Procopiuc, O., Toma, L., Vahrenhold, J., Vengroff, D. E., and Wickremesinghe, R. 2007a. TPIE user manual and reference, edition 1.0. Duke University, NC, http://www.cs.duke.edu/TPIE/ (In preparation).]]

[13]

Arge, L. A., Bender, M. A., Demaine, E. D., Holland-Minkley, B., and Munro, J. I. 2007b. An optimal cache-oblivious priority queue and its applications to graph algorithms. SIAM Journal on Computing 36, 6, 1672--1695. An extended abstract appeared in the Proceedings of the 34th Symposium on Theory of Computing, 2002.]]

Digital Library

[14]

Bast, H., Funke, S., Sanders, P., and Schultes, D. 2007. Fast routing in road networks with transit nodes. Science 316, 5824 (Apr.), 566.]]

[15]

Breimann, C. and Vahrenhold, J. 2003. External memory computational geometry revisited. In Algorithms for Memory Hierarchies, U. Meyer, P. Sanders, and J. Sibeyn, Eds. Lecture Notes in Computer Science, vol. 2625, Chapter 6, Springer, Berlin. 110--148.]]

[16]

Brengel, K., Crauser, A., Ferragina, P., and Meyer, U. 2000. An experimental study of priority queues in external memory. ACM Journal of Experimental Algorithmics 5 (Article 17).]]

Digital Library

[17]

Brodal, G. S., Fagerberg, R., and Vinther, K. 2004. Engineering cache-oblivious sorting algorithms. In Proceedings of the 6th Workshop on Algorithm Engineering and Experimentation, 4--17.]]

[18]

Brodal, G. S., Fagerberg, R., and Moruz, G. 2005. Cache-aware and cache-oblivious adaptive sorting. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, and M. Yung, Eds. Lecture Notes in Computer Science, vol. 3580. Springer, Berlin. 576--588.]]

Digital Library

[19]

Chan, T. M. 2006. All-pairs shortest paths for unweighted undirected graphs in o(mn) time. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms. 514--523.]]

Digital Library

[20]

Cherkassky, B. V., Goldberg, A. V., and Radzik, T. 1994. Shortest paths algorithms: Theory and experimental evaluation. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms. 516--525.]]

Digital Library

[21]

Chiang, Y.-J., Goodrich, M. T., Grove, E. F., Tamassia, R., Vengroff, D. E., and Vitter, J. S. 1995. External-memory graph algorithms. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms. 139--149.]]

Digital Library

[22]

Dementiev, R., Sanders, P., Schultes, D., and Sibeyn, J. F. 2004. Engineering an external memory minimum spanning tree algorithm. In Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science. 195--208.]]

[23]

Dementiev, R., Kettner, L., and Sanders, P. 2005. stxxl: Standard template library for XXL data sets. In Proceedings of the 13th European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 3669. Springer, Berlin. 640--651.]]

Digital Library

[24]

Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269--271.]]

Digital Library

[25]

Floyd, R. W. 1962. Algorithm 97: Shortest path. Communications of the ACM 5, 6 (June), 345.]]

Digital Library

[26]

Floyd, R. W. 1964. Algorithm 245: Treesort. Communications of the ACM 7, 12 (Dec.), 701.]]

Digital Library

[27]

Frigo, M., Leiserson, C. E., Prokop, H., and Ramachandran, S. 1999. Cache-oblivious algorithms. In Proceedings of the 40th Annual Symposium on the Foundations of Computer Science. IEEE Computer Press, Los Alamitos, CA. 285--299.]]

Digital Library

[28]

Goldberg, A. V. 2001. Shortest path algorithms: Engineering aspects. In Proceedings of the 12th International Symposium on Algorithms and Computation, P. Eades and T. Takaoka, Eds. Springer, Berlin. 502--513.]]

Digital Library

[29]

Goldberg, A. V. and Werneck, R. F. 2005. An efficient external memory shortest path algorithm. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments. 15 pp.]]

[30]

Goldberg, A. V. and Harrelson, C. 2005. Computing the shortest path: A&ast; search meets graph theory. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. 156--165.]]

Digital Library

[31]

Goldberg, A. V., Kaplan, H., and Werneck, R. F. 2006. Reach for A&ast;: Efficient point-to-point shortest path algorithms. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments. 15 pp.]]

[32]

Gutman, R. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments. 100--111.]]

[33]

Henzinger, M. R., Klein, P., Rao, S., and Subramanian, S. 1997. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences 55, 1 (Aug.), 3--23.]]

Digital Library

[34]

Holzer, M., Schulz, F., Wagner, D., and Willhalm, T. 2005. Combining speed-up techniques for shortest-path computations. ACM Journal of Experimental Algorithmics 10, 18 pp.]]

Digital Library

[35]

Holzer, M., Schulz, F., and Wagner, D. 2006. Engineering multi-level overlay graphs for shortest-path queries. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments. 156--170.]]

[36]

Jampala, H. and Zeh, N. 2005. Cache-oblivious planar shortest paths. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, and M. Yung, Eds. Lecture Notes in Computer Science, vol. 3580. Springer, Berlin. 563--575.]]

Digital Library

[37]

Klein, P. N. 2005. Multiple-source shortest paths in planar graphs. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 146--155.]]

Digital Library

[38]

Knuth, D. E. 1998. Sorting and Searching, 2nd ed. The Art of Computer Programming, vol. 3. Addison-Wesley, Reading, MA.]]

Digital Library

[39]

Köhler, E., Möhring, R. H., and Schilling, H. 2005. Acceleration of shortest path and constrained shortest path computation. In Proceedings of the 4th International Workshop on Experimental and Efficient Algorithms, S. E. Nikoletseas, Ed. Lecture Notes in Computer Science, vol. 3503. Springer, Berlin. 126--138.]]

Digital Library

[40]

Kramer, D. and MacInnis, M. 2004. Utilization of a local grid of Mac OS X-based computers using Xgrid. In Proceedings of the 13th IEEE International Symposium on High Performance Distributed Computing. IEEE Computer Society, Los Alamitos, CA. 264--265.]]

Digital Library

[41]

Kumar, V. and Schwabe, E. J. 1996. Improved algorithms and data structures for solving graph problems in external memory. In Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing. IEEE Computer Society, Los Alamitos, CA. 169--177.]]

Digital Library

[42]

LaMarca, A. and Ladner, R. E. 1996. The influence of caches of the performance of heaps. ACM Journal of Experimental Algorithmics 1, 32 pp.]]

Digital Library

[43]

Lambert, O. and Sibeyn, J. F. 1999. Parallel and external list ranking and connected components on a cluster of workstations. In Proceedings of the 11th International Conference Parallel and Distributed Computing and Systems. 454--460.]]

[44]

Lauther, U. 2004. 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. IfGI Prints, vol. 22. 219--230.]]

[45]

Maheshwari, A. and Zeh, N. 1999. External memory algorithms for outerplanar graphs. In Proceedings of the 10th International Symposium on Algorithms and Computation, A. Aggarwal and C. P. Rangan, Eds. Lecture Notes in Computer Science, vol. 1741. Springer, Berlin. 307--316.]]

Digital Library

[46]

Maheshwari, A. and Zeh, N. 2002. I/O-optimal algorithms for planar graphs using separators. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 372--381.]]

Digital Library

[47]

Mehlhorn, K. and Meyer, U. 2002. External-memory breadth-first search with sublinear I/O. In Proceedings of the 10th European Symposium on Algorithms, R. H. Möhring and R. Raman, Eds. Lecture Notes in Computer Science, vol. 2461. Springer, Berlin. 723--735.]]

Digital Library

[48]

Meyer, U. and Zeh, N. 2003. I/O-efficient undirected shortest paths. In Proceedings of the 11th European Symposium on Algorithms, G. Di Battista and U. Zwick, Eds. Lecture Notes in Computer Science, vol. 2832. Springer, Berlin. 434--445.]]

[49]

Meyer, U. and Zeh, N. 2006. I/O-efficient undirected shortest paths with unbounded weights. In Proceedings of the 14th European Symposium on Algorithms, Y. Azar and T. Erlebach, Eds. Lecture Notes in Computer Science, vol. 4168. Springer, Berlin. 540--551.]]

Digital Library

[50]

Möhring, R. H., Schilling, H., Schütz, B., Wagner, D., and Willhalm, T. 2005. Partitioning graphs to speed up Dijkstra's algorithm. In Proceedings of the 4th International Workshop on Experimental and Efficient Algorithms, S. E. Nikoletseas, Ed. Lecture Notes in Computer Science, vol. 3503. Springer, Berlin. 189--202.]]

Digital Library

[51]

Pettie, S. 2004. A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science 312, 1 (Jan.), 47--74.]]

Digital Library

[52]

Pettie, S. and Ramachandran, V. 2002. Computing shortest paths with comparisons and additions. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 267--276.]]

Digital Library

[53]

Pettie, S. and Ramachandran, V. 2005. A shortest path algorithm for real-weighted undirected graphs. SIAM Journal on Computing 34, 6, 1398--1431.]]

Digital Library

[54]

Pettie, S., Ramachandran, V., and Sridhar, S. 2002. Experimental evaluation of a new shortest path algorithm. In Proceedings of the 4th Workshop on Algorithm Engineering and Experiments, D. Mount and C. Stein, Eds. Lecture Notes in Computer Science, vol. 2409. Springer, Berlin. 126--142.]]

Digital Library

[55]

Sanders, P. 2000. Fast priority queues for cached memory. ACM Journal on Experimental Algorithmics 5 (Article 7).]]

Digital Library

[56]

Sibeyn, J. F., Abello, J., and Meyer, U. 2002. Heuristics for semi-external depth first search on directed graphs. In Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures. 282--292.]]

Digital Library

[57]

Thorup, M. 1997. Undirected single source shortest paths in linear time. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA. 12--21.]]

Digital Library

[58]

Vitter, J. S. 2001. External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys 33, 2 (June), 209--271.]]

Digital Library

[59]

Wagner, D. and Willhalm, T. 2005. Drawing graphs to speed up shortest-path computations. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments. 15--24.]]

Cited By

Sorokine AWhite DHardin A(2017)From Everywhere to Everywhere (FETE): Adaptation of a Pedestrian Movement Network Model to a Hybrid Parallel EnvironmentAdvances in Geocomputation10.1007/978-3-319-22786-3_31(347-353)Online publication date: 5-Jan-2017
https://doi.org/10.1007/978-3-319-22786-3_31
Etherington T(2016)Least-Cost Modelling and Landscape Ecology: Concepts, Applications, and OpportunitiesCurrent Landscape Ecology Reports10.1007/s40823-016-0006-91:1(40-53)Online publication date: 2-Jun-2016
https://doi.org/10.1007/s40823-016-0006-9
Roles JElAarag H(2013)A Smoothest Path algorithm and its visualization tool2013 Proceedings of IEEE Southeastcon10.1109/SECON.2013.6567453(1-6)Online publication date: Apr-2013
https://doi.org/10.1109/SECON.2013.6567453
Show More Cited By

Index Terms

Terracost: Computing least-cost-path surfaces for massive grid terrains

Recommendations

The weighted region problem: finding shortest paths through a weighted planar subdivision

The problem of determining shortest paths through a weighted planar polygonal subdivision with n vertices is considered. Distances are measured according to a weighted Euclidean metric: The length of a path is defined to be the weighted sum of (...
Improved algorithms for the k simple shortest paths and the replacement paths problems

Given a directed, non-negatively weighted graph G=(V,E) and s,t@?V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want ...
A Shortest Path Algorithm for Real-Weighted Undirected Graphs

We present a new scheme for computing shortest paths on real-weighted undirected graphs in the fundamental comparison-addition model. In an efficient preprocessing phase our algorithm creates a linear-size structure that facilitates single-source ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 12, Issue

2008

507 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/1227161

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2008

Accepted: 01 October 2007

Revised: 01 August 2007

Received: 01 December 2006

Published in JEA Volume 12

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
503
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sorokine AWhite DHardin A(2017)From Everywhere to Everywhere (FETE): Adaptation of a Pedestrian Movement Network Model to a Hybrid Parallel EnvironmentAdvances in Geocomputation10.1007/978-3-319-22786-3_31(347-353)Online publication date: 5-Jan-2017
https://doi.org/10.1007/978-3-319-22786-3_31
Etherington T(2016)Least-Cost Modelling and Landscape Ecology: Concepts, Applications, and OpportunitiesCurrent Landscape Ecology Reports10.1007/s40823-016-0006-91:1(40-53)Online publication date: 2-Jun-2016
https://doi.org/10.1007/s40823-016-0006-9
Roles JElAarag H(2013)A Smoothest Path algorithm and its visualization tool2013 Proceedings of IEEE Southeastcon10.1109/SECON.2013.6567453(1-6)Online publication date: Apr-2013
https://doi.org/10.1109/SECON.2013.6567453
Verma VSnoeyink JWolfson OAgrawal DLu C(2009)Reducing the memory required to find a geodesic shortest path on a large meshProceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/1653771.1653804(227-235)Online publication date: 4-Nov-2009
https://dl.acm.org/doi/10.1145/1653771.1653804
Lan-Kun Chung Yao-Min Fang Yin-Huei Chang Tien-Yin Chou Lee BHsiao-Yuen Yin Baranski B(2009)A SOA based debris flow monitoring system2009 17th International Conference on Geoinformatics10.1109/GEOINFORMATICS.2009.5293549(1-6)Online publication date: Aug-2009
https://doi.org/10.1109/GEOINFORMATICS.2009.5293549

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents