Discovering prevalent co-location patterns in different density spatial data without distance thresholds

Abstract

A prevalent spatial co-location pattern (PSCP) refers to a group of different features that their instances occur frequently within a spatial neighborhood. The neighbor of instances is typically evaluated based on the spatial separation between them. If the spatial separation is not greater than a threshold value set by users, they are considered to be neighboring each other. However, determining an appropriate distance threshold for each specific spatial dataset is challenging for users, as it requires careful analysis of the dataset. To address the issue, we propose an algorithm called Delaunay triangulation k-order clique (DTkC) to discover PSCPs without distance thresholds. This algorithm integrates three phases: the spatial neighbor hierarchy structure of instances is created by Delaunay triangulation, employing k-order neighbors allows users to select an appropriate level from the neighbor structure, a clique-based approach is designed to store compactly neighboring instances and quickly collect co-location instances of each candidate pattern to filter PSCPs. We conducted experimental analysis on both synthetic and real-world datasets, to demonstrate the effectiveness of the DTkC algorithm in terms of generating the number of PSCPs, execution time, and memory consumption.