Technical Perspective: Progress in Spatial Computing for Flood Prediction

Imagine you are considering buying a long-term place with a view of mountains or ocean. For due diligence, your partner asks about flood risk in the area. FEMA maps show the place is outside the 100-year flood zones (1% annual chance). However, you have heard that climate change is making extreme events more extreme and some places have seen multiple 100-year floods within a few years. Next, you browse information about climate change and its impact. These provide the projected climate change and precipitation (for example, rainfall, snowfall) under different policy scenarios, but not projected flood risk maps. How will you assess long-term flood risks for candidate places? This is an important societal use-case of and a challenging problem in spatial computing.^3,4

Flood forecast and risk assessment started as early as Egyptian civilization. The Nile monsoon floods nourished nearby fertile lands but also erased mud-based farm boundaries motivating the invention of land surveying, which was later formalized as geometry and trigonometry across the Mediterranean sea.

Communities started recording floods for forecasts and risk assessments to reduce loss of property and lives. Nile flood records go back hundreds of years and confound "one-size-fits-all" machine learning methods^1,5 due to spatio-temporal auto-correlation, teleconnections (for example, upstream use and storage), and non-stationarity (for example, climate change). Physics-driven models¹ account for hydrological processes such as surface run-off, ground absorption, and evaporation using data about upstream precipitation, snow melt, water levels, flow rates, soil type, soil moisture, atmospheric humidity, temperature, river bathymetry, sewer networks, and so on. The model parameters are calibrated using historical data. Due to the high data needs and computational costs, hydrological models are difficult to use for large areas and time-constrained use cases, for example, flash floods. Thus, many use Geographic Information Systems (GIS)-based approaches focusing on surface run-offs, sub-processes of flow accumulation, and depression overflows. For example, the ArcGIS hydro² uses maps of terrain elevation, precipitation and snow melt. These are converted to a flow graph, where nodes are locations and directed edges represent gravity-driven water-flows. For example, a single-flow graph sends flows towards the lowest neighbors.

Flood forecasting and risk assessment started as early as the Egyptian civilization.

Progress in spatial computing^3,4 is made by either improving the approximation of spatial phenomena or by improving the computation cost or both. Spatial computing literature has investigated both for flood-modeling. It has investigated triangulated irregular networks (TINs) as an alternative to traditional gridded digital elevation models to not only reduce approximation error but also storage costs. It also advanced multi-flow graphs to allow water from a node to flow toward multiple downhill neighbors for more accurate representation of surface run-offs and down-stream floods. However, there are few algorithms for multi-flow graphs beyond flow accumulation.

The authors of the following paper take a big step to fill this knowledge gap. Design of scalable algorithms is more difficult for multi-flow graphs due to their weighted directed acyclic graph topology in contrast with the simpler tree or forest topology of single-flow graphs. While well-known transitive closure algorithms may estimate flow accumulations, new spatial algorithms are needed to efficiently compute edge weights and cascading depression overflows. This paper leverages properties of planar graphs, priority queues and fast matrix multiplication methods to address the challenges. Key results include new scalable (for example, linear or n log n) algorithms for point-flood query, terrain-flood query and flood time query on multi-flow graphs. These were lauded by a best paper award at a recent ACM SIGSPATIAL conference and open doors for design of algorithms for next-generation use cases such as preparation of climate-change aware flood-plain maps with uncertainty quantification.

Going back to the opening story, you (or an insurance company) may use the algorithm for point-flood query to quickly assess flood risk for candidate properties. Smart cities and communities may use the terrain-flood query algorithms to identify flood-prone low-lying areas for remedies.