Research On Algorithm For Mining Gathering Pattern Of Spatio-Temporal Trajectory In Cloud Computing Environment

With the application of location-acquisition technologies, including telemetry attached on wildlife, GPS set on cars, WLAN network and mobile phone, people can record the trajectories of all moving objects in higher spatio-temporal resolution, which generating massive spatio-temporal data in the form of trajectories. It contributes to our research on human behavior patterns, transport and logistics, animal behavior and marketing and so on by analyzing the spatio-temporal trajectory of different moving objects. The spatio-temporal trajectory pattern mining is an important content of data mining. As an important part of the spatio-temporal trajectory pattern, the gathering pattern of spatio-temporal trajectory is a behavior pattern of a set of spatio-temporal moving objects, moving together within a certain period of time. Through mining the spatio-temporal trajectory, we can discover meaningful gathering patterns to help people monitor and predict some unusual group incidents. The main research content of this thesis are the algorithms of mining gathering pattern from spatio-temporal trajectory, and the main research achievements are as follows:1. Propose a parallel algorithm to discover gathering pattern from spatio-temporal trajectory, called PDGP(Parallel algorithm for Discovering Gathering Pattern), using MapReduce parallel programming model to implement this parallel algorithm. To improve the efficiency of trajectory clustering, PDGP algorithm process different dataset with clustering algorithm on different computing nodes. The experimental results demonstrate that the parallel algorithm I proposed is much more efficient compared to the origin algorithm. The most important thing is that, with the increase of number of computing nodes, the parallel algorithm shows high efficiency obviously. And the parallel algorithm shows increasingly obvious advantages in the rapidly expanding data.2. Present a grid-based algorithm for spatio-temporal trajectory clustering, called GTRAJ-DBSCAN(Grid-based algorithm for TRAJectory-DBSCAN), meanwhile realize a grid-based parallel algorithm for spatio-temporal trajectory clustering in the cloud computing environment, called GPTRAJ-DBSCAN(Grid-based Parallel algorithm for TRAJectory-DBSCAN). The experimental results demonstrate that, compared to the TRAJ-DBSCAN algorithm, the GTRAJ-DBSCAN and GPTRAJ-DBSCAN algorithms improve the efficiency of clustering by employing the grid index to realize regional query and reduce some unnecessary calculations.3. Propose an algorithm based on center-distance to discover closed crowds, called CDCC(algorithm based on Center-distance for Discovering Closed Crowds). Compared to the DCC algorithm, the CDCC algorithm get the center of each cluster by computing the average position of all moving objects in the same cluster, and then calculate the distances between each center of clusters to get the distance of each cluster, which greatly reduce the distance computation to improve efficiency of discovering closed crowd, at the same time, guaranteeing the result accuracy.