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

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: James Abello , Adam L. Buchsbaum , Jeffery Westbrook, A Functional Approach to External Graph Algorithms, Proceedings of the 6th Annual European Symposium on Algorithms, p.332-343, August 24-26, 1998
• 7: Pankaj K. Agarwal , Lars Arge , T. M. Murali , Kasturi R. Varadarajan , Jeffrey Scott Vitter, I/O-efficient algorithms for contour-line extraction and planar graph blocking, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.117-126, January 25-27, 1998, San Francisco, California, United States
• 8: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 9: ARC/INFO. 1993. Understanding GIS--the ARC/INFO method. ARC/INFO. Rev. 6 for workstations.
• 10: Lars Arge, The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.334-345, August 16-18, 1995
• 11: Lars Arge, The I/O - Complexity of Ordered Binary - Decision Diagram Manipulation, Proceedings of the 6th International Symposium on Algorithms and Computation, p.82-91, December 04-06, 1995
• 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: Lars Arge , Gerth Stølting Brodal , Laura Toma, On External-Memory MST, SSSP, and Multi-way Planar Graph Separation, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.433-447, July 05-07, 2000
• 14: Klaus Brengel , Andreas Crauser , Paolo Ferragina , Ulrich Meyer, An Experimental Study of Priority Queues in External Memory, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.345-359, July 19-21, 1999
• 15: Gerth Stølting Brodal , Jyrki Katajainen, Worst-Case External-Memory Priority Queues, Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, p.107-118, July 08-10, 1998
• 16: Adam L. Buchsbaum , Michael Goldwasser , Suresh Venkatasubramanian , Jeffery R. Westbrook, On external memory graph traversal, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.859-860, January 09-11, 2000, San Francisco, California, United States
• 17: Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
• 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: Esteban Feuerstein , Alberto Marchetti-Spaccamela, Memory Paging for Connectivity and Path Problems in Graphs, Proceedings of the 4th International Symposium on Algorithms and Computation, p.416-425, December 15-17, 1993
• 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: Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
• 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: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 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: Vijay Kumar , Eric J. Schwabe, Improved Algorithms and Data Structures for Solving Graph Problems in External Memory, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.169, October 23-26, 1996
• 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: Kameshwar Munagala , Abhiram Ranade, I/O-complexity of graph algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.687-694, January 17-19, 1999, Baltimore, Maryland, United States
• 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: Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, May 1998
• 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.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization
      D.4.4 Communications Management
          Subjects: Input/output

General Terms:
Algorithms, Design, Performance