Privacy-preserving publication of user locations in the proximity of sensitive sites

Bharath Krishnamachari*, Gabriel Ghinita, Panagiotis Kalnis

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations


Location-based services, such as on-line maps, obtain the exact location of numerous mobile users. This information can be published for research or commercial purposes. However, privacy may be compromised if a user is in the proximity of a sensitive site (e.g., hospital). To preserve privacy, existing methods employ the K-anonymity paradigm to hide each affected user in a group that contains at least K∈-∈1 other users. Nevertheless, current solutions have the following drawbacks: (i) they may fail to achieve anonymity, (ii) they may cause excessive distortion of location data and (iii) they incur high computational cost. In this paper, we define formally the attack model and discuss the conditions that guarantee privacy. Then, we propose two algorithms which employ 2-D to 1-D transformations to anonymize the locations of users in the proximity of sensitive sites. The first algorithm, called MK, creates anonymous groups based on the set of user locations only, and exhibits very low computational cost. The second algorithm, called BK, performs bichromatic clustering of both user locations and sensitive sites; BK is slower but more accurate than MK. We show experimentally that our algorithms outperform the existing methods in terms of computational cost and data distortion.

Original languageEnglish (US)
Title of host publicationScientific and Statistical Database Management - 20th International Conference, SSDBM 2008, Proceedings
Number of pages19
StatePublished - Aug 14 2008
Event20th International Conference on Scientific and Statistical Database Management, SSDBM 2008 - Hong Kong, China
Duration: Jul 9 2008Jul 11 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5069 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other20th International Conference on Scientific and Statistical Database Management, SSDBM 2008
CityHong Kong

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this