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

Access Restriction
Subscribed

 Author Arge, Lars ♦ Toma, Laura ♦ Vitter, Jeffrey Scott Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2001 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data 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 $\textit{M}$ denotes the size of the main memory and $\textit{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. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2001-12-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 6

Open content in new tab

Source: ACM Digital Library