A fast space-saving algorithm for maximal co-location pattern mining. (30th November 2016)

• Record Type: Journal Article
• Authors: Yao, Xiaojing; Peng, Ling; Yang, Liang; Chi, Tianhe
• Is Part Of: Expert systems with applications. Volume 63(2016)
• Page Start: 310
• Page End: 323
• Publication Date: 2016-11-30
• Subjects: Spatial data mining -- Maximal co-location patterns -- Sparse undirected graph -- Condensed tree -- Hierarchical verification; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2016.07.007
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A new algorithm for mining maximal co-location patterns was presented. A fast, sparse-graph-based strategy was used for mining candidate co-locations. A condensed-tree-based strategy was to reduce the time and space complexities. The new algorithm was compared with two other maximal co-location algorithms. Abstract: Real space teems with potential feature patterns with instances that frequently appear in the same locations. As a member of the data-mining family, co-location can effectively find such feature patterns in space. However, given the constant expansion of data, efficiency and storage problems become difficult issues to address. Here, we propose a maximal-framework algorithm based on two improved strategies. First, we adopt a degeneracy-based maximal clique mining method to yield candidate maximal co-locations to achieve high-speed performance. Motivated by graph theory with parameterized complexity, we regard the prevalent size-2 co-locations as a sparse undirected graph and subsequently find all maximal cliques in this graph. Second, we introduce a hierarchical verification approach to construct a condensed instance tree for storing large instance cliques. This strategy further reduces computing and storage complexities. We use both synthetic and real facility data to compare the computational time and storage requirements of our algorithm with those of two other competitive maximal algorithms: "order-clique-based" and "MAXColoc". The results show that our algorithm is both more efficient and requires less storage space than the other two algorithms.