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

article

I/O-Efficient Algorithms for Problems on Grid-Based Terrains

Authors:

Jeffrey Scott VitterAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 6

Pages 1 - es

https://doi.org/10.1145/945394.945395

Published: 31 December 2001 Publication History

Abstract

The potential and use of Geographic Information Systems is rapidly increasing due to the increasing availability of massive amounts of geospatial data from projects like NASA's Mission to Planet Earth. However, the use of these massive datasets also exposes scalability problems with existing GIS algorithms. These scalability problems are mainly due to the fact that most GIS algorithms have been designed to minimize internal computation time, while I/O communication often is the bottleneck when processing massive amounts of data. In this paper, we consider I/O-efficient algorithms for problems on grid-based terrains.Detailed grid-based terrain data is rapidly becoming available for much of the earth's surface. We describe [EQUATION] I/O algorithms for several problems on [EQUATION] grids for which only O(N) algorithms were previously known. Here M denotes the size of the main memory and B the size of a disk block.We demonstrate the practical merits of our work by comparing the empirical performance of our new algorithm for the flow accumulation problem with that of the previously best known algorithm. Flow accumulation, which models flow of water through a terrain, is one of the most basic hydrologic attributes of a terrain. We present the results of an extensive set of experiments on real-life terrain datasets of different sizes and characteristics. Our experiments show that while our new algorithm scales nicely with dataset size, the previously known algorithm "breaks down" once the size of the dataset becomes bigger than the available main memory. For example, while our algorithm computes the flow accumulation for the Appalachian Mountains in about three hours, the previously known algorithm takes several weeks.

References

[1]

NASA Earth Observing System (EOS) project, http://eos.nasa.gov/.]]

[2]

NASA Shuttle Radar Topography Mission (SRTM). http://www-radar.jpl.nasa.gov/srtm/.]]

[3]

U.S. Geological Survey: Five minute Gridded Earth Topography Data (ETOPO5). http://edewww.cr.usgs.gov/Webglis/glisbin/guide.pl/glis/hyper/guide/etopo5.]]

[4]

U.S. Geological Survey: Global thirty arc second Elevation Dataset (GTOPO30). http://edcwww.er.usgs.gov/landdaac/gtopo30/gtopo30.html.]]

[5]

U.S. Geological Survey (USGS) digital elevation models. http://mcmcweb.er.usgs.gov/status/dem_stat.html.]]

[6]

ABELLO, J., BUCHSBAUM, A. L., AND WESTBROOK., J.R. 1998. A functional approach to external graph algorithms. In Proc. Annual European Symposium on Algorithms, LNCS 1461 (1998), pp. 332-343.]]

Digital Library

[7]

AGARWAL, P. K., ARGE, L., MURALI, T. M., VARADARAJAN, K., AND VITTBR, J. S. 1998. I/O-efficient algorithms for contour line extraction and planar graph blocking. In Proc. ACM-SIAM Syrup. on Discrete Algorithms (1998), pp. 117-126.]]

Digital Library

[8]

AGGARWAL, A. AND VITTER, J.S. 1988. The Input/Output complexity of sorting and related problems. Communications off the ACM 31, 9, 1116-1127.]]

Digital Library

[9]

ARC/INFO. 1993. Understanding GIS--the ARC/INFO method. ARC/INFO. Rev. 6 for workstations.]]

[10]

ARGE, L. 1995a. The buffer tree: A new technique for optimal I/O-algorithms. In Proc. Workshop on Algorithms and Data Structures, LNCS 955 (1995), pp. 334-345. A complete version appears as BRICS technical report RS-96-28, University of Aarhus.]]

Digital Library

[11]

ARGE, L. 1995b. The I/O-complexity of ordered binary-decision diagram manipulation. In Proc. Int. Syrup. on Algorithms and Computation, LNCS 1004 (1995), pp. 82-91. A complete version appears as BlllCS technical report RS-96-29, University of Aarhus.]]

Digital Library

[12]

ARGE, L., BARVE, R., PROCOPIUC, O., TOMA, L., VENGROFF, D. E., AND WICKEREMESINGHE, R. 1999. TPIE User Manual and Reference (edition 0.9.01a). Duke University. The manual and software distribution are available on the web at http://www.cs.duke.edu/TPIE/.]]

[13]

ARGE, L., BRODAL, G. S., AND TOMA, L. 2000. On external memory MST, SSSP and multi-way planar graph separation. In Proc. Scandinavian Workshop on Algorithms Theory (2000).]]

Digital Library

[14]

BRENGEL, K., CRAUSER, A., FERRAGINA, P., AND MEYER, U. 1999. An experimental study of priority queues in external memory. In Proc. Workshop on Algorithm Engineering, LNCS 1668 (1999), pp. 345-358.]]

Digital Library

[15]

BRODAL, G. S. AND KATAJAINEN, J. 1998. Worst-case efficient external-memory priority queues. In Proc. Scandinavian Workshop on Algorithms Theory, LNCS 1432 (1998), pp. 107-118.]]

Digital Library

[16]

BUCHSBAUM, A. L., GOLDWASSER, M., VENKATASUBRAMANIAN, S., AND WESTBROOK, J. R. 2000. On external memory graph traversal. In Proc. ACM-SIAM Symp. on Discrete Algorithms (2000), pp. 859-860.]]

Digital Library

[17]

CHIANG, Y.-J, GOODRICH, M. T., GROVE, E. F., TAMASSIA, R., VENGROFF, D. E., AND VITTER, J.S. 1995. External-memory graph algorithms. In Proc. ACM-SIAM Symp. on Discrete Algorithms (1995), pp. 139-149.]]

Digital Library

[18]

DIJKSTHA, E.W. 1969. A note on two problems in connection with graphs. Numerische Mathematik.]]

[19]

FAIRFIELD, J. AND LEYMARIE, P. 1991. Drainage network from grid digital elevation model. Water Resource Research 27, 709-717.]]

[20]

FEUERSTEIN, E. AND MARCHETTI-SPACCAMELA, A. 1993. Memory paging for connectivity and path problems in graphs. LNCS 762, 416-425.]]

Digital Library

[21]

FRANK, A. U., PALMER, B., AND ROBINSON, V.B. 1986. Formal methods for the accurate definition of some fundamental terms in physical geography. In Proc. 2nd Int. Syrup. on Spatial Data Handling (1986), pp. 583-599.]]

[22]

FREDERICKSON, G.N. 1987. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal of Computing 16, 1004-1022.]]

Digital Library

[23]

HUTCHINSON, D., MAHESHWARI, A., AND ZEH, N. 1999. An external memory data structure for shortest path queries. In Proc. 5th Annual Int. Conf. Computing and Combinatorics, Number 1627 in LNCS (July 1999). Springer-Verlag.]]

[24]

KNUTH, D.E. 1998. Sorting and Searching (second ed.), Volume 3 of The Art of Computer Programming. Addison-Wesley, Reading MA.]]

Digital Library

[25]

KREVELD, M.V. 1997. Digital elevation models: overview and selected TIN algorithms. In M. VAN KREVELD, J. NIEVERGELT, T. ROOS, AND P. WIDMAYER Eds., Algorithmic Foundations of GIS. Springer-Verlag, Lecture Notes in Computer Science 1340.]]

[26]

KUMAR, V. AND SCHWABE, E. 1996. Improved algorithms and data: structures for solving graph problems in external memory. In Proc. IEEE Syrup. on Parallel and Distributed Processing (1996), pp. 169-177.]]

Digital Library

[27]

MAHESHWARI, A. AND ZEH, N. 1999. External memory algorithms for outerplanar graphs. Manuscript.]]

[28]

MOORE, I.D. 1996. Hydrologic Modeling and GIS, Chapter 26, pp. 143-148. GIS World Books. Boulder.]]

[29]

MOORE, I. D., GRAYSON, R. B., AND LADSON, A.R. 1991. Digital terrain modelling: a review of hydrological, geomorphological and biological aplications. Hydrological Processes 5, 3-30.]]

[30]

MOORE, I. D, TURNER, A. K., WILSON, J. P., JENSON, S. K., AND BAND, L.E. 1993. GIS and Environmental Modelling. Oxford University Press.]]

[31]

MUNAGALA, K. AND RANADE, A. 1999. I/O-complexity of graph algorithm. In Proc. ACM-SIAM Syrup. on Discrete Algorithms (1999), pp. 687-694.]]

Digital Library

[32]

NODINE, M. H., GOODRICH, M. T., AND VITTER, J.S. 1996. Blocking for external graph searching. Algorithmica 16, 2, 181-214.]]

[33]

O'CALLAGHAN, J. F. AND MARK, D. M. 1984. The extraction of drainage networks from digital elevation data. Computer Vision, Graphics and Image Processing 28.]]

[34]

ULLMAN, J. D. AND YANNAKAKIS, M. 1991. The input/output complexity of transitive closure. Annals of Mathematics and Artificial Intellegence 3, 331-360.]]

[35]

VENGROFF, D.E. 1994. A transparent parallel I/O environment. In Proc. DAGS Symposium on Parallel Computation (1994).]]

[36]

VITTER, .}. S. 1998. External memory algorithms (invited tutorial). In Proc. of the 1998 ACM Symposium on Principles of Database Systems (1998), pp. 119-128.]]

[37]

WOLOCK, D. 1993. Simulating the variable-source-area of streamflow generation with the watershed model topmodel. Technical report, U.S. Department of the Interior.]]

[38]

YU, S., VAN KREVELD, M., AND SNOEYINK, J. 1996. Drainage queries on TINs: from local to global and back again. In Proc. 7th Int. Symp. on Spatial Data Handling (1996), pp. 13A.I-13A.14.]]

Cited By

Arge LLowe ASvendsen SAgarwal P(2023)1D and 2D Flow Routing on a TerrainACM Transactions on Spatial Algorithms and Systems10.1145/35396609:1(1-39)Online publication date: 12-Jan-2023
https://dl.acm.org/doi/10.1145/3539660
van den Bout BJetten Vvan Westen CLombardo L(2023)A breakthrough in fast flood simulationEnvironmental Modelling & Software10.1016/j.envsoft.2023.105787168(105787)Online publication date: Oct-2023
https://doi.org/10.1016/j.envsoft.2023.105787
Méndez-Vázquez LLasa-Covarrubias RCerdeira-Estrada SLira-Noriega A(2022)Using Simulated Pest Models and Biological Clustering Validation to Improve Zoning Methods in Site-Specific Pest ManagementApplied Sciences10.3390/app1204190012:4(1900)Online publication date: 11-Feb-2022
https://doi.org/10.3390/app12041900
Show More Cited By

Index Terms

I/O-Efficient Algorithms for Problems on Grid-Based Terrains
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Communications management
        Input / output
        Process management
        Multiprocessing / multiprogramming / multitasking
        Process synchronization

Recommendations

Computing the drainage network on huge grid terrains
BigSpatial '12: Proceedings of the 1st ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data

We present a very efficient algorithm, named EMFlow, and its implementation to compute the drainage network, that is, the flow direction and flow accumulation on huge terrains stored in external memory. It is about 20 times faster than the two most ...
A Novel Method for Automatic Extracting Loess Positive and Negative Terrains Based on Grid DEMs
ICISE '09: Proceedings of the 2009 First IEEE International Conference on Information Science and Engineering

The Loess Positive and Negative Terrains (P-N terrains), which are separated by loess shoulder-lines obviously, are crucial parameters in constructing the mechanism-processing models of the loess landform drainage systems. This paper proposed a novel ...
Bridge detection in grid terrains and improved drainage enforcement
GIS '10: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems

Bare Earth gridded digital elevation models (DEMs) are often used to extract hydrologic features such as rivers and watersheds. DEMs must be conditioned by removing spurious sinks (or depressions) which impede water flow in the model, but are not true ...

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 6, Issue

2001

313 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/945394

Issue’s Table of Contents

Copyright © 2001 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: 31 December 2001

Published in JEA Volume 6

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
763
Total Downloads

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

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Arge LLowe ASvendsen SAgarwal P(2023)1D and 2D Flow Routing on a TerrainACM Transactions on Spatial Algorithms and Systems10.1145/35396609:1(1-39)Online publication date: 12-Jan-2023
https://dl.acm.org/doi/10.1145/3539660
van den Bout BJetten Vvan Westen CLombardo L(2023)A breakthrough in fast flood simulationEnvironmental Modelling & Software10.1016/j.envsoft.2023.105787168(105787)Online publication date: Oct-2023
https://doi.org/10.1016/j.envsoft.2023.105787
Méndez-Vázquez LLasa-Covarrubias RCerdeira-Estrada SLira-Noriega A(2022)Using Simulated Pest Models and Biological Clustering Validation to Improve Zoning Methods in Site-Specific Pest ManagementApplied Sciences10.3390/app1204190012:4(1900)Online publication date: 11-Feb-2022
https://doi.org/10.3390/app12041900
Lowe ASvendsen SAgarwal PArge L(2020)1D and 2D Flow Routing on a TerrainProceedings of the 28th International Conference on Advances in Geographic Information Systems10.1145/3397536.3422269(5-14)Online publication date: 3-Nov-2020
https://dl.acm.org/doi/10.1145/3397536.3422269
Franklin Wde Magalhães SAndrade M(2018)Data Structures for Parallel Spatial Algorithms on Large Datasets (Vision paper)Proceedings of the 7th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data10.1145/3282834.3282839(16-19)Online publication date: 6-Nov-2018
https://dl.acm.org/doi/10.1145/3282834.3282839
Fife TOxley J(2017)Laminar matroidsEuropean Journal of Combinatorics10.1016/j.ejc.2017.01.00262:C(206-216)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.ejc.2017.01.002
Vuduc RDemmel JBilmes J(2016)Statistical Models for Empirical Search-Based Performance TuningThe International Journal of High Performance Computing Applications10.1177/109434200404129318:1(65-94)Online publication date: 26-Jul-2016
https://doi.org/10.1177/1094342004041293
Alexander CArge LBøcher PRevsbæk MSandel BSvenning JTsirogiannis CYang J(2016)Computing River Floods Using Massive Terrain DataGeographic Information Science10.1007/978-3-319-45738-3_1(3-17)Online publication date: 14-Sep-2016
https://doi.org/10.1007/978-3-319-45738-3_1
Su CYu WFeng CYu CHuang ZZhang X(2015)An Efficient Algorithm for Calculating Drainage Accumulation in Digital Elevation Models Based on the Basin Tree IndexIEEE Geoscience and Remote Sensing Letters10.1109/LGRS.2014.234556112:2(424-428)Online publication date: Feb-2015
https://doi.org/10.1109/LGRS.2014.2345561
Yao YShi X(2015)Alternating scanning orders and combining algorithms to improve the efficiency of flow accumulation calculationInternational Journal of Geographical Information Science10.1080/13658816.2015.102720929:7(1214-1239)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1080/13658816.2015.1027209
Show More Cited By

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.

Media

Figures

Other

Tables

View Issue’s Table of Contents