The ACM Journal of Experimental Algorithmics

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

The potential and use of Geographic Information Systems is rapidly increasing due to the increasing availabilty of massive amounts of geospatial data from projects like NASA's Mission to Planet Earth. However, the use of thes 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 compuation 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 O((N/B) log_(M/B) (N/B) ) I/O algorithms for several problems on sqrt(N) by sqrt(N) 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 pracitcal 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.