About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SDM 2012
Conference paper
Detecting irregularly shaped significant spatial and spatio-temporal clusters
Abstract
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.