Research On Algorithms For Mining Time Relaxed Gradual Clustering Patterns From Spatio-Temporal Trajectories Based On Cloud Computing Environment

With the rapid development of wireless communication technology and location position technology,more and more position technology such as intelligent moving terminals can record trajectory of moving objects,and thus a massive spatio-temporal trajectory data can be collected.Time relaxed gradual clustering pattern mining from spatio-temporal trajectory is an important component of spatio-temporal trajectory pattern mining which is widely applied in various aspects such as urban planning,biological protection and animal moving habit research.Aiming at the shortcomings of the current relevant algorithm for mining time relaxed gradual clustering pattern,the thesis mainly studies the effectiveness and efficiency of the pattern mining.The main contributions of the thesis are as follows:1.Algorithm PTRGCP(Parallel algorithm for mining Time Relaxed Gradual Clustering Pattern)for parallel mining time relaxed gradual clustering pattern from spatio-temporal trajectory is proposed which is based on algorithm ClusterGrowth.The algorithm is executed under Spark framework.All sampled points are divided into point sets with different timestamps,and then,point sets are parallel clustered.Timestamp of clusters are respectively transformed into corresponding sequence number,and clusters with same sequence number are divided into a computing node.Cluster lists with inclusion relationship are obtained through intersection action.Finally,all clusters are collected into master node and then maximal interesting time relaxed gradual clustering patterns are output.Experiment results indicate that algorithm PTRGCP has good effectiveness and efficiency.2.To improve the efficiency of algorithm PTRGCP,algorithm PTRGCP-G(Parallel algorithm for mining Time Relaxed Gradual Clustering based on Grid index)is proposed for parallel mining time relaxed gradual clustering pattern from spatio-temporal trajectory based on grid index.The algorithm aims to improve spatial query efficiency of cluster algorithm through building grid index in clustering process.Experiment results show that algorithm PTRGCP-G is more efficient than algorithm PTRGCP.3.Algorithm ITRGCP(Incremental updating Time Relaxed Gradual Clustering pattern)for incremental mining time relaxed gradual clustering pattern from spatio-temporal trajectory.The algorithm is applied to update time relaxed gradual clustering pattern from spatio-temporal trajectory.Preprocessing such as noise reduction and trajectory interpolation are used in spatio-temporal trajectory and then incremental clustering is applied through algorithm IncrementalDBSCAN.Updated time relaxed gradual clustering patterns are obtained through intersection between historical gradual clustering patterns and updated clusters.Finally,all time relaxed gradual clustering pattern are output.Experiment results state clearly that algorithm ITRGCP has good effectiveness.4.To improve the efficiency of algorithm ITRGCP,algorithm PITRGCP based on Spark parallel computing framework is put forward(Parallel algorithm for Incremental updating Time Relaxed Gradual Clustering pattern),the algorithm is used to parallel update time relaxed gradual clustering pattern.Spatio-temporal trajectory data is transformed into the form of key and value,key is timestamp of sampled points and value is longitude and latitude of sampled point.Sampled points with same timestamp are parallel distributed into same point set with different timestamp and then point sets are parallel clustered through incremental algorithm IncrementalDBSCAN.New clusters obtained will be collected into master node and broadcast to all other computing nodes.Historical pattern are mapped into all computing nodes,and then updated gradual clustering pattern are got through incremental intersection algorithm.Experimental results show that algorithm PITRGCP is more efficient than algorithm ITRGCP.