A joinless approach for mining spatial colocation patterns

Jin Soung Yoo, Shashi Shekhar

Research output: Contribution to journalArticlepeer-review

188 Scopus citations

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 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 languageEnglish (US)
Article number1683769
Pages (from-to)1323-1337
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume18
Issue number10
DOIs
StatePublished - Oct 2006

Bibliographical note

Funding 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.

Keywords

  • Association rule
  • Relocation pattern
  • Spatial data mining
  • Spatial neighbor relationship

Fingerprint

Dive into the research topics of 'A joinless approach for mining spatial colocation patterns'. Together they form a unique fingerprint.

Cite this