A reciprocal framework for spatial K-anonymity

Gabriel Ghinita, Keliang Zhao, Dimitris Papadias, Panos Kalnis

Research output: Contribution to journalArticlepeer-review

53 Scopus citations

Abstract

Spatial K-anonymity (SKA) exploits the concept of K-anonymity in order to protect the identity of users from location-based attacks. The main idea of SKA is to replace the exact location of a user U with an anonymizing spatial region (ASR) that contains at least K-1 other users, so that an attacker can pinpoint U with probability at most 1/K. Simply generating an ASR that includes K users does not guarantee SKA. Previous work defined the reciprocity property as a sufficient condition for SKA. However, the only existing reciprocal method, Hilbert Cloak, relies on a specialized data structure. In contrast, we propose a general framework for implementing reciprocal algorithms using any existing spatial index on the user locations. We discuss ASR construction methods with different tradeoffs on effectiveness (i.e., ASR size) and efficiency (i.e., construction cost). Then, we present case studies of applying our framework on top of two popular spatial indices (namely, R*-trees and Quad-trees). Finally, we consider the case where the attacker knows the query patterns of each user. The experimental results verify that our methods outperform Hilbert Cloak. Moreover, since we employ general-purpose spatial indices, the proposed system is not limited to anonymization, but supports conventional spatial queries as well. © 2009 Elsevier B.V. All rights reserved.
Original languageEnglish (US)
Pages (from-to)299-314
Number of pages16
JournalInformation Systems
Volume35
Issue number3
DOIs
StatePublished - May 2010

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'A reciprocal framework for spatial K-anonymity'. Together they form a unique fingerprint.

Cite this