Mining Maximal Dynamic Spatial Colocation Patterns

Mining Spatial Co-Location Patterns With a Mixed Prevalence Measure

A co-location pattern indicates a subset of spatial features whose instances are frequently located together in proximate geographical space. Most previous studies of spatial co-location pattern mining concern what percentage of instances per feature are involved in the table instance of a pattern, but neglect the heterogeneity in the number of feature instances and the distribution of instances. As a result, the deviation may be occurred in the interest measure of co-locations. In this article, we propose a novel mixed prevalence index (MPI) incorporating the effect of feature-level and instance-level heterogeneity on the prevalence measure, which can address some dilemmas in existing interest measures. Luckily, MPI possesses the partial antimonotone property. In virtue of this property, a branch-based search algorithm equipped with some optimizing strategies of MPI calculation is proposed, namely, Branch-Opt-MPI. Comprehensive experiments are conducted on both real and synthetic spatial datasets. Experimental results reveal the superiority of MPI compared to other interest measures and also validate the efficiency and scalability of the Branch-Opt-MPI. Particularly, the Branch-Opt-MPI performs more efficiently than baselines for several times or even orders of magnitude in dense data.

Efficiently mining maximal l-reachability co-location patterns from spatial data sets

A co-location pattern is a set of spatial features that are strongly correlated in space. However, some of these patterns could be neglected if the prevalence metrics are based solely on the clique (or star) relationship. Hence, the l-reachability co-location pattern is proposed by introducing the l-reachability clique where the members of each instance pair can be reachable to each other in a given step length l. Because the average size of l-reachability co-location patterns tends to be longer, maximal l-reachability co-location pattern mining is researched in this paper. First, some sparsification strategies are introduced to shorten star neighborhood lists of instances in an updated graph called the l-reachability neighbor relationship graph, and then, they are grouped by their corresponding patterns. Second, candidate maximal l-reachability co-location patterns are iteratively detected in a size-independent way on bi-graphs that contain group keys and their intersection sets. Third, the prevalence of each candidate maximal l-reachability co-location pattern is checked in a binary search way with a natural l-reachability clique called the ⌊l/2⌋-reachability neighborhood list. Finally, the effectiveness and efficiency of our model and algorithms are analyzed by extensive comparison experiments on synthetic and real-world spatial data sets.

Mining Non-Redundant Co-Location Patterns

Co-location pattern mining refers to discovering neighboring relationships of spatial features distributed in geographic space. With the rapid growth of spatial datasets, the usefulness of co-location patterns is strongly limited by the large number of discovered patterns containing multiple redundancies. To address this problem, in this article, we propose a novel approach for discovering the super participation index-closed (SPI-closed) co-location patterns which are a newly proposed lossless condensed representation of co-location patterns by considering distributions of the spatial instances. In the proposed approach, first, a linear-time method is designed to generate complete and correct neighboring cliques using extended neighboring relationships. Based on these cliques, a hash structure is then constructed to store the distributions of the co-location patterns in a condensed way. Finally, using this hash structure, the SPI-closed co-location patterns (SCPs) are efficiently discovered even if the prevalence threshold is changed, while similar approaches have to restart their mining processes. To confirm the efficiency of the proposed method, we compared its performance with similar approaches in the literature on multiple real and synthetic spatial datasets. The experiments confirm that our new approach is more efficient, effective, and flexible than similar approaches.