A Novel Algorithm for Efficiently Mining Spatial Multi-Level Co-Location Patterns

The spatial co-location pattern is a collection of spatial features in which instances of features prevalently appear in neighboring spatial regions. Due to the heterogeneity of spatial data distribution, the instances of some patterns appear prevalently in the global region (i.e., Global Prevalent Co-location Patterns, GPCPs), while some patterns are not prevalent globally, and their instances are clustered only in some local regions (i.e., Local Prevalent Co-location Patterns, LPCPs). Multi-level co-location pattern mining aims to mine these two types of patterns simultaneously, but existing methods cannot accurately judge the spatial distribution of patterns in a certain region, leading to unsuitable judgment of both GPCPs and LPCPs. To overcome this problem, this paper firstly proposes the relative distribution coefficient to identify the spatial distribution form of patterns, and provides a more refined way for discovering both GPCPs and LPCPs. Secondly, a novel multi-level co-location pattern mining algorithm is proposed by using the relative distribution coefficient as the interest metrics, and some pruning strategies are suggested to improve the mining efficiency. Finally, extensive experiments are conducted on both real and synthetic datasets to verify the effectiveness and efficiency of the proposed method.