Research On Algorithms For Mining Converging Patterns From Spatio-temporal Trajectories

With the rapid development of location positioning technology, more and more intelligent terminals are equipped with positioning function, these terminals can record the moving object trajectory, which gradually formed a massive spatio-temporal trajectory data. As one of the spatio-temporal trajectory pattern, the converging pattern of spatio-temporal trajectory can be widely used in empirical path recommendation, traffic forecast, urban planning and taxi service. Aiming at the shortcomings of the current algorithms about converging pattern mining, this thesis mainly studies the effectiveness and efficiency of the pattern mining. The main contributions of this thesis are as follows:1. Algorithm CPMP for mining converging patterns based on point clustering is proposed. First, the algorithm locates the density peak points and converging central zones, then identifies the converging groups on consecutive timestamps and then identifies the converging patterns according to the durability of the group patterns.Based on the real-life trajectory data, experiment results show the algorithm is effective and efficient. In order to meet the mining requirements of massive trajectory data, this thesis proposes a parallel implementation algorithm PCPMP using Spark.This algorithm replicates trajectory data, so that the records corresponding to each timestamp contains some trajectory data on a consecutive timestamps, and then using the algorithm CPMP to mine in each record in parallel. Experiment results show that algorithm PCPMP has good scalability and acceleration ratio.2. Algorithm CPMS for mining converging patterns based on segment clustering is proposed. First, the algorithm updates the evolving cluster of each time interval according to the gradual movement of moving object, and then mines the center-intensive converging patterns based on the evolving cluster. Experiments on a real-life trajectory data verify the effectiveness and efficiency of the algorithm.Similarly, in order to cope with the mining requirements of massive trajectory data,this thesis proposes algorithm CPMS based parallel algorithm PCPMS using Spark.The algorithm divides the trajectory data on the consecutive time interval into the same partition by the range partition method, and then computes the evolving cluster of each time interval using the algorithm CPMS in parallel. In order to mine the converging patterns on the consecutive time interval, the algorithm replicates the evolving cluster, so that the records corresponding to each time interval contain some evolving cluster on a consecutive time interval,and then using the algorithm CPMS to mine in each record in parallel. Experiment results show that algorithm PCPMS has a better performance than algorithm PCPMP, and has good scalability and acceleration ratio comparing to algorithm CPMS.