The Research Of Trajectory Search In Geopositioning Logs

In recent years,with the rapid development of mobile information technologies and location-aware chip-integrated mobile terminals,people can easily access to personal daily trajectories and the Cloud can easily obtain data of personal daily trajectories.With more researches based on geographical position information come more applications and services which are closely linked to geographical position information.These new researches and applications of spatio-temporal trajectory facilitate people's daily life,but also bring a greate challenge to the effective management of spatio-temporal data in geodatabase.At the same time,how to effectively use these vast amounts of data has become a hot topic in the area of the management and utilization of spatio-temporal data.The k-BCT query(k Best-Connected Trajectories query)is a recently proposed problem for the k-nearest neighbor search with numerous query points.It has widely used in the field of recommending travel routes and the research on individual traveling patterns.However,because of the only consideration of Euclidian distance without the time factor in k-BCT query,the k-BCT query does not consider the time factor and the life guidance of it for practical application is limited.Therefore,this paper presents an improved query model,and then proposed two responses algorithms for it.And at the last,we proved the effectiveness of these two algorithms by performing relevent experiments.This paper can be roughly divided into two parts:First,by analyzing k Best-Connected Trajectories(k-BCT),we found that k-BCT only takes into account of the Euclidian distance between the trajectory points,which means that its has limited guidance in real life because the trajectory points in positioning log has a property of time and trajectory differences in time represent different meaning in real life.Therefore this paper attempts to improve k-BCT searches by proposing k Weighted Connected Trajectories(k-WCT)which is based on weight of trajectory points and takes into account of time and Euclidian distance,and proves that k-WCT provides more guidance in real life.We also propose a response algorithm in regard to k-WCT,the Rtree-FA algorithm based on the Max Rtree space index,and proves that this algorithms regarding to k-WCT are better to find qualified trajectories than BF-O regarding to k-BCT algorithm through comparative experiment analysis.Secondly,the Rtree-FA algorithm we proposed can solve the problem of k-WCT query,but because of its data structural characteristics,it has several dects,such as the overmuch queries,excessive consumption of CPU,high I/O occupancy rate.For the purpose of compensating those defects of Rtree-FA algorithm on the lower query performance and hight I/O occupancy rate and bringing a greater query performance of k-WCT,we propose the building of combining the grid structure and the Voronoi diagram to form a hybrid index,and then propose a trajectory search algorithm based on this hybrid grid index,the Grid-FA,which has a greater query performance of k-WCT than Rtree-FA.There are several advantages in this Grid-FA algorithm,such as a small query range,a rapid positioning,a less query count and a low I/O occupancy.At the last,we prove that the Grid-FA algorithm performs better than the Rtree-FA algorithm by comparative experiment analysis.