Search

Spatial co-location pattern mining (SCPM) aims to discover subsets of spatial features frequently located together in proximate areas. Previous studies of SCPM solely concern the inter-features association of a pattern, but neglect the interesting intra-feature behavior. In this paper, we propose the task of spatial co-location pattern mining with coupling relation consideration (SCPM-CR) to capture complex relations embedded in a co-location. Specifically, InterPCI measure is designed to capture the inter-features coupling by considering the comprehensive interaction of objects for the features in a pattern, and luckily it possesses the anti-monotone property. Another measure, IntraCAI, is proposed to capture the congregating behavior of intra-feature objects under the restriction of a co-location. A general framework is designed for SCPM-CR task and experiments show that a large fraction of computation time is devoted to identifying the participating objects of a candidate pattern. To tackle this calculation bottleneck, a novel candidate-and-search algorithm is suggested, CS-HBS, equipped with heuristic backtracking search. Extensive experiments are conducted on real and synthetic datasets to demonstrate the superiority of SCPM-CR compared with traditional SCPM methods, and also to validate the efficiency and scalability of CS-HBS. Experimental results show that CS-HBS outperforms the baselines by several times or even orders of magnitude. [ABSTRACT FROM AUTHOR]

Spatial co-location pattern mining is an interesting and important task in spatial data mining which discovers the subsets of spatial features frequently observed together in nearby geographic space. However, the traditional framework of mining prevalent co-location patterns produces numerous redundant co-location patterns, which makes it hard for users to understand or apply. To address this issue, in this paper, we study the problem of reducing redundancy in a collection of prevalent co-location patterns by utilizing the spatial distribution information of co-location instances. We first introduce the concept of semantic distance between a co-location pattern and its super-patterns, and then define redundant co-locations by introducing the concept of δ-covered, where $\delta \,(0\leq \delta \leq 1)$ is a coverage measure. We develop two algorithms RRclosed and RRnull to perform the redundancy reduction for prevalent co-location patterns. The former adopts the post-mining framework that is commonly used by existing redundancy reduction techniques, while the latter employs the mine-and-reduce framework that pushes redundancy reduction into the co-location mining process. Our performance studies on the synthetic and real-world data sets demonstrate that our method effectively reduces the size of the original collection of closed co-location patterns by about 50 percent. Furthermore, the RRnull method runs much faster than the related closed co-location pattern mining algorithm. [ABSTRACT FROM AUTHOR]

A spatial colocation pattern is a group of spatial features whose instances are frequently located together in geographic space. Discovering colocations has many useful applications. For example, colocated plant species discovered from plant distribution data sets can contribute to the analysis of plant geography, phytosociology studies, and plant protection recommendations. In this paper, we study the colocation mining problem in the context of uncertain data, as the data generated from a wide range of data sources are inherently uncertain. One straightforward method to mine the prevalent colocations in a spatially uncertain data set is to simply compute the expected participation index of a candidate and decide if it exceeds a minimum prevalence threshold. Although this definition has been widely adopted, it misses important information about the confidence which can be associated with the participation index of a colocation. We propose another definition, probabilistic prevalent colocations, trying to find all the colocations that are likely to be prevalent in a randomly generated possible world. Finding probabilistic prevalent colocations (PPCs) turn out to be difficult. First, we propose pruning strategies for candidates to reduce the amount of computation of the probabilistic participation index values. Next, we design an improved dynamic programming algorithm for identifying candidates. This algorithm is suitable for parallel computation, and approximate computation. Finally, the effectiveness and efficiency of the methods proposed as well as the pruning strategies and the optimization techniques are verified by extensive experiments with “real $(+)$ synthetic” spatially uncertain data sets. [ABSTRACT FROM AUTHOR]

With recent advances in information technologies such as global position system and mobile internet, a huge volume of spatio-textual objects have been generated from location-based services, which enable a wide range of spatial keyword queries. Recently, researchers have proposed a novel query, called Spatial Pattern Matching (SPM), which uses a pattern to capture the user's intention. It has been demonstrated to be fundamental and useful for many real applications. Despite its usefulness, the SPM problem is computationally intractable. Existing algorithms suffer from the low efficiency issue, especially on large scale datasets. To enhance the performance of SPM, in this paper we propose a novel Efficient Spatial Pattern Matching (ESPM) algorithm, which exploits the inverted linear quadtree index and computes matched node pairs and object pairs level by level in a top-down manner. In particular, it focuses on pruning unpromising nodes and node pairs at the high levels, resulting in a large number of unpromising objects and object pairs to be pruned before accessing them from disk. We experimentally evaluate the performance of ESPM on real large datasets. Our results show that ESPM is over one order of magnitude faster than the state-of-the-art algorithm, and also uses much less I/O cost. [ABSTRACT FROM AUTHOR]