Practical Approximate k Nearest Neighbor Queries with Location and Query Privacy

Practical Approximate k Nearest Neighbor
Queries with Location and Query Privacy

Abstract— Practical Approximate k Nearest Neighbor Queries with Location and Query Privacy. 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 < Final Year Projects 2016 > 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 querieswith location privacy, our solution is more efficient. Experiments have shown that our solution is practical for kNN queries.