Publications and Research

Document Type


Publication Date



The tremendous growth of the Internet has significantly reduced the cost of obtaining and sharing information about individuals, raising many concerns about user privacy. Spatial queries pose an additional threat to privacy because the location of a query may be sufficient to reveal sensitive information about the querier. In this paper we focus on k nearest neighbor (kNN) queries and define the notion of strong location privacy, which renders a query indistinguishable from any location in the data space. We argue that previous work fails to support this property for arbitrary kNN search. Towards this end, we introduce methods that offer strong location privacy, by integrating private information retrieval (PIR) functionality. Specifically, we employ secure hardware-aided PIR, which has been proven very efficient and is currently considered as a practical mechanism for PIR. Initially, we devise a benchmark solution building upon an existing PIR-based technique. Subsequently, we identify its drawbacks and present a novel scheme called AHG to tackle them. Finally, we demonstrate the performance superiority of AHG over our competitor, and its viability in applications demanding the highest level of privacy.


This article was published originally in the Proceedings of the VLDB Endowment, Vol. 3, No. 1 and was presented at the 36th International Conference on Very Large Data Bases, September 13-17, 2010, Singapore.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.