Mining Maximal High Utility Co-location Patterns from Large-Scale Spatial Data

High utility co-location patterns (HUCPs), which are groups of spatial features considering the utility values of these spatial features, can effectively expose valuable relationships and knowledge from spatial data. However, the mining result normally contains too many HUCPs, this makes it difficult for users to absorb and apply the mining result. This work proposes a concise representation of the mining result, maximal HUCPs. A HUCP is maximal iff it has no supersets that also are HUCPs. A straightforward way to discover maximal HUCPs is to first find all HUCPs and then filter maximal HUCPs. However, at present, the methods of mining HUCPs employ a common generation-test candidate level-wise traversal mining framework combined with some pruning strategies. These methods are relatively inefficient and require a large storage when dealing with large-scale spatial data. In order to efficiently discover maximal HUCPs, this work adopts a clique-hash table-based top-down traversal mining method. First, all neighboring instances are enumerated by a set of maximal cliques. Then these cliques are further arranged into a hash table structure. After that, the mining process iterates all the keys of the hash table structure beginning from the largest keys. If the keys are maximal HUCPs, the mining process continues with the next sizes of keys. While the keys are not maximal HUCPs, the directed subsets of the keys are generated and examined in the next iterator. Experimental results on both synthetic and real spatial data sets show that the proposed method is effective and efficient.