Mining spatial co-location patterns via γ-quasi-clique detection

Spatial co-location patterns (SCPs) are sets of spatial features with instances frequently co-occurring proximally in geographical space. Extracting SCPs is crucial for understanding urban space structure and function. Given that spatial datasets frequently exhibit non-uniform density distributions, such characteristics impose significant limitations and constraints on classical spatial co-location pattern (SCP) mining algorithms in accurately capturing the nuanced proximity relationships among spatial instances. This paper introduces a new materialized model with γ-quasi-clique to comprehensively and flexibly capture complex instance spatial relations. However, the γ-quasi-clique’s structural relaxation can violate downward closure in certain cases, and exhaustive clique enumeration for co-location identification is computationally challenging. To address these problems, we develop a novel neighbor relationship function and a shared scoring mechanism to avoid instance over-counting in this paper. We also implement candidate feature and pattern filtering strategies to reduce computational complexity, along with a filtering-verification framework for participation instance determination. Compared to Fraction-Score, γ-quasi-clique can capture more complex spatial relationships while reducing time complexity by 30% through shared score computation. Empirical evaluations on three real-world datasets show the γ-quasi-clique framework’s theoretical advantage and the proposed algorithms’ computational efficiency.