Research On Query And Index Technology For Historical Trajectories Of Moving Objects

As the technology of communication,sensing and positioning continues to evolve,the falling price of related equipment,together with the growing demand from society and market,location-aware applications of moving objects are developing rapidly.In addition,it enjoys a promising prospect in the future.Given the possible changes of their time and locations,the moving objects will generate a considerable amount of historical trajectory data.The storage,management and utilization of these data and mining useful information from them can provide more quantitative and scientific decision-making help for production and operation management of enterprises and public institutions,public service of government departments,dailylife arrangement of residents.Consequently,this would be important content and the necessary step to take to achieve the big data strategy.Although there have been many research achievements related to the historical data processing of moving objects,the emerging demands and problems in practice make it a constantly popular research topic.Therefore,this dissertation researches and explores several query and index technologies for historical trajectories of moving objects.The main contributions and innovations of this dissertation are summarized as follows:(1)Propose fistly the problem of historical closing event query based on moving objects' trajectory sets.Design algorithms for trajectory oriented query and point oriented query.Extend node access estimation method from spatial query to spatio-temporal query,and construct two cost models including upper limit estimation for trajectory oriented query and accurate estimation for point oriented query.(2)Explore firstly historical closing event query of uncertain moving objects.Propose the idea of converting uncertain query to certain query by distance metrics.Proved the basic theorem of directly accepting results or pruning under single or multiple uncertain queried objects.To support the new kind of query,U-TB tree is proposed as well as its random insert algorithm and bulk insert algorithm.(3)Introduce firstly the time length uncertainty of not retrieved trajectory segments during the query process and the location uncertainty of moving objects into similarity threshold query for trajectories.Realize the querying alogorithms for certain trajectories and uncertain trajectories respectively.The new measures for dissimilarity and similarity are proposed to make the querying threshold more intuitive,understandable and easy to configure.(4)Propose a new trajectory index structure called Time Partitioned Trajectory-Bundle Tree(TPTB-tree).Based on TPTB-tree,the dissertation presents the heuristic rules for linear search of trajectory-based query and realizes the algorithms of trajectory-based query and range query.To evaluate node access for both algorithms,cost models are built respectively.Verified by extensive experiments on synthesized data sets,it is proved that the structure of TPTB-tree is rational,both models are reliable,and the trajectory-based query algorithm renders satisfying effectiveness,efficiency and scalability.