Research On Key Issues Of Moving Object Trajectory Data Management

With the rapid development of mobile Internet and Internet of Vehicles technology and the widespread application of mobile terminals,the moving object trajectory data is generated at an extremely fast rate and exploding in the massive moving environment,the collection,processing,storage,query and service of the data show the following characteristics:firstly,the number of moving objects is huge,and mobile devices have a high frequency and real-time of data acquisition for each object,so that location based services often need to face a challenge of a larger number of user concurrent accessing,the system is under tremendous pressure of data processing at all times,and the parallel optimization technology is a necessary measure to narrow the gap between the growing data size and the quality of service;each object has a large amount of trajectory data,but the value density of trajectory data is low,so that the real-time transmission may consume a large amount of network communication resources,meanwhile,storing every point of the original trajectory is a disaster for any storage system,and traditional methods are no longer suitable for processing moving object trajectory data;the query patterns that need to be processed are varied for a single object,such as spatial query,time range query and time slice query,efficient retrieval of moving object trajectory data relies on data index,so in order to support a variety of different types of queries,how to establish an effective spatio-temporal index is the critical problem to be solved.In this dissertation,several critical problems about the management of moving object trajectory data are deeply studied.The dissertation studies some key technologies,such as parallel processing for location of moving object,simplification and storage of trajectory data.The specific research content as follows:(1)This dissertation proposes a spatial mapping based parallel processing framework that maximizes the degree of parallelism for massive moving environment.The framework exploits the grouping of the update operations to reduce the lock contention among multiple physical threads.By defining the boundary region,the framework can alleviate the conflicts of multiple location processing by using the spatial mapping strategy.On this basis,as for the mutual accesses to the boundary objects,the lock-free operations are introduced for further improving the scalability of the proposed framework.This dissertation firstly conducts detailed experiments by validating the parameters for the proposed framework with variant running conditions.Using the synthetic data,the experiments show that framework is much faster than the existing fastest grid based parallel method,while providing high consistency in accordance with the serialized processing.(2)For the original trajectory sequence of the moving object collected from the mobile devices,the linear prediction method used in the existed speed based simplification method only consider two newly acquired trajectory points.For fluctuant trajectory,the error between the real velocity vector and predicted velocity vector calculated by this method is larger,which lead to the frequency triggering of the constraint conditions for simplification and generate more simplification trajectory points.The dissertation constructs a backtracking based simplification framework for moving object trajectory.The framework uses the velocity,time,distance and the quantity threshold of the cumulative historical trajectory points to dominate the opportunity of simplication.The original trajectory sequence between the present moment and the starting time of backtracking is simplified by the offline simplification,and a precise description of moving object trajectory is established,which privides the basic for the storage and query of data.In this framework,the dissertation proposes a new velocity prediction method which utilizes the new reduced points(include the points being replaced)and time range covered by these points to construct several vectors.In order to narrow the gap between the prediction speed and the real speed in the future and reduce the number of simplification trajectory points,the framework computes the prediction velocity by above-mentioned vectors.Then,the optimal line algorithm is optimized in the framework.Aim at the high time complexity of the optimal line algorithm,the point set is used to store the necessary access edges in the acyclic graph reducing the distance calculation and the access overhead.This is to reduce the time complexity of the algorithm and improve the simplification efficiency of the moving object trajectory.The experiment results show that the velocity prediction method in this dissertation can effectively improve the compression ratio of the high fluctuant trajectory.Meanwhile,optimization strategy of the optimal line algorithm can effectively improve the simplification efficiency.Moreover,compared with the existing simplification methods,the simplification method proposed in this dissertation has higher accuracy in the case of higher fluctuant coefficients.(3)Due to the existing storage structures take the spatial dimension as the main index object,the processes of time-dependent queries are inefficient.The dissertation proposes a disk based storage structure for trajectory data,a temporal index is built above and below the spatial index.The time-dependent queries first filter the temporal conditions using the versioned periods of trajectory storage nodes.For the queries that cross more than one versioned period,the query manager divides them into multiple sub-queries and then parallel processing on the trajectory storage nodes.Aiming at the discreteness and randomness of the I/O processes in the bulk trajectory data store,the dissertation proposes the optimization strategy of buffer for read-write process.This dissertation proposes a disk based k-nearest neighbor query algorithm which exploit the geometry characteristic of rectangle and the density distribution of trajectory points.The algorithm chooses appropriate radii to expand the search area and reduce the unnecessary access overhead in search process.The experiments first evaluate the parameters of the storage structure on different datasets.The experiment result show that the proposed storage optimization method can effectively improve the storage performance of the index under the relative optimal parameter configuration.Using the synthetic data,the optimal versioned period of the storage node is determined in the experiments.Compared with the Traj Store under the optimal versioned period,the experimental results show that the storage performance of the structure proposed in this dissertation is very close to Traj Store.However,the structure proposed in this dissertation has better time-dependent query performance.In summary,with the architecture for moving object trajectory data management system,this dissertation first proposes a space mapping based parallel processing structure.Then it studies the optimization strategy for the backtracking based online trajectory simplification framework.Finally,it designs a spatio-temporal clustering based trajectory storage structure.Experiments have done on multiple public dataset of the moving objects and their trajectories,and the result indicates the effectiveness of the proposed structures and algorithms in the paper.