Fast Mining Prevalent Co-location Patterns Over Dense Spatial Datasets

Traditional prevalent co-location pattern mining (PCPM) methods generate complete table instances (TIs) of all candidates, which is both time and space consuming. Existing Apriori-like methods focus on improving the efficiency of TI generation, while existing Clique-based methods still contain many repeated traversing processes, and therefore neither of them can very well detect the overlap in TIs. To address these challenges, this paper first proposes the concept of extended maximal cliques (EMCs) to detect instance overlap situations, and designs a hash-based storage structure SSHT to reduce mining consumption. Second, a novel approach PCPM-EMC is introduced to detect all prevalent co-location patterns (PCPs), which uses the proposed P-BKp,d algorithm to generate EMCs, and adopts a bidirectional pruning strategy for PCP detection. Lastly, extensive experiments on both real-world and synthetic datasets show that the proposed approach is efficient, and reducing more over 80% space consumption and more than 50% time consumption than existing methods, especially in dense datasets.