Practical Approximate k Nearest Neighbor Queries with Location and Query Privacy
Practical Approximate k Nearest Neighbor Queries with Location and Query Privacy
复制标题
DOI：
10.1109/tkde.2016.2520473
复制
发表时间：
2016-06
影响因子：
8.9
通讯作者：
X. Yi;Russell Paulet;E. Bertino;V. Varadharajan
中科院分区：
文献类型：
--
作者：
X. Yi;Russell Paulet;E. Bertino;V. Varadharajan
在移动的通信中，空间查询对用户位置隐私构成严重威胁，因为查询的位置可能泄露关于移动的用户的敏感信息。在本文中，我们研究了近似k最近邻（kNN）查询的移动的用户查询的位置为基础的服务（LBS）提供商的近似k最近的兴趣点（POI）的基础上，他的当前位置。我们提出了一个基本的解决方案和一个通用的解决方案，为移动的用户保持他的位置和查询隐私近似kNN查询。所提出的解决方案主要是建立在Paillier公钥密码系统，可以提供位置和查询隐私。为了保护查询隐私，我们的基本解决方案允许移动的用户检索一种类型的POI，例如，近似k个最近的停车场，而不向LBS提供商透露检索到什么类型的点。我们的通用解决方案可以应用于多个离散型属性的私人位置为基础的查询。与现有的解决方案相比，位置隐私的kNN查询，我们的解决方案是更有效的。实验表明，我们的解决方案是实用的kNN查询。
In mobile communication, spatial queries pose a serious threat to user location privacy because the location of a query may reveal sensitive information about the mobile user. In this paper, we study approximate k nearest neighbor (kNN) queries where the mobile user queries the location-based service (LBS) provider about approximate k nearest points of interest (POIs) on the basis of his current location. We propose a basic solution and a generic solution for the mobile user to preserve his location and query privacy in approximate kNN queries. The proposed solutions are mainly built on the Paillier public-key cryptosystem and can provide both location and query privacy. To preserve query privacy, our basic solution allows the mobile user to retrieve one type of POIs, for example, approximate k nearest car parks, without revealing to the LBS provider what type of points is retrieved. Our generic solution can be applied to multiple discrete type attributes of private location-based queries. Compared with existing solutions for kNN queries with location privacy, our solution is more efficient. Experiments have shown that our solution is practical for kNN queries.