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 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 spatial data which are 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.
|Original language||English (US)|
|Number of pages||15|
|Journal||IEEE Transactions on Knowledge and Data Engineering|
|State||Published - Oct 2006|
Bibliographical noteFunding Information:
This work was partially supported by US National Science Foundation grant 0431141 and Oak Ridge National Laboratory. The content of this work does not necessarily reflect the position or policy of the government and no official endorsement should be inferred. The authors are thankful to Kim Koffolt for her feedback that helped improve the readability of this paper.
- Association rule
- Relocation pattern
- Spatial data mining
- Spatial neighbor relationship