Practical approximate k nearest neighbor queries with location and query privacy

Xun Yi*, Russell Paulet, Elisa Bertino, Vijay Varadharajan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

93 Citations (Scopus)


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.

Original languageEnglish
Article number7389401
Pages (from-to)1546-1559
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number6
Publication statusPublished - 1 Jun 2016


  • Location based query
  • Paillier cryptosystem
  • RSA
  • location and query privacy
  • private information retrieval


Dive into the research topics of 'Practical approximate k nearest neighbor queries with location and query privacy'. Together they form a unique fingerprint.

Cite this