Research On Algorithms For Mining Blackhole Patterns Based On Dynamic Spatial Networks

With the development of wireless communication and positioning technology,and the popularity of location-based services,analysing and mining of large-scale mobility data becomes possible.Blackhole pattern mining is a hot issue in mobility data mining.It aims to discover the movement patterns and laws of moving groups converging towards a common target area.And it has extensive application value in practical applications such as public safety,disease prevention and control,and traffic optimization.However,it cannot reflect the distribution of moving groups in geospatial space over time,causing its limitations in the dynamic modeling of moving patterns.In order to overcome this shortcoming,this thesis studies the blackhole pattern mining algorithm based on dynamic spatial network.The main contributions of this thesis are as follows:1.A dynamic spatial network construction algorithm for urban road networks is proposed.The construction process includes: trajectory data preprocessing,extraction of spatial network information,and weight calculation of dynamic spatial network.Due to the complex structure and the large scale of the road network data,the dynamic spatial network construction efficiency is low.In order to improve the construction efficiency,this thesis proposes a fast construction algorithm,which uses spatial index technology to filter the candidate set in the network weight calculation process.Experiments with real data set show that the above algorithm can be effectively applied to modeling the movement behavior of moving objects in urban areas.2.A blackhole pattern mining algorithm based on dynamic spatial network is proposed,including offline and online methods.The blackhole pattern mining is defined as a subgraph discovery problem in dynamic spatial networks.And the group aggregation events are modeled as subgraph structures in dynamic spatial network based on features of group aggregation events,including long duration,precise spatial extent,and large group scale.The offline algorithm,first,divides dynamic spatial network in spatio-temporal dimension.And then heuristic search algorithm is used to detect the blackhole patterns in each partition.In order to improve the efficiency of the mining algorithm,the flow upper bound function is adopted,so that the candidate set of the mining algorithm is efficiently filtered.Finally,in order to deal with online scenarios in practical applications,a blackhole pattern online mining algorithm is proposed,which detects blackhole patterns incrementally from data updated in real time with a time window.Experiments with real data set show that the algorithm can more accurately describe the aggregation behavior of moving groups in spatio-temporal dimension.3.A prototype system for blackhole pattern mining is developed.The system is designed with a three-layer architecture: data management layer,pattern mining layer,and interaction and visualization layer.The data management layer provides construction and access services of dynamic spatial network data,which provides data access support for upper-level modules.The pattern mining layer uses the blackhole pattern mining algorithm proposed in this thesis to detect group aggregation events,and provides two major functional modules according to different application scenarios: offline scene mining and online scene mining.The interaction and visualization layer provides the user with a graphical interactive interface and the mining results are visualized and statistically analyzed.The system can be used to discover and display group aggregation events in urban road networks from real data sets.