SCPM-R+ER: A R+ER-based Algorithm for Mining Spatial Co-location Patterns

Spatial co-location pattern (SCP) mining aims to reveal the inherent association between spatial features. Existing table instance-based mining methods consume significant time and space in generating table instances. While methods leveraging cliques or maximal cliques have enhanced mining efficiency, the huge number of cliques still bring considerable challenges in terms of time and space. To address this issue and reduce the quantity of maximal cliques, on the basic of the neighbor relationship (R) between instances with distinct spatial features, this paper introduces a concept of extended neighbor relationship (ER) between instances sharing the same spatial feature and determines the upper bound distance for ER. To mine SCPs, all extended maximal cliques are enumerated by simultaneously considering R and ER. To efficiently calculate the participation index (PI) for each pattern, we design a two-layer hash mapping, namely MFIIndex, which stores the feature set of each extended maximal clique as well as the instances of each feature within the set. Leveraging MFIIndex, we design a R+ER-based algorithm for SCP mining called SCPM-R+ER, which can efficiently compute the PI of each pattern. To validate its performance, we compare SCPM-R+ER with four classic methods on two real-world datasets. The results on the experiments demonstrate that SCPM-R+ER can efficiently discover all prevalent SCPs, particularly when the distance threshold d is fixed and meanwhile the minimum prevalence threshold min_prev is varied. In addition, SCPM-R+ER consumes the least memory when facing a larger d.