Thomas Hazel '05
Efficient shortest path computation on grid-based terrains
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.