Location diversity: Enhanced privacy protection in location based services

Mingqiang Xue*, Panagiotis Kalnis, Hung Keng Pung

*Corresponding author for this work

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

105 Scopus citations


Location-based Services are emerging as popular applications in pervasive computing. Spatial k-anonymity is used in Locationbased Services to protect privacy, by hiding the association of a specific query with a specific user. Unfortunately, this approach fails in many practical cases such as: (i) personalized services, where the user identity is required, or (ii) applications involving groups of users (e.g., employees of the same company); in this case, associating a query to any member of the group, violates privacy. In this paper, we introduce the concept of Location Diversity, which solves the above-mentioned problems. Location Diversity improves Spatial k-anonymity by ensuring that each query can be associated with at least ℓ different semantic locations (e.g., school, shop, hospital, etc). We present an attack model that maps each observed query to a linear equation involving semantic locations, and we show that a necessary condition to preserve privacy is the existence of infinite solutions in the resulting system of linear equations. Based on this observation, we develop algorithms that generate groups of semantic locations, which preserve privacy and minimize the expected query processing and communication cost. The experimental evaluation demonstrates that our approach reduces significantly the privacy threats, while incurring minimal overhead.

Original languageEnglish (US)
Title of host publicationLocation and Context Awareness - 4th International Symposium, LoCA 2009, Proceedings
Number of pages18
StatePublished - Aug 10 2009
Event4th International Symposium on Location and Context Awareness, LoCA 2009 - Tokyo, Japan
Duration: May 7 2009May 8 2009

Publication series

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


Other4th International Symposium on Location and Context Awareness, LoCA 2009

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Location diversity: Enhanced privacy protection in location based services'. Together they form a unique fingerprint.

Cite this