Adaptive detection of spatial point event outliers using multilevel constrained Delaunay triangulation

• The SPEOD algorithm proposed in this study is specially designed for outlier detection in spatial point event data sets.
• The SPEOD algorithm can accurately detect various types of spatial outliers in both global and local levels.
• The SPEOD algorithm is easy to implement with no need of user-specified parameters.

Spatial outlier detection is a research hot spot in the field of spatial data mining. Because of the lack of specific research on spatial point events, this study presents an adaptive approach for spatial point events outlier detection (SPEOD) using multilevel constrained Delaunay triangulation. First, the spatial proximity relationships between spatial point events are roughly captured by Delaunay triangulation. Then, three-level constraints are described and used to refine spatial proximity relationships with the consideration of statistical characteristics. Finally, those spatial point events connected by remaining edges are gathered to form a series of subgraphs. Those subgraphs containing very few point events are regarded as spatial outliers. Experiments on both synthetic and real-world spatial data sets are used to show that the proposed SPEOD algorithm can detect various types of spatial point event outliers with high efficiency. Moreover, there is no need to input any parameter in SPEOD.