Research On Distributed Frequent Pattern Mining From Vehicle GPS Trajectories

With the deep integration of GIS,mobile Internet and Internet of Things technologies with urban intelligent transportation systems,large-scale trajectory data can be efficiently acquired,transmitted and stored.The trajectory data is time series data obtained by sampling the continuous motion position of a moving object in a specific spatio-temporal environment.The trajectory data in the urban road network implies the travel laws of urban citizens and the dynamic changes of the traffic state of the urban road network,which further embodies the wisdom of urban crowds travel.Therefore,the trajectory data in the urban road network has significant research value in the fields of urban planning,traffic management,traffic service recommendation,and location prediction.Aiming at the trajectory data in the urban road network,the trajectory frequent sequence pattern mining method is one of the cardinal manners to extract valuable information and discover its hidden laws.Taking taxi's historical trajectory data as the research object,this thesis proposes a method for mining frequent sequence patterns of trajectories based on index collections,improving the issues existing in traditional frequent trajectory sequence pattern mining methods that the Apriori Traj algorithm will cause frequent disk IO problems during the mining process and the Traj-Prefix Span algorithm will perform poorly in the face of long trajectory sequence,uneven trajectory sequence length distribution,or data set mining with a large number of trajectory sequence items.While taking the effect of trajectory sequence pattern mining into account,this method effectively reduces the time consumption of the mining process and improves the performance of the trajectory frequent sequence pattern mining method.Furthermore,for satisfing the demands of large-scale trajectory frequent sequence pattern mining,the proposed method is implemented in parallel based on a distributed computing framework.Finally,a route recommendation method based on frequent trajectory sequence patterns is proposed,which can effectively provide users with optimized travel route recommendation services.The concrete research work of this thesis is as follows:(1)A preprocessing method for the original GPS trajectory data is proposed,which realizes the conversion from the original GPS trajectory data to the road section trajectory data.Data cleaning,trajectory segmentation,and trajectory compression are performed on the original GPS trajectory data,and the original GPS trajectory data is transformed into a road segment trajectory sequence convenient for frequent sequence pattern mining.(2)This thesis proposes an index collections-based frequent trajectory sequence pattern mining method FTPMIC.Compared with the existing trajectory sequence pattern mining methods,the proposed method has better time performance while obtaining the same mining effect.The FTPMIC method records the position of the items in the trajectory sequence of the road segment in the entire database through the idea of index collection;in the mining process,two hash tables are used to respectively update the index collection of each trajectory sequence item and the trajectory sequence collection adjacent to each trajectory sequence item.Therefore,there is no need to repeatedly scan the original trajectory database during the mining process,and only the index collection of the trajectory item and its adjacent trajectory sequence can be obtained from the corresponding hash table to obtain the candidate trajectory sequence for the next round.(3)For meeting the demands of frequent sequential pattern mining of large-scale trajectories,the FTPMIC algorithm is improved to the parallel D-FTPMIC algorithm based on the RDD abstract data model in the Spark distributed computing framework.Meanwhile,a data partition strategy considering load balancing is proposed to further improve the execution efficiency of the proposed method in a distributed environment.The quantitative relationship between trajectory data sets of different scales and their optimal partition number is studied,and the empirical estimation formula for the optimal number of partitions under the condition of different scale trajectory data sets is given.(4)Combining the above methods,a route recommendation method based on frequent trajectory sequence patterns is proposed to provide users with optimized travel route recommendation service.For evaluating the reasonableness of the route recommendation method,four simulation scenarios are set and the route recommendation method is analyzed and evaluated through simulation cases.The results show that the routes recommended for users are in line with the travel habits of most skilled drivers such as short driving distance,less driving time,high average speed,etc.