TerraFlow Algorithm Outline

FILL | FLOW

Our approach to optimizing performance develops algorithms that explicitly manage data placement and movement, which we refer to as external memory algorithms or I/O-efficient algorithms. In order to be effective, I/O-efficient algorithms must be based on reasonably accurate, yet simple, model of the memory system's characteristics, the I/O-model.

TerraFlow takes as input an elevation grid and outputs the flow direction grid and the flow accumulation grid (it has options to output intermediate grids like the watershed grid, the plateaus grid a.s.o). TerraFlow has two components: FILL and FLOW.

FILL and FLOW are outlines below. For additional details see

FILL

Flow routing is hard because of flat areas. Flat areas are of two types: plateaus and sinks.

The three main phases of FILL are:

  1. Partition the terrain into watersheds and build the watershed graph.
  2. Flood.
  3. Assign flow directions.

You may want to check out how we deal with nodata.

Each of the three phases of FILL can be solved using Sort(N) I/Os.

FLOW

Flow accumulation of a cell represents the total amount of flow draining through a cell of the terrain. We assume that every grid cell initially has one unit of flow (water) and that each grid cell distributes the flow, initial as well as incoming, to the neighbors pointed to by its flow directions. The standard (in-memory) algorithm for flow accumulation uses O(N) I/Os.

..in progress..in the meanwhile see


<laura@cs.duke.edu>
Last modified: Thu Mar 1 00:06:52 2001 by laura.