EHUCM:An Efficient Algorithm For High Utility Co-Location Pattern Mining

The development of location sensors,wireless networks,and ubiquitous computing are generating large amounts of valuable spatial data,and spatial data mining aims to mine previously unknown and meaningful patterns or knowledge from the massive amounts of valuable data.Spatial co-location pattern mining is an interesting data mining task in spatial data mining,aim ing to discover correlations among spatial features.However,the limitation of co-location pattern mining is that all features are considered equally important,which may lead to some important but non-prevalent patterns being missed,while some unimportant but prevalent patterns are found.To address this issue,high utility co-location pattern mining has emerged.In contrast to co-location pattern mining,high utility co-location pattern mining considers the case where each feature has a utility.In high utility co-location pattern mining,utility value is used to measure whether a pattern is interesting.Since the utility measure does not satisfy the anti-monotonicity,the mining algorithm based on anti-monotonicity cannot be simply applied to the high utility co-location pattern mining,so the research of mining high utility co-location patterns is challenging.The existing high utility co-location pattern mining algorithm suffers from high time complexity and high space complexity,which is difficult to adapt to the task of mining patterns in mass spatial data.Focusing on these problems,in this paper,an Efficient High Utility Co-location pattern Mining algorithm,named EHUCM,is proposed,which first introduces the concept of participating objects of features.EHUCM replaces the method of generating table instances with the method of generating participating objects of features.At the same time,to quickly generate participating objects of feat ures in a candidate pattern,the idea of neighborhood materialization is adopted,and the spatial neighbor relationships among objects are pre-stored in the data structure of feature-object neighbor tree.Due to the utility measure does not satisfy the anti-monotonicity,an effective pruning strategy are proposed to predetermine candidate patterns that do not satisfy the minimum utility index threshold and filter the hopeless candidate patterns to achieve pruning the search space.Finally,this paper conducts extensive experiments on real and synthetic datasets to verify the efficiency and scalability of the EHUCM algorithm.Experiments show that the EHUCM algorithm is not only 10 times or even100 times faster than the traditional high utility co-location pattern mining algorithm but also has better scalability.