Detection of Spatial Outlier Patterns from Point Events Based on Multi-constrained Delaunay Triangulation

In recent years, spatial outlier detection has become a research hotspot in the domain of spatial data mining. The aim of spatial outlier detection is to discover those small parts of spatial entities deviating from the global or local distribution in massive spatial datasets. Spatial outliers may indicate potential, unknown, and important knowledge instead of noise in many application domains, e.g., environmental science, meteorology, urban traffic, and so on. Existing spatial outlier detection methods focus on detecting spatial outliers in the spatial datasets with non-spatial attributes. There is still a lack of detection methods specifically designed for spatial point event datasets, in particular, for complicated spatial point event datasets with clusters having arbitrary shapes and/or different densities. Therefore, we developed a method of detecting outlier patterns for spatial point events by considering spatial locations; the definition of a spatial outlier is extended and a multi-level constrained Delaunay triangulation is employed. Spatial adjacency relationships are roughly obtained from Delaunay triangulation. Then, three-level constraints are described and utilized for precise spatial adjacency relationships with the consideration of statistical characteristics. Finally, those spatial point events connected by the remained edges are gathered to form a series of clusters. The clusters containing very few point events are regarded as spatial outlier patterns. This algorithm does not involve any parameters. Experiments on both synthetic and real-world spatial datasets demonstrate that this algorithm can detect all kinds of spatial outlier patterns efficiently and robustly.