A Join-less Approach for Co-location Pattern Mining: A Summary of Results

Date of Submission: 
December 29, 2005
Report Number: 
05-042
Report PDF: 
Abstract: 
Spatial co-location patterns represent the subsets of features whose instances are frequently located together in geographic space. For example, MacDonald's and Burger Kings are likely co-located in a local business map. Co-location pattern discovery presents challenges since the instances of spatial features are embedded in a continuous space and share a variety of spatial relationships. A large fraction of the computation time is devoted to identifying the instances of co-location patterns. We propose a novel join-less approach for co-location pattern mining, which materializes spatial neighbor relationships with no loss of co-location instances and reduces the computational cost of identifying the instances. The join-less co-location mining algorithm is efficient since it uses an instance-lookup scheme instead of an expensive spatial or instance join operation for identifying co-location instances. We prove the join-less algorithm is correct and complete in finding co-location rules. The experimental evaluations using synthetic datasets and real world datasets show the join-less algorithm performs more efficiently than a current join-based algorithm and is scalable in dense spatial datasets.