一种保护用户隐私的路网兴趣点KNN查询方法

针对查询K近邻兴趣点方法多基于欧氏空间的不实用问题，提出了适用于路网环境下的查询方法。首先，利用四叉树索引划分路网结点。然后，用户基于划分结果，计算所在路段指向的路网顶点，以该顶点为出发点查询路网距离下的K近邻目标兴趣点。最后，用户构造包含这K个目标兴趣点的匿名框并注入虚假兴趣点查询请求，LBS服务器只返回匿名框内的兴趣点查询结果。该方法在控制通信开销的同时，能够保护用户的位置隐私和查询内容隐私。

A Privacy-preserving Method for K Nearest Neighbor Query in Road Networks

The current K nearest neighbor (KNN) query methods using cloaking region were almost proposed based on Euclidean space, which were not applicable to the actual road networks. A KNN query method was proposed based on the distribution of places of interest (PoI) in road networks. LBS server organized the nodes in road networks into a lightweight and hierarchical grid structure with quadtree index. Then, using the grid structure, a user computed the coming node which he was heading to based on his current location and velocity vector, the KNN PoIs in road networks were searched starting from the coming node. Finally, the user constructed a cloaking region covering the K PoIs and injected fake queries into the query request, LBS server only returned the results in the cloaking region. The experiments show that the communication cost of this method is lower, the users'' location privacy and query content privacy are protected well, and the performance of this method is good.