Location: Bowdoin / Computer Science / Student Projects / 2005 / Thomas Hazel '05

Computer Science

Thomas Hazel '05

Efficient shortest path computation on grid-based terrains

GIS DataAs more and more spatial data becomes available, the need for
efficient and scalable solutions to Geographic Information Systems
(GIS) problems increases. Typically algorithms are designed assuming
that data fits in memory and do not scale up to large inputs. When
processing massive data, the transfer of data between memory and disk
(disk I/O), rather than CPU time, is normally the bottleneck. One
approach to improving performance is to design algorithms that optimize
both CPU and disk I/O.

Thomas Hazel, Bowdoin '05This project addresses the problem of computing multiple-source weighted shortest paths on massive grid-based terrains obtained using remote sensing techniques such as LIDAR and satellite imaging. We present Terracost, the implementation of an I/O-efficient version of Dijkstra's shortest path algorithm. We have implemented terracost in the context of the GRASS open source GIS system, and we report experimental results that demonstrate that the algorithm is not only of theoretical and conceptual interest but also performs very well in practice. More specifically, the algorithm outperforms the current implementation provided by GRASS and additionally scales well with both increasing grid size and increasing number of sources from which the shortest paths are computed.