As 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.
This 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.