Flow computation on massive grids

Journal Article

As detailed terrain data 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 efficient 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 outperforms 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.

Full Text

Duke Authors

Cited Authors

  • Toma, L; Wickremesinghe, R; Arge, L; Chase, JS; Vitter, JS; Halpin, PN; Urban, D

Published Date

  • January 1, 2001

Published In

  • Proceedings of the Acm Workshop on Advances in Geographic Information Systems

Start / End Page

  • 82 - 87

Digital Object Identifier (DOI)

  • 10.1145/512161.512180

Citation Source

  • Scopus