Research On Algorithms For Trajectory Similarity Queries

With the rapid development of global positioning technology and wireless communication network,it is possible to obtain a large number of trajectory data through mobile terninals.However,there are some problems in trajectory data,such as large scale,low quality and different sampling rates,which directly affect the mining effect and computing efficiency of trajectory data.In order to deal with these problems,academia has carried out a lot of research work in the aspect of trajectory data management.Among them,the similarity queries of trajectory are one of the research hotspots in academia in recent years.This research mainly includes two core issues:the similarity measurement method of trajectory and the corresponding query algorithm.The former determines the similarity effect of query results,while the latter deternines the efficiency of similarity query computation.This thesis mainly studies the similarity query of spatio-temporal trajectory and semantic trajectory.The main contributions of the thesis are achieved as follows:1.Propose a spatio-temporal trajectory similarity query algorithm for uneven distribution of sampling points.Most spatio-temporal trajectory similarity measurement methods are sensitive to the distribution of sampling points.The moving speed of the moving object cannot be kept constant.It may cause uneven distribution of sampling points in the trajectory.Compared with the sparse trajectory segment of sampling points,the proportion of similarity measure of dense trajectory segment in the final measurement result will be exaggerated,which will affect the final result of spatiotemporal trajectory similarity query.In order to solve this problem,a query algorithm based on similarity subtrajectories is proposed to compute the similarity of spatio-temporal trajectory.The similarity of spatio-temporal trajectory is no longer calculated with the trajectory points as the main body.In addition,this thesis uses the"filter-verify" computing framework to improve the query efficiency of space-time trajectory.In the filtering stage,the similar trajectory points in the similar subtrajectories are adjacent to each other.Based on the spatial grid index,the similar values of each trajectory are quickly estimated and the candidate similar trajectories are obtained.In the verification stage,the candidate trajectories are verified by dynamic programming,and the final result set is obtained.Experiments based on real trajectory data verify the effectiveness and feasibility of the proposed query algorithm.2.Propose a similarity semantie trajectory query algorithm based on the longest common subsequence.Since both temporal and spatial attributes and semantic information are included in the semantic trajectory,similarity queries must take into account both temporal and semantic requirements.In order to solve this problem,this thesis proposes a semantic similarity trajectory query method based on the longest common subsequence,which takes into account both spatial and semantic similarity measurement requirements when calculating similar trajectory points.In order to improve query efficiency,this method adopts the"filter-validation" computing framework.In the filtering stage,similar eandidate trajectories are obtained by establishing the spatial grid index with semantic infornation,searching for similar trajectory points quickly,and estimating similarity in linear time.In the verification stage,based on dynamic programming idea,the similarity threshold is used to reduce the comparison range of similar trajectory points and improve the verification efficiency Experiments based on real trajectory data verify the effectiveness and efficiency of the algorithm.