Efficient algorithms for K-anonymous location privacy in participatory sensing

Khuong Vu, Rong Zheng, Jie Gao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

157 Scopus citations


Location privacy is an important concern in participatory sensing applications, where users can both contribute valuable information (data reporting) as well as retrieve (location-dependent) information (query) regarding their surroundings. K-anonymity is an important measure for privacy to prevent the disclosure of personal data. In this paper, we propose a mechanism based on locality-sensitive hashing (LSH) to partition user locations into groups each containing at least K users (called spatial cloaks). The mechanism is shown to preserve both locality and K-anonymity. We then devise an efficient algorithm to answer kNN queries for any point in the spatial cloaks of arbitrary polygonal shape. Extensive simulation study shows that both algorithms have superior performance with moderate computation complexity.

Original languageEnglish (US)
Title of host publication2012 Proceedings IEEE INFOCOM, INFOCOM 2012
Number of pages9
StatePublished - 2012
Externally publishedYes
EventIEEE Conference on Computer Communications, INFOCOM 2012 - Orlando, FL, United States
Duration: Mar 25 2012Mar 30 2012

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


OtherIEEE Conference on Computer Communications, INFOCOM 2012
Country/TerritoryUnited States
CityOrlando, FL

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Efficient algorithms for K-anonymous location privacy in participatory sensing'. Together they form a unique fingerprint.

Cite this