Maximal Sub-prevalent Co-location Patterns and Efficient Mining Algorithms

Spatial prevalent co-location pattern mining plays an important role to identify spatially correlated features in many applications, such as Earth science and public transportation. Observe that the existing approaches only consider the clique instances where feature instances form a clique and may neglect some important spatial correlations among features in practice, in this paper, we introduce star participation instances to measure the prevalence of co-location patterns such that spatially correlated instances which cannot form cliques will also be properly considered. Then we propose a new concept of subprevalent co-location patterns (SCP) based on the star participation instances. We present two efficient algorithms, the prefix-tree-based algorithm (PTBA) and the partition-based algorithm (PBA), to mine all the maximal sub-prevalent co-location patterns (MSCP) in a spatial data set. PTBA adopts a typical candidate generate-and-test method starting from candidates with the longest pattern-size, while PBA is performed step by step from 3-size core patterns. We demonstrate the significance of the new concepts as well as the efficiency of our algorithms through extensive experiments.