Detecting irregularly shaped significant spatial and spatio-temporal clusters

Detecting significant overdensity or underdensity clusters in spatio-temporal data is critical for many real-world applica- Tions. Most existing approaches are designed to deal with regularly shaped clusters such as circular, elliptic and rect- Angular ones, but cannot work well on irregularly shaped clusters. In this paper, we propose GridScan, a grid-based approach for detecting irregularly shaped spatial clusters. In GridScan, a cluster is asymptotically described by a set of connected grid cells and is computed by a fast greedy region- growing algorithm with elaborating cluster merging in the process. The time complexity of GridScan is linear to the number of grids, making it scalable to very large datasets. A prospective spatio-temporal cluster detection approach, GridScan-Pro, is also proposed by extending GridScan. Ex- periments and a case study in the epidemic scenario demon- strate that our approaches greatly outperform existing ones in terms of accuracy, effciency, and scalability. Copyright © 2012 by the Society for Industrial and Applied Mathematics.