Research On Algorithms For Spatial-temporal Anomaly Trajectory 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 topic in the field of spatial-temporal trajectory pattern mining, which can be widely used in traffic management and control, animal migration analysis, weather forecast emergency supervision and so on. In order to solve the problem of the anomalous trajectory detection of the massive spatial-temporal trajectories, this thesis uses the Spark parallel fiamework to implement the outlier detection in both spatial and temporal dimensions jointly with cloud computing environment. The main innovative contributions of the thesis are as follows:1. Propose an algorithm STOD(Spatial-temporal Trajectory Outlier Detection) for detecting spatial-temporal anomalous trajectories. Algorithm STOD detects the anomalous trajectory segment by constructing MBB(Minimal Boundary Box). With the computation of distance measurements including overlapping volume, angle and speed,the outlier index can be calculated and the anomaly trajectories can be detected. To improve the efficiency of algorithm STOD, the spatial-temporal grid index is proposed based on grid index, which can reduce the computation of the detection in both spatial and temporal dimensions.2. Propose an algorithm STODP(Spatial-temporal Trajectory Outlier Detection algorithm based on Point density grid) for detecting spatial-temporal trajectory outliers.The algorithm takes advantages of the direction and the density of trajectories, and is able to detect the LAS(Longest Anomaly Sub-sequence) of each complete trajectory.Furthermore, we proposed dynamic distance grid index to balance the difference between sparse region and dense region which improving the rationality of detection results.3. Present two parallel algorithms of the above algorithms denoted as PSTOD and PSTODP based on Spark parallel framework to reduce the time cost. With the utilization of Spark, these algorithms detect the anomalous trajectory segment on each computing node and make it balanced. The experimental results on real taxi datasets demonstrate that these algorithms can effectively detect anomalous trajectories and have high scalability and better speedup.