A Joinless Approach for Mining Spatial Colocation Patterns
Citations Over TimeTop 10% of 2006 papers
Abstract
Spatial colocations represent the subsets of features which are frequently located together in geographic space. Colocation pattern discovery presents challenges since spatial objects are embedded in a continuous space, whereas classical data is often discrete. A large fraction of the computation time is devoted to identifying the instances of colocation patterns. We propose a novel joinless approach for efficient colocation pattern mining. The joinless colocation mining algorithm uses an instance-lookup scheme instead of an expensive spatial or an instance join operation for identifying colocation instances. We prove the joinless algorithm is correct and complete in finding colocation rules. We also describe a partial join approach for a spatial data set often clustered in neighborhood areas. We provide the algebraic cost models to characterize the performance dominance zones of the joinless method and the partial join method with a current join-based colocation mining method, and compare their computational complexities. In the experimental evaluation, using synthetic and real-world data sets, our methods performed more efficiently than the join-based method and show more scalability in dense data.
Related Papers
- A Dynamic Scalable Asynchronous Message Model Based on Distributed Objects(2002)
- → Implementation issues relating to the WPRAM model for scalable computing(1996)5 cited
- → User-Controlled Reflection on Join Points(2007)3 cited
- → Performance Analysis of Controlled Scalability in Unstructured Peer-to-Peer Networks(2012)
- Incremental computation of materialized outer-join views(2011)