Location: Bowdoin / Computer Science / Student Projects / Summer / 2005 / Thomas Hazel

Computer Science

Efficient shortest path computation on grid-based terrains

As a Surdna Undergraduate Research Fellow, Tom spent the summer of 2004 at Bowdoin College working with Professor Laura Toma on studying and improving the performance of a commonly used Geographic Information System (GIS) application on terrains -- the computation of the cumulative cost of moving on a cost surface to user specified locations.

GIS DataThe widely-used open source GIS GRASS implements this functionality in a command called r.cost. This command takes as inputs a map and a set of starting points and then computes the least cost path to get from one of these starting points to every other point on the map. However, the problem is that this command does not scale up to even moderately large grids. An email sent to the GRASS developers mailing list points out that r.cost takes an unreasonably long time on grids of a mere 12 million points (approx. 50MB). The problem stems from the fact that the input maps are too large to fit in a computer's main memory. Therefore, whenever r.cost needs to reference a point on the map, it must load the information from the computer's hard-drive, which is an extremely slow operation (a disk access is 10^6 times slower then a main memory access).

The project consists in analyzing the algorithm underlying the r.cost GRASS command and redesigning it to make it I/O-efficient. The new module that Tom has been designing, r.terracost, maintains all functionality of r.cost but relies on I/O-techniques to make it scalable to very large datasets. The main idea is to break down a map (terrain) into small pieces or tiles any one of which can fit into memory. The new algorithm will load in each tile one at a time and do all the calculations necessary for that tile. Once the algorithm is finished looking at each tile individually, it can piece together these individual results to solve the problem as a whole. Although the algorithm was already known in theory, this project is the first time it has ever been implemented.

Thomas HazelAs this project is continuing as an independent study into the fall semester, we are hoping to that r.terracost will improve significantly the performance of r.cost and will make a good contribution the the GRASS community as well as to the world-wide open source GIS users.