Given a collection of boolean spatial features, the co-location pattern discovery process finds the subsets of features frequently located together. For example, the analysis of an ecology dataset may reveal the frequent co-location of a fire ignition source feature with a needle vegetation type feature and a drought feature. The spatial co-location rule problem is different from the association rule problem. Even though boolean spatial feature types(also called spatial events) may correspond to items in association rules over market-basket datasets, there is no natural notion of transactions. This creates difficulty in using traditional measures (e.g. support, confidence) and applying association rule mining algorithms which use support based pruning.In our recent work, we proposed a notion of user-specified neighborhoods in place oftransactions to specify groups of items, new interest measures for spatial co-location patterns which are robust in the face of potentially infinite overlapping neighborhoods,and an algorithm to mine frequent spatial co-location patterns and analyzed its correctness,and completeness. The Co-location Miner generates candidateprevalent co-locations in the spatial feature level and generates table instances for the candidate co-locations to check their prevalence. When the false candidate prevalent co-location set is large, the performance of the Co-location Miner decreases. Due to spatial autocorrelation, the locations of individual spatial features of a point data set are often clustered spatially, the Co-location Miner is computationally expensive without taking spatialautocorrelation into consideration. In this paper, a new algorithm called Multi-resolution Co-location Miner is presented. The proposed algorithm has two logical phases, namely filter and refinement. The filter phase summarizes the original point dataset into a smaller lattice dataset using space partitioning which allows the computation of the upper bounds of the interest measures. It eliminates many non-interesting co-locations, reducing the set of candidates to be explored by the refinement phase, which computes the true values of the interest measures. We show that the proposed algorithm is correct and complete and the proposed algorithm is several times faster than the traditional Co-location Miner algorithm in a dataset with spatially autocorrelation by experiments.
Shekhar, Shashi; Huang, Yan.
The Multi-resolution Co-location Miner: A New Algorithm to Find Co-location Patterns in Spatial Dataset.
Retrieved from the University of Minnesota Digital Conservancy,
Content distributed via the University of Minnesota's Digital Conservancy may be subject to additional license and use restrictions applied by the depositor.