Research On K-nearest Neighbor Query Of Uncertain Trajectory Under Privacy Protection

With the continuous development of spatial database and GPS system,users' massive trajectory storage has gradually become a reality.The query technology for trajectory data has also become a research hotspot of many scholars.But at the same time,because the trajectory data contains a large amount of user personal information,once leaked,it will have serious consequences for the user's personal privacy.Therefore,the privacy protection of trajectory data has become an urgent problem to be solved.The uncertainty of trajectory data is caused by the accuracy problem of GPS system and transmission delay.Based on the above reasons,this paper solves the problem of privacy protection of uncertain trajectory.In addition,considering the real application environment,the k-nearest neighbor query problem of uncertain trajectory in road network environment is studied.Firstly,in the aspect of privacy protection of uncertain trajectories,this paper proposes a differential privacy protection method for uncertain trajectories.This method is mainly divided into three steps.Firstly,the uncertain trajectory data is preprocessed based on the location and shape of the grid.Secondly,the privacy budget is adaptively allocated according to its own uncertainty,so as to ensure the degree of privacy protection of the data and increase the availability of the data at the same time.Finally,a predictive publishing method of uncertain trajectory data is proposed.According to the state transition matrix of Markov chain,the possible false location set of location points in the uncertain area is calculated,and then the false location set is filtered to publish the location points that meet the geographical indistinguishability and high location availability,which improves the utilization of privacy budget.Secondly,in order to make up for the blank of k-nearest neighbor query of uncertain trajectory in road network environment,an algorithm is proposed.Firstly,Dijkstra algorithm is used to fill the position points of too sparse uncertain trajectories.Secondly,the road network features are integrated into the uncertain Voronoi diagram,and the uncertain trajectory set is preliminarily screened through the characteristics of Voronoi diagram to generate the uncertain trajectory candidate set.Finally,further calculation is carried out through probability distance,relative entropy and angle to generate the final k-nearest neighbor query result.