Generalization Methods For Trajectory Data

With the rapid development of computer technology and spatial information theory,the trajectory data of moving objects has an explosive growth. Massive trajectory dataurgently demands for faster transmission, larger storage and stronger privacypreservation. As an important branch of moving objects data mining, trajectorygeneralization aims at abstraction of trajectory data, which is useful for dimensionalityreduction, privacy protection and multi-granularity analysis.This thesis focuses on trajectory data generalization. In conclusion, this thesisconsists of the following achievements.a. Multivariate generalization for trajectory dataMost of the trajectory generalization algorithms only consider the spatial features,which result in the precision decrease and limit of generalized results. A multivariategeneralization method for trajectory data, named TRMGEN, is presented to overcomethe shortages existing in current algorithms. Firstly, trajectory point multivariateclustering algorithm (TPM-DBSCAN) is given to cluster the points according to thepoints’ features including position, velocity, acceleration, angular displacement, etc.Then, for clustering, we calculate the information gain of features to optimize theparameters’selection. Finally,in orderto evaluatethegeneralizationeffect, on onehand,information loss is introduced to calculate the shape difference between the generalizedtrajectory and original trajectory; on the other hand, cluster respectively on generalizedtrajectories and original trajectories, and calculate the similarity of two clusteringresults. Experiments on hurricane dataset show that generalized trajectories producedby TRMGEN well maintains features of moving objects, and get accurate and effectiveresults when applied into further processing include clustering and well reduce therunning time.b. Trajectory data generalization based on spatial iterative partition and differencereconstructionFor the efficiency problem caused by points clustering based space discretization,and defects of uniform meshing, Trajectory data generalization method based on spatialiterative partition and difference reconstruction, named TRGEN-SIPDR is put forward.Firstly, spatial iterative partition algorithm is proposed to discretize the space accordingto the distribution of trajectory points. Secondly, time-constraint is used to merge theadjacent grids that the trajectory reciprocate continuously. Finally, in order to meet thedemand for different generalization degree, generalized trajectory difference reconstruction method is given for users’ selection. Experiments show that TRGEN-SIPDR maintains well effectiveness and efficiency. Moreover, comparisons ofTRGEN-SIPDR and TRMGEN from several aspects show that both methods haveimplemented the basic functionalities of trajectory generalization. However, TRMGENapplies multivariate in generalization, while TRGEN-SIPDR applies differencereconstruction, so that user can control the generalization degree according to their ownneeds.c. Design and realization of trajectory data generalization system.Based on theory in the thesis, we design and realize the trajectory datageneralization system. In this system, users can generalize various kinds of trajectoryand evaluate the generalization effect by using methods of TRMGEN or TRGEN-SIPDR. At each step, a friendly parameter input interface and visualization display forthe data process results are presented, as long as a good performance for differenttrajectories.