Flow computation on massive grids

ABSTRACT

As detailed terrain becomes available, GIS applications target larger geographic areas at finer resolutions. Processing the massive data presents significant challenges to GIS systems and demands algorithms that are optimized for both data movement and computation.In this paper we develop effcient algorithms for flow routing on massive terrains, extending our previous work on flow accumulation. Our implementations of these algorithms constitute the first comprehensive terrain flow software system designed and optimized for massive data. We compare the performance of our system, called TERRAFLOW, with that of state of the art commercial and open-source GIS systems. On large terrains, TERRAFLOW outpreforms existing systems by a factor of 2 to 1000, and is capable of solving problems of a scope and scale that are impractical with previous algorithms.

REFERENCES

• 1: 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]
• 2: 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
• 3: [3] L. Arge, R. Barve, O. Procopiuc, L. Toma, D. E. Vengroff, and R. Wickremesinghe. TPIE User Manual and Reference. Duke University, 1999.
• 4: [4] L. Arge, L. Toma, and J. S. Vitter. I/O-efficient algorithms for problems on grid-based terrains. In Proc. Workshop on Algorithm Engineering and Experimentation, 2000.
• 5: 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
• 6: [6] C. Ehlschlaeger. Using the A^T search algorithm to develop hydrologic models from digital elevation data. In International Geographic Information Systems (IGIS) Symposium, pages 275-281. U.S. Army Construction Engineering Research Laboratory, 1989. Baltimore, MD, 18-19 March 1989.
• 7: [7] J. Fairfield and P. Leymarie. Drainage network from grid digital elevation model. Water Resource Research, 27:709-717, 1991.
• 8: T. Graham Freeman, Calculating catchment area with divergent flow based on a regular grid, Computers & Geosciences, v.17 n.3, p.413-422, 1991 [doi>10.1016/0098-3004(91)90048-I]
• 9: L. W. Martz , J. Garbrecht, Numerical definition of drainage network and subcatchment areas from digital elevation models, Computers & Geosciences, v.18 n.6, p.747-761, July 1992 [doi>10.1016/0098-3004(92)90007-E]
• 10: [10] J. Garbrecht and L. Martz. The assignment of drainage directions over flat surfaces in raster digital elevation models. Journal of Hydrology, 193:204-213, 1997.
• 11: [11] S. Jenson and J. Domingue. Extracting topographic structure from digital elevation data for geographic information system analysis. Photogrammetric Engineering and Remote Sensing, 54(11):1593-1600, 1988.
• 12: Lawrence W. Martz , Eeltje De Jong, CATCH: a FORTRAN program for measuring catchment area from digital elevation models, Computers & Geosciences, v.14 n.5, p.627-640, July 1988 [doi>10.1016/0098-3004(88)90018-0]
• 13: [13] I. Moore, R. Grayson, and A. Ladson. Digital terrain modelling: a review of hydrological, geomorphological, and biological applications. Hydrological Processes, 5:3-30, 1991.
• 14: [14] J. O'Callaghan and D. Mark. The extraction of drainage networks from digital elevation data. Computer Vision, Graphics and Image Processing, 28:328-344, 1984.
• 15: [15] S. Peckham. Self-similarity in the geometry and dynamics of large river basins. PhD thesis, Univ. of Colorado, Boulder, 1995.
• 16: [16] D. Tarboton. A new method for the determination of flow directions and contributing areas in grid digital elevation models. Water Resources Research, 33:309-319, 1997.
• 17: [17] D. Tarboton, R. Bras, and I. Rodriguez-Iturbe. On the extraction of channel networks from digital elevation data. Hydrological Processes, 5:81-100, 1991.
• 18: [18] A. Tribe. Automated recognition of valley lines and drainage networks from grid digital elevation models: a review and a new method. Journal of Hydrology, 139:263-293, 1992.
• 19: [19] D. Wolock and G. McCabe. Comparison of single and multiple flow direction algorithms for computing topographic parameters in topmodel. Water Resources Research, 31:1315-1324, 1995.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Earth and atmospheric sciences

General Terms:
Algorithms, Theory