Bibliography on Spatial Anonymity in Location Based Services

Query Privacy and Spatial Anonymity in Location Based Services

Nowadays, mobile users with positioning devices can access Location Based Services (LBS) and query about points of interest in their proximity. For such applications to succeed, privacy and confidentiality are essential. Encryption alone is not adequate; although it safeguards the system against eavesdroppers, the queries themselves may disclose the location and identity of the user. Recently, K-anonymity has been considered as a strong candidate to achieve query privacy in LBS.

K-anonymity has been used in statistical databases as well as for publishing census, medical and voting registration data. A dataset is said to be K-anonymized, if each record is indistinguishable from at least K−1 other records with respect to certain identifying attributes. In the LBS domain, K-anonymity can be achieved by spatio-temporal cloaking that conceals the location of a user. Instead of reporting the exact coordinates to the LBS, an Anonymizing Spatial Region (K-ASR) is constructed, which encloses the locations of the query source and K−1 additional users.

Panos Kalnis

Assistant Professor

Department of Computer Science

National University of Singapore

kalnis at comp.nus.edu.sg

Gabriel Ghinita

Research Fellow

Department of Computer Science

National University of Singapore

ghinitag at comp.nus.edu.sg

For suggestions or contributions to this page, please contact us.

Preventing Location-Based Identity Inference in Anonymous Spatial Queries

Panos Kalnis, Gabriel Ghinita, Kyriakos Mouratidis and Dimitris Papadias

IEEE Transactions on Knowledge and Data Engineering (IEEE TKDE), 19(12), 1719-1733, 2007

Overview

We propose a framework which deals with the entire procedure of anonymization and query processing for Location Based Services. Our system supports Range and k-Nearest Neighbor (kNN) queries, and retrieves the exact answers without revealing the location or identity of the user. We assume that all the users carry a positioning device (e.g., GPS) reporting their exact coordinates. The system includes a trusted anonymizer and a number of untrusted location servers (LS) providing various Location Based Services (LBS)

System Architecture

HilbASR

We introduce HilbASR, an efficient method for constructing query K-ASR based on fractals and conceptual partitioning. Our goal is to assemble fast an appropriate K-ASR that preserves anonymity while minimizing the expected cost at the LBS and the required bandwidth between the LBS and the anonymizer.

We construct Hilbert K-ASRs by grouping users together into K-sized buckets based on the Hilbert ordering of user locations. The HilbASR algorithm guarantees that the probability of identifying a user in a bucket is always bounded by 1/K, since it uses a fixed bucket partitioning scheme.

HilbASR Algorithm

The Hilbert space filling curve transforms the 2D coordinates of each user into an 1D value H(u). With high probability, if two points are in close proximity in the 2D space, they will also be close in the 1D transformation, therefore resulting K-ASRs have reduced spatial extent and incur low processing cost. We sort the Hilbert values of all users and split them in buckets. Each Hilbert bucket has the same number of users, K, except for the last one which is enlarged in order to contain at least K users.

Query Processing

The LBS computes the answer based on the K-ASR, instead of the exact user location; thus, the response of the LBS is a superset of the answer. The anonymizer filters the result from the LBS and returns the exact answer to the user. We consider the case of both rectangular ASR and circular ASR (circular ASRs are likely to have lower diameter which favors NN queries)

The Location Server (LS) receives the query from the anonymizer, processes it and sends the results back to the anonymizer. In our implementation, the data in the LS are indexed by an R*-Tree; our methods, however, are independent of the index structure. As we mentioned, we are interested in two types of queries:

The 1-NNs of rectangle abcd are p1 and p2

Range queries: The LS receives the query range which is either an axis-parallel rectangle R or a circle C. Processing is straight-forward; the R-tree is traversed from the root to the leaves and any object inside R (or C) is returned.
kNN queries: This case is more complex, since the LS must find the kNNs of the entire range.

PRIVÉ: Anonymous Location-Based Queries in Distributed Mobile Systems

Gabriel Ghinita, Panos Kalnis and Spiros Skiadopoulos

In Proceedings of World Wide Web Conference (WWW), 371-380, 2007

Overview

We propose PRIVÉ, a distributed architecture for anonymous location-based queries. We introduce a distributed protocol used by mobile entities to self-organize into a fault-tolerant overlay network. The structure of the network resembles a distributed B+-tree (each mobile user corresponds to a data point), with additional annotation to support efficiently Hilbert-based K-ASR construction. In PRIVÉ, any participant can play the role of the anonymizer. Therefore, the bottleneck of a centralized server is avoided. Moreover, since the status of the system is distributed, PRIVÉ is resilient to attacks. Our experimental evaluation confirms that PRIVÉ achieves efficient anonymization and load balancing with low maintenance overhead, while being fault-tolerant. Therefore, it is scalable to a large number of mobile users.

Architecture of PRIVÉ

Distributed Indexing Structure

PRIVÉ mimics the functionality of a B+-tree in a distributed setting. Each mobile user u has an associated index entry consisting of an ID (e.g., IP address), and the Hilbert value H(u) of his location as index key. A node (leaf or internal) in the B+-tree, corresponds to a cluster of users, with size bounded between ά and 3ά, where ά is a fixed system parameter. The maximum cluster size is 3ά, instead of the usual 2ά for B+-trees, to prevent cascading splits and merges (i.e., a split followed by a user departure), which are costly in the distributed environment.

PRIVÉ supports insertion, deletion and ASR construction with logarithmic complexity in the number of indexed users. User mobility is efficiently supported by using a relocation algorithm, which handles relocation locally, without propagation to higher levels of the tree.

Distributed Index Structure, ά=2

PRIVÉ uses a soft-state based approach to deal with user disconnection. The cluster membership state is replicated to all cluster members for enhanced fault-tolerance. To address the potential lack of balance inherent to hierarchical structures, PRIVÉ uses a load-balancing mechanism that rotates cluster heads in a round-robin fashion. Since query workload distribution may not be uniform over time, rotation is triggered based on the accumulated load of a user.

Bibliography on Spatial Anonymity and Privacy in Location Based Services

Gabriel Ghinita, Panos Kalnis, Ali Khoshgozaran, Cyrus Shahabi and Kian-Lee Tan, "Private Queries in Location Based Services: Anonymizers are not Necessary", In Proceedings of ACM SIGMOD Conference 2008 (to appear)
Panos Kalnis , Gabriel Ghinita, Kyriakos Mouratidis, Dimitris Papadias. Preventing Location-Based Identity Inference in Anonymous Spatial Queries, IEEE Transactions on Knowledge and Data Engineering (IEEE TKDE), 19(12), 1719-1733, 2007 (pdf)
Ali Khoshgozaran, Cyrus Shahabi. Blind Evaluation of Nearest Neighbor Queries Using Space Transformation to Preserve Location Privacy , In Proceedings of the Int. Symposium in Spatial and Temporal Databases (SSTD), Boston, MA, 239-257, 2007
Gabriel Ghinita, Panos Kalnis, Spiros Skiadopoulos. MOBIHIDE: A Mobile Peer-to-Peer System for Anonymous Location-Based Queries, In Proceedings of the Int. Symposium in Spatial and Temporal Databases (SSTD), Boston, MA, 221-238, 2007 (pdf)
Gabriel Ghinita, Panos Kalnis, Spiros Skiadopoulos. PRIVE: Anonymous Location-based Queries in Distributed Mobile Systems, In Proceedings of World Wide Web Conf. (WWW), 371-380, 2007 (pdf)
Mohamed F. Mokbel, Chi-Yin Chow and Walid G. Aref. The New Casper: Query Processing for Location Services without Compromising Privacy, In Proceedings of VLDB 2006
Chi-Yin Chow, Mohamed F. Mokbel and Xuan Liu. A Peer-to-Peer Spatial Cloaking Algorithm for Anonymous Location-based Services. In Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, ACM GIS 2006
R. Cheng, Y. Zhang, E. Bertino and S. Prabhakar. Preserving User Location Privacy in Mobile Data Management Infrastructures. In Proceedings of Privacy Enhancing Technology Workshop (PET) 2006 (pdf)
M. Duckham and L. Kulik. Location privacy and location-aware computing. Book chapter in Dynamic & Mobile GIS: Investigating Change in Space and Time, CRC Press, Boca Rator, FL, pp 35-51
L. Kazatzopoulos C. Delakouridis G. F. Marias, and P. Georgiadis, iHIDE: Hiding Sources of Information in WSNs. In Proceedings of 2nd International Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing (IEEE SecPerU2006)
Bugra Gedik and Ling Liu. Location-Privacy in Mobile Systems: A Personalized Anonymization Model, In Proceedings of ICDCS 2005 (pdf)
P. Kamat, Y. Zhang, W. Trappe and C. Ozturk. Enhancing Source-Location Privacy in Sensor Network Routing. In Proceedings of ICDCS 2005 (pdf)
B. Hoh and M. Gruteser. Protecting location privacy through path confusion, In First International Conference on Security and Privacy for Emerging Areas in Communications Networks, SecureComm 2005 (pdf)
Claudio Bettini, X. SeanWang and Sushil Jajodia. Protecting Privacy Against Location-Based Personal Identification, In Proceedings of 2nd VLDB Workshop on Secure Data Management (SDM) 2005 (pdf)
M. Youssef, V. Atluri and N. R. Adam . Preserving Mobile Customer Privacy: An Access Control System for Moving Objects and Customer Profiles, In Proceedings of the 6th International Conference on Mobile Data Management (MDM) 2005. (pdf)
Marco Gruteser and Xuan Liu. Protecting Privacy in Continuous Location Tracking Applications, IEEE Security and Privacy Magazine, 2(2), pp 28-34, 2004
A. R. Beresford and F. Stajano. Mix zones: User privacy in location-aware services, In Second IEEE Annual Conference on Pervasive Computing and Communications Workshops, March 2004 (pdf)
Marco Gruteser and Dirk Grunwald, Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking, In Proceedings of MobySys 2003 (pdf)
A. R. Beresford and F. Stajano. Location privacy in pervasive computing, IEEE Pervasive Computing, 2(1):46–55, 2003 (pdf)
J. Al-Muhtadi, R. Campbell, A. Kapadia, M. D. Mickunas and S. Yi. Routing Through the Mist: Privacy Preserving Communication in Ubiquitous Computing Environments. In Proceedings of ICDCS 2002 (pdf)

Related Publications - Bibliography on Privacy in Relational Databases

Gabriel Ghinita, Yufei Tao and Panos Kalnis "On the Anonymization of Sparse High-Dimensional Data", In Proceedings of International Conference on Data Engineering (ICDE) 2008 (pdf)
Gabriel Ghinita, Panos Karras, Panos Kalnis, Nikos Mamoulis. Fast Data Anonymization with Low Information Loss, In Proceedings of VLDB 2007 (pdf)
Xiaokui Xiao Yufei Tao. Anatomy: Simple and Effective Privacy Preservation, In Proceedings of VLDB 2006 (pdf)
Ashwin Machanavajjhala, Johannes Gehrke and Daniel Kifer. ℓ-Diversity: Privacy Beyond k-Anonymity, In Proccedings of ICDE 2006 (pdf)
Xiaokui Xiao and Yufei Tao. Personalized Privacy Preservation, In Proceedings of SIGMOD 2006 (pdf)
Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas and An Zhu. Achieving Anonymity via Clustering, In Proceedings of PODS 2006 (pdf)
Charu C. Aggarwal. On k-Anonymity and the Curse of Dimensionality, In Proceedings of VLDB 2005 (pdf)
Kristen LeFevre, David J. DeWitt and Raghu Ramakrishnan. Incognito: Efficient Full-Domain K-Anonymity, In Proceedings of SIGMOD 2005 (pdf)
Laks V.S. Lakshmanan, Raymond T. Ng and Ganesh Ramesh. To Do or Not To Do: The Dilemma of Disclosing Anonymized Data, In Proceedings of SIGMOD 2005 (pdf)
L. Sweeney. k-Anonymity: A Model for Protecting Privacy, International Journal of Uncertainty, Fuzziness, and Knowledge-based Systems 2002, 10(5), pp 557-570 (pdf)

Links

k-Anonymity page at CMU Data Privacy Lab