Research On Clustering Algorithms For Massive Trajectory Data

In recent years, with the rapid progress of the satellite technology, global positioning technology, sensor networks and electronic mobile devices, applications based on the location information are becoming more and more popular in our daily life. Real-time traffic monitoring systems and moving objects real-time positioning systems are becoming more and more widely used, following by is the vigorous development of location based service and the increasing popularity of mobile social networks. The real-time location information of a moving object with the change of time generates a trajectory of the moving object within a certain period of time. Different kinds of mobile terminals produce huge amounts of trajectory data every day. These data accumulated together is explored and analyzed for different types of applications. These huge collections of trajectory data often hide important and interesting information which conventional systems and classical data mining techniques are unable to utilize effectively and timely. In addition, the processing of spatiotemporal data is more complex, which makes the data processing tasks increasingly onerous. How to manage and utilize the trajectory data effectively and how to find out the potentially valuable information from them remains a big challenge for the researchers in this field. Among the available methods for data analysis, clustering as one of the most important data mining method is becoming more and more widely used in trajectory data mining.After studying the related research background, this thesis mainly focuses on the method for decomposing a whole trajectory into sub-trajectories, the measurement of the distance between two trajectories, the sub-trajectory clustering method and real-time updating method to trajectory clusters. Considering that the trajectory data of the moving objects contain multiple attribute dimensions, such as location, time, speed, direction and so on, a method for trajectory data analysis shall differ from those for analysis of other types of data. When dealing with the trajectory data processing problem, different from the traditional data processing methods, we no longer consider the trajectory as a basic processing unit. In order to fully consider the multi-dimensional information, we decompose a whole trajectory into several sub-trajectories and treat each sub-trajectory as a real basic processing unit. For the distance measurement problem, this thesis puts forward a new multidimensional distance metric method that considers time, space and speed properties simultaneously. This method can effectively measure the similarity between different sub-trajectories according to different application scenarios and hence improves the accuracy of trajectory data processing. For the problem of online updating trajectory clusters, this thesis proposes a new storage structure for the real-time data updating algorithm. This algorithm maintains the latest sub-trajectory clustering results of the moving objects and provides the convenience for real-time queries on the trajectory data. Through experiments on real taxi GPS trajectory data, this thesis proves that the proposed new method achieves better processing efficiency and better clustering results compared with related data processing algorithms. The research results of this thesis have important academic value and broad application prospects.