Ring-Shaped Hotspot Detection

Given a set of activity points (e.g., crime, disease locations), Ring-Shaped Hotspot Detection (RHD) finds ring-shaped areas where the concentration of activities inside is significantly higher than that outside. RHD is societally important for applications such as environmental criminology, epidemiology, and biology to investigate evasive patterns. RHD is computationally challenging because of the large number of candidate rings, non-monotonic interest measure, and cost of the statistical significance test. Previous approaches (e.g., spatial scan statistics tools) focus on simply-connected shaped areas (e.g., circles, rectangles) and can not detect statistically significant rings. In this paper, a novel algorithm, DGPLMR, is proposed to discover statistically significant ring-shaped hotspots based on the ideas of dual grid based pruning and best enclosing ring refining. Theoretical evaluation proves that the proposed approach is a correct approach (i.e., all outputs satisfy input thresholds) to detect ring-shaped hotspots. Case study on real disease data shows that the proposed approach finds ring-shaped hotspots which were not detected by the existing techniques. Cost analysis and experimental results on synthetic data show that the proposed approach with algorithmic refinements yields substantial computational savings.