Colocation patterns refer to subsets of spatial features whose instances are frequently located together. Mining colocation patterns is important in many applications such as identifying relationships between diseases and environmental factors, but is computationally challenging due to the large number of instances and candidate patterns. Existing algorithms are mostly sequential, and thus can be insufficient for big spatial event data. Recently, parallel colocation mining algorithms have been developed based on the Map-reduce framework, which is economically expensive. Another work proposed a GPU algorithm based on iCPI tree, but assumes that the number of neighbors for each instance is within a small constant, and thus cannot be used when instances are dense and unevenly distributed. To address these limitations, we recently proposed grid-based GPU colocation mining algorithms that include a novel cell-aggregate-based upper bound filter, and two refinement algorithms. In this paper, we provide theoretical analysis of running time. Furthermore using GPU profiling, we identify our recent GPU implementation, GPU-grid-join, as a memory bound problem and to address its bottlenecks, we proposes GPU-grid-join+, an optimized GPU algorithm. Our experimental results on real world data shows that GPU-grid-join+ achieves 4 to 12-fold speedup over GPU-grid-join both running on Nvidia P100 GPU as well as 56 to 126-fold speedup over OpenMP implementation over Intel(R) Xeon(R) CPU with 12 cores. Also for synthetic data, the speedup is in ranges 3 to 7-fold and 9 to 42-fold respectively.

Given a spatial raster framework with explanatory feature layers, a spatial contextual layer, as well as a set of training samples with class labels, the spatial prediction problem aims to learn a model that can predict a class layer. The problem is important in societal applications such as flood extent mapping, but is challenging due to the noise, obstacles, and heterogeneity in feature maps, implicit spatial dependency between locations based on the contextual layer, and the large number of sample locations. Existing work often assumes undirected spatial dependency, or directed dependency with a total order. In contrast, we recently proposed geographical hidden Markov tree, a probabilistic graphical model that generalizes the common hidden Markov model from a one-dimensional sequence to a two-dimensional map. Partial order class dependency is incorporated in the hidden class layer with a reverse tree structure. We also investigated efficient learning algorithms. This paper extends our recent model with overlaying class nodes between observation nodes and underlying hidden class nodes. The additional overlaying class layer makes the model more robust to large scale feature obstacles. We also update learning and inference methods. Extensive evaluations on real world datasets show that our models outperform multiple baselines.

Spatial structured models are predictive models that capture dependency structure between samples based on their locations in the space. Learning such models plays an important role in many geoscience applications, but it also poses significant challenges due to implicit dependency structure in continuous space and high computational costs. Existing models often assume that the dependency structure is based on either spatial proximity or network topology, and thus cannot incorporate complex dependency structure such as contour and flow direction on a 3D potential surface. To fill the gap, we recently proposed hidden Markov contour tree (HMCT), which generalizes the traditional hidden Markov model from a total order sequence to a partial order polytree. HMCT also advances existing work on hidden Markov trees through capturing complex contour structures. We proposed efficient model construction and learning algorithms. This paper extends our initial HMCT model into a post-processor. We analyzed the theoretical properties of the extended model. Evaluations on real-world flood mapping datasets show that HMCT outperforms multiple baseline methods in classification performance and the HMCT post-processor can also effectively enhance other baseline methods. Computational experiments show that HMCT is scalable to large data sizes (e.g., classifying millions of samples in seconds).

The accurate and prompt mapping of flood-affected regions is important for effective disaster management, including damage assessment and relief efforts. While high-resolution optical imagery from satellites during disasters presents an opportunity for automated flood inundation mapping, existing segmentation models face challenges due to noises such as cloud cover and tree canopies. Thanks to the digital elevation model (DEM) data readily available from sources such as United States Geological Survey (USGS), terrain guidance was utilized by recent graphical models such as hidden Markov trees (HMTs) to improve segmentation quality. Unfortunately, these methods either can only handle a small area where water levels at different locations are assumed to be consistent or require restricted assumptions such as there is only one river channel. This article presents an algorithm for flood extent mapping on large-scale Earth imagery, applicable to a large geographic area with multiple river channels. Since water level can vary a lot from upstream to downstream, we propose to detect river pixels to partition the remaining pixels into localized zones, each with a unique water level. In each zone, water at all locations flows to the same river entry point. Pixels in each zone are organized by an HMT to capture water flow directions guided by elevations. Moreover, a novel regularization scheme is designed to enforce inter-zone consistency by penalizing pixel-pairs of adjacent zones that violate terrain guidance. Efficient parallelization is made possible by coloring the zone adjacency graph to identify zones and zone-pairs that have no dependency and hence can be processed in parallel, and incremental one-pass terrain-guided scanning is conducted wherever applicable to reuse computations. Experiments demonstrate that our solution is more accurate than existing solutions and can efficiently and accurately map out flooding pixels in a giant area of size 24,805 × 40,129. Despite the imbalanced workloads caused by a few large zonal HMTs dominating the serial computing time, our parallelization approach is effective and manages to achieve up to 14.3× speedup on a machine with Intel Xeon Gold 6126 CPU @ 2.60 GHz (24 cores, 48 threads) using 32 threads.