中文摘要：

为了在使用基于位置的服务时用户的位置信息不被不可信的位置服务提供商所泄漏,k-匿名位置隐私保护已被广泛研究。然而在集中匿名器被黑客控制时原k-匿名算法会泄漏所有用户的位置隐私,在进行k个最近邻目标查询时对网络的负载较重,而Space Twist算法又不能保证k-匿名。提出了一种基于经纬网格的递增KNN位置隐私保护查询算法,将经典的k-匿名算法与Space Twist算法相杂交,并引入经纬网格代替原来精确的位置上报给集中匿名器,从而解决了上述问题。实验证明基于经纬网格的递增KNN查询算法比较节省从集中匿名器到位置服务提供商的服务器之间的网络流量。

英文摘要：

In order to enjoy location-based services without leaking the users’ location information to untrusted location service provider,k-anonymous location privacy protection had been well studied. However,for the original k-anonymity algorithm,all users’ location privacy would be leaked when the centralized anonymizer was controlled by hackers,and the network load was very heavy when making k-nearest neighbor inquiries; for the Space Twist algorithm,it could not guarantee k-anonymity.This paper proposed an incremental KNN query algorithm based on the grid of latitude-longitude for location privacy protection,it came from the classical k-anonymity algorithm hybridized with the Space Twist algorithm,using the grids of latitude-longitude instead of the precise coordinates reported to centralized anonymizer,and thus it could solve the above problems. Experiments show that the algorithm can save the network traffic between the anonymizer and the location service provider’s servers.