A maximal ordered ego-clique based approach for prevalent co-location pattern mining

Spatial data often exhibit a tendency highly similar to spatial objects located close to each other. Thus, prevalent co-location pattern (PCP) mining has been studied extensively to discover this tendency. The organization of neighboring relationships on spatial data, called neighborhood materialization (NM), is critical to the PCP problem. However, the previous NM methods suffer from poor efficiency and a large set of results. To this end, a new NM model based on maximal cliques with ego-centric points is proposed in this study, called the maximal ordered ego-clique (MOEC). Here, the correctness of the materialized neighboring relationships of spatial data is proven, and the complexity is further analyzed. In addition, a generalized algorithm GMOEC is designed to effectively transform the neighboring relationships of a spatial data set into MOECs. The geometry of the spatial data set is fully exploited to develop several optimization strategies to enhance efficiency. Furthermore, a novel generalized PCP mining method, GPCP, is proposed to avoid multiple scans of the materialized neighborhood. The GPCP method discovers all PCPs based on the materialized neighborhood using the vertical data format. Finally, extensive experiments on both synthetic and real data sets demonstrate that the proposed solution is highly effective and efficient. (C) 2022 Elsevier Inc. All rights reserved.