Maximal Cliques Generating Algorithm for Spatial Co-location Pattern Mining

The spatial co-location pattern represents the relationships between spatial features that are frequently located close together, and is one of the most important concepts in spatial data mining. The spatial co-location pattern mining approach, which is based on association analysis and uses maximal cliques as input data, is general and useful. However, there are no algorithms that can generate all maximal cliques from large dense spatial data sets in polynomial execution time. We propose a polynomial algorithm called AGSMC to generate all maximal cliques from general spatial data sets; including an enhanced existing materializing method to extract neighborhood relationships between spatial objects, and a tree-type data structure to express maximal cliques. AGSMC constructs the tree-type data structures using the materializing method, and generates maximal cliques by scanning the constructed trees. AGSMC can support the spatial co-location pattern mining efficiently, and is also useful for listing maximal cliques of graph whose vertexes are a geometric object.