Research On Algorithms For Spatial-Temporal Trajectory Outlier Detection In Cloud Computing Environment

In recent years, with the development of global positioning wireless communication and electronic digital products, more and more vehicle equipment and handled devices with positioning function have been widely used. This allows people to record the location information of moving objects with high space-time resolution, and generates a lot of spatial and temporal trajectory data. Trajectory outlier detection is an important research content in the field of spatial-temporal trajectory pattern mining, which can be widely used in traffic planning and detection, natural phenomenon analysis and so on. In order to solve the problem of the anomalous trajectory detection of the massive spatial-temporal trajectories, this paper uses the MapReduce parallel computation model to realize trajectory anomaly detection in cloud computing environment. The main innovative contributions of the thesis are achieved as follows:1. Propose two parallel algorithms for detecting anomalous trajectories based on MapReduce, PTRAOD (Parallel algorithm for TRAjectory Outlier Detection) and GPTRAOD (Grid-based Parallel algorithm for TRAjectory Outlier Detection). Algorithm PTRAOD detects the anomalous trajectory segment on each computing node based on MapReduce framework. Then, the anomalous trajectory segment detected by each node are combined, and anomalous trajectory length accounted for the proportion for the whole trajectory threshold value is calculated. In order to reduce some unnecessary calculations, algorithm GPTRAOD is proposed. It makes use of the grid index to realize regional query, and the candidate set for the calculation of the similarity of the trajectory segment is reduced. Finally, the amount of computation is reduced.2. Present a parallel algorithm for detecting trajectory outliers based on evolutionary computation, called PDAT-TOP (Parallel Detecting Anomalous Trajectories based on TOP-EYE). The algorithm takes advantages of MapReduce framework to group the trajectories and make each node balanced. The experimental results demonstrate that the algorithm can effectively detect anomalous trajectories, and it has high scalability and better speedup.3. Introduce an algorithm for detecting trajectory outliers between regions of interest, called DATIR (Detecting Anomalous bnormal Trajectories between Interest Regions). Unlike the existing algorithm to detect from the local sample points, algorithm DATIR takes into account the local and global characteristics of the trajectory, and uses clustering method to detect the standard path and anomalous trajectory between interest regions. In order to improve the efficiency of mining trajectory from massive trajectory datasets, the parallel algorithm for detecting trajectory outliers based on MapReduce framework, which is called PDATIR (Parallel algorithm for Detecting Anomalous Trajectories between Interest Regions), is presented. The experimental results demonstrate that algorithm DATIR can effectively detect the anomalous trajectories between regions of interest, and algorithm PDATIR has the high scalability and good speedup ratio.