Research On Improvement And Parallelization Of Spatio Temporal Trajectory Gathering Mining Algorithm

Location-based mobile applications generate mass trajectory data,identifying variation trend and regularity from these spatio-temporal trajectory data is useful for guiding resident trip planning,road flow monitoring,air quality monitoring,earthquake and hurricane prediction and avoidance,etc.For the massive spatio-temporal trajectory data,the existing trajectory gathering mining methods have the problems of low accuracy and low efficiency.This thesis starts with the accuracy and efficiency of gathering mining and proceeds from the following aspects.The main research results are as follows:In view of the fact that the compression algorithm in mining process does not consider the motion state information of moving objects,which leads to the low accuracy of the trajectory extraction,a Direction Speed Synchronous Distance(DSSD)algorithm considering the direction,speed and offset information is proposed.This algorithm uses the direction angle of the adjacent line segment to represent the moving direction variation of the trajectory point,uses the ratio of the length of the trajectory segment to the time to express the moving speed variation of the trajectory point,and uses the synchronized Euclidean distance with time information to represent the offset of the trajectory point.By preserving the trajectory points with significant changes in the motion state,the algorithm is able to compress the trajectory more accurately.Experimental results verify the effectiveness and efficiency of the proposed algorithm.In order to improve the efficiency of the clustering algorithm in the mining process,a clustering algorithm based on R* tree index(Discovering Closed Crowds by R*-tree,DCCR)is proposed.The algorithm first segments the trajectory data and then performs DBSCAN density clustering based on the R* tree index for the trajectory segments.For gathering pattern detection,aggregation detection algorithm based on clustering center is used to mine gathering mode.The experimental results show that compared with the existing mining algorithms,the proposed algorithm improves the efficiency at the same time guarantees the accuracy.Aiming at the large computational complexity of the trajectory gathering pattern mining algorithm under massive data,this thesis proposes a parallel mining algorithm named RPTRAJ-DBSCAN(R* tree Parallel Density-Based Spatial Clustering of Applications with Noise)based on Hadoop platform.The algorithm includes three stages: trajectory compression,trajectory clustering and gathering detection.Trajectory compression and clustering processes are parallelized for time independence while gathering mining process is processed in a serial way based on time dependence.Experimental results show that the proposed algorithm performs better than the single-node algorithm,which effectively improves the efficiency of the mining algorithm.