Research On Spatial Co-location Pattern Mining Based On Maximal Cliques And Hash Maps

Nowadays,global positioning systems,handheld devices,vehicles with positioning systems,and many other fields daily generate vast amounts of spatial data,and the spatial data implies very important and potential value.The purpose of spatial data mining is to present meaningful and valuable information hidden in spatial data.Spatial co-location pattern mining is an important branch of spatial data mining.Traditional algorithms for co-location pattern mining is to use a minimum prevalence threshold to determine whether a co-location pattern is prevalent or not.However,it is not easy to specify a suitable prevalence threshold in practice.In addition,the performance of these approaches is limited because of the expensive cost of identifying row-instances of co-location patterns.Moreover,the mining results often contain too many patterns,and the information of these patterns overlaps each other,resulting in redundant information,which makes it difficult for users to absorb and understand mining results.In this thesis,a new method based on maximal clique and hash table is proposed to discover complete and correct co-location patterns,which not only reduces the huge overhead of identifying row-instances of co-location patterns,but also avoids the problem of the sensitivity to the minimum prevalence threshold.The co-location patterns and its row instances is obtained by enumerating the maxial cliques.In order to quickly obtain the row instances in maximal cliques,a hash table is designed based on the enumerated maximal cliques.Take advantage of the random access feature of hash tables to speed up the collection of row instances in each pattern.Then,a twostage mining framework is proposed and all prevalent co-location patterns can be filtered efficiently.Aiming at the problem of information redundancy in the prevalent co-location patterns,this thesis also proposes the concept of meta co-location patterns.The meta co-location pattern can effectively reduce the number of prevalent co-location patterns,reduce the redundancy between patterns,and will not lose too much participation information.It is proved by experiments that the meta co-location pattern avoids the excessive number of prevalent closed co-location patterns and the loss of too much participation information in maximal co-location patterns.Finally,a prototype system for mining co-location patterns is developed to makeusers can freely set parameters based their applications.The system will mine according to the parameters set by users and display the results on the interface.