ADMISSIONS| ACADEMICS| SWARTHMORE

Talk by Andrew Danner, Duke University

Scalable Algorithms for Terrain Analysis and GIS
Wednesday, April 5 2006
4:15 pm in Science Center 240

Abstract

Modern remote sensing methods can rapidly collect an enormous amount of digital geographic data. In particular, a remote sensing method called LIDAR uses a airplane equipped with a laser range finder and GPS to collect a set of (x,y,z) points that measure the elevation of a terrain. These LIDAR data sets contain millions or hundreds of millions of data points.

Processing data sets that are much larger than the physical memory of a computer poses a number of computational challenges. Portions of the data must reside on large but slow hard disks. The transfer of data between disk and main memory, not the internal memory computation, can become the primary bottleneck when processing these data sets.

I will describe the I/O model of computation in which we can develop I/O-efficient algorithms that are scalable to data sets much larger than the physical memory of modern computers. I will then describe an I/O efficient algorithm for constructing a grid surface model of a terrain given a large set of points sampled from the terrain surface, and highlight some additional applications in geographic information systems (GIS) where I have applied I/O-efficient algorithms.