Portal de Periódicos da CAPES

A Joinless Approach for Mining Spatial Colocation Patterns

2006; IEEE Computer Society; Volume: 18; Issue: 10 Linguagem: Inglês

10.1109/tkde.2006.150

2326-3865

Jin Soung Yoo, Shashi Shekhar,

Advanced Database Systems and Queries

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.