Discovering Spatial Prevalent Co-location Patterns by Once Scanning Datasets Without Generating Candidates

Discovering spatial prevalent co-location patterns (SPCPs) has become an important branch of spatial data mining because it can effectively reveal the hidden knowledge between spatial features in space. Many efficient algorithms have been proposed and the common idea of them is to first generate a set of candidates and then search for all co-location instances of these candidates. Although the existing algorithms designed different data structures to quickly collect co-location instances, they need to retrieve multiple times these structures to collect the complete set of co-locations of different candidates and the neighbor relationship between instances has to be verified multiple times in different co-location instances. Therefore, mining SPCP performance degrades rapidly when dealing with dense and/or big data. To overcome this, this paper proposes a mining algorithm called one scan for generating co-location instance-based spatial prevalent co-location pattern mining without generating candidates (OS-noC-SPCPM). It uses a co-location instance tree structure that is constructed on each instance and its neighboring instances to collect co-location instances of a bunch of candidates. The tree is in the style of a building-deleting node simultaneously. When all co-location instances derived from the tree of an instance are collected completely, the tree is also cleared. Extensive experiments on real and simulated data sets show that the proposed algorithm can show better performance than the state-of-the-art algorithms.