Given a collection of geo-located activities (e.g., Crime reports), ring-shaped hotspot detection (RHD) finds rings, where concentration of activities inside the ring is much higher than outside. RHD is important for the applications such as crime analysis, where it may focus the search for crime source's location, e.g. The home of a serial criminal. RHD is challenging because of the large number of candidate rings and the high computational cost of the statistical significance test. Previous statistically significant hotspot detection techniques (e.g., Sat Scan) identify circular/rectangular areas, but can not discover rings. This paper proposes a dual grid based pruning (DGP) approach to detect ring-shaped hotspots. A case study on real crime data confirms that DGP detects novel ring-shaped regions, regions that go undetected by Sat Scan. Experiments show that DGP improves the computational cost of a naive approach substantially.

Data summarization is an important concept in data mining for finding a compact representation of a dataset. In spatial network activity summarization (SNAS), we are given a spatial network and a collection of activities (e.g., pedestrian fatality reports, crime reports) and the goal is to find k shortest paths that summarize the activities. SNAS is important for applications where observations occur along linear paths such as roadways, train tracks, etc. SNAS is computationally challenging because of the large number of k subsets of shortest paths in a spatial network. Previous work has focused on either geometry or subgraph-based approaches (e.g., only one path), and cannot summarize activities using multiple paths. This paper proposes a K-Main Routes (KMR) approach that discovers k shortest paths to summarize activities. KMR generalizes K-means for network space but uses shortest paths instead of ellipses to summarize activities. To improve performance, KMR uses network Voronoi, divide and conquer, and pruning strategies. We present a case study comparing KMR's network-based output (i.e., shortest paths) to geometry-based outputs (e.g., ellipses) on pedestrian fatality data. Experimental results on synthetic and real data show that KMR with our performance-tuning decisions yields substantial computational savings without reducing summary path coverage.