| K-nearest neighbor query is an important branch in the field of query.With the deepening of research,the traditional k-nearest neighbor query in Euclidean space is not applicable to all problems in real life,so the k-nearest neighbor query in road network has become the focus of close attention.In addition,with the advent of the digital era and the change of people’s thinking,more and more people pay more attention to the time cost of road network,privacy of personal data and personal preference,etc.Therefore,based on the above,this paper studies the recent query of spatial data k in the road network environment.Firstly,in order to make up for the existing k-nearest neighbor query algorithm for time-dependent road networks,which only considers a single state index to evaluate the road operation ability at the road network environment level,and does not consider the privacy protection problem of query results,this paper proposes a knearest neighbor query method based on differential privacy in time-dependent road networks for the first time.Different from the traditional method,the proposed method mainly queries the nearest k results in time dimension from the point of interest to the query point.The method consists of three parts,In the first part,based on the road network rules and the restriction of the query direction,this paper proposes a data point filtering algorithm to achieve the purpose of logarithmic data point pruning.In the second part,we propose a data point refining algorithm,which fully considers the influence of multi-source uncertain information of road network on time,and can effectively carry out secondary pruning on logarithmic data points,improving the query efficiency.In the third part,aiming at the problem that the knearest neighbor query in the time-dependent network cannot deal with the data privacy protection,we uses the differential privacy technology to add noise to the query results,and proposes a differential privacy budget allocation algorithm to balance the privacy and availability of data.Firstly,the algorithm performs classification to obtain the best privacy allocation model,and then obtains two parts of privacy budget parameters.Finally,according to the global sensitivity and the allocated privacy budget parameters,the final Laplacian noise to be added to each classification is calculated.Secondly,in order to solve the problem of missing preference values caused by not considering the uncertainty of multi-user preferences in the k-nearest neighbor query of road network,this paper proposes a multi-user uncertain preference knearest neighbor query algorithm based on differential privacy in road network.The algorithm is divided into four parts.In the first part,this paper proposes a multi-user uncertain preference completion algorithm based on association rules.Firstly,the algorithm uses the frequent pattern tree proposed in this paper to mine frequent item sets,and then uses the frequent itemsets to mine the strong correlation rules.Finally,we completes the incomplete preferences of multiple users based on the strong correlation rules.In the second part,based on the different preferences of multiple users,we put forward the weight coefficient of attribute preference and cluster users accordingly,and then group users within the class according to the differences of users’ preferences for user attributes.The third part compares the domination of the query object,filtering the data with low domination and then conducting k-nearest neighbor query.The fourth part proposes a privacy budget allocation method based on differential privacy technology,which uses Laplace mechanism to add noise to the data to balance the privacy and availability of data. |
