A new join-less approach for co-location pattern mining

TLDR

Spatial datasets are rapidly expanding, making the automatic discovery of spatial knowledge—especially co‑location patterns—essential yet difficult because of the massive data volume and the heavy computation needed to generate pattern instances. The study proposes a join‑less co‑location pattern mining method that employs a CPI‑tree data structure to replace traditional join operations. The CPI‑tree captures spatial neighbor relationships, enabling all co‑location table instances to be generated efficiently without joins. The method is proven correct and complete, and experiments on synthetic and real data demonstrate it is computationally more efficient than existing join‑less algorithms.

Abstract

With the rapid growth and extensive applications of the spatial dataset, it's getting more important to solve how to find spatial knowledge automatically from spatial datasets. Spatial co-location patterns represent the subsets of features whose instances are frequently located together in geographic space. It's difficult to discovery co-location patterns because of the huge amount of data brought by the instances of spatial features. A large fraction of the computation time is devoted to generating the table instances of co-location patterns. The essence of co-location patterns discovery and three kinds of co-location patterns mining algorithms proposed in recent years are analyzed, and a new join-less approach for co-location patterns mining, which based on a data structure— CPI-tree (Co-location Pattern Instance Tree), is proposed. The CPI-tree materializes spatial neighbor relationships. All co-location table instances can be generated quickly with a CPI-tree. This paper proves the correctness and completeness of the new approach. Finally, an experimental evaluation using synthetic datasets and a real world dataset shows that the algorithm is computationally more efficient than the join-less algorithm.