Privacy Preservation in the Publication of Trajectories
Published 1 April 2008
Manolis Terrovitis, Nikos Mamoulis
Citations294
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that one can use partial trajectory knowledge as a quasi-identifier for the remaining locations in the sequence and device a data suppression technique, which prevents this type of breach, while keeping the posted data as accurate as possible.
Abstract
We study the problem of protecting privacy in the publication of location sequences. Consider a database of trajectories, corresponding to movements of people, captured by their transactions when they use credit or RFID debit cards. We show that, if such trajectories are published exactly (by only hiding the identities of persons that followed them), there is a high risk of privacy breach by adversaries who hold partial information about them (e.g., shop owners). In particular, we show that one can use partial trajectory knowledge as a quasi-identifier for the remaining locations in the sequence. We device a data suppression technique, which prevents this type of breach, while keeping the posted data as accurate as possible.
Keywords
Computer Science
International Journal of Uncertainty Fuzziness and Knowledge-Based Systemsk-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
8,492 Citations2002Latanya Sweeney
The solution provided in this paper includes a formal protection model named k-anonymity and a set of accompanying policies for deployment and examines re-identification attacks that can be realized on releases that adhere to k- anonymity unless accompanying policies are respected.
L-diversity: privacy beyond k-anonymity
2,376 Citations2006Ashwin Machanavajjhala, Johannes Gehrke +2 more
This paper shows with two simple attacks that a \kappa-anonymized dataset has some subtle, but severe privacy problems, and proposes a novel and powerful privacy definition called \ell-diversity, which is practical and can be implemented efficiently.
IEEE Transactions on Knowledge and Data EngineeringProtecting respondents identities in microdata release
2,302 Citations2001Pierangela Samarati
This paper addresses the problem of releasing microdata while safeguarding the anonymity of respondents to which the data refer and introduces the concept of minimal generalization that captures the property of the release process not distorting the data more than needed to achieve k-anonymity.
Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking
2,283 Citations2003Marco Gruteser, Dirk Grunwald
A middleware architecture and algorithms that can be used by a centralized location broker service that adjusts the resolution of location information along spatial or temporal dimensions to meet specified anonymity constraints based on the entities who may be using location services within a given area.
Trajectory clustering
1,335 Citations2007Jae-Gil Lee, Jiawei Han +1 more
A new partition-and-group framework for clustering trajectories is proposed, which partitions a trajectory into a set of line segments, and then, groups similar line segments together into a cluster, and a trajectory clustering algorithm TRACLUS is developed, which discovers common sub-trajectories from real trajectory data.
Data Privacy through Optimal k-Anonymization
1,130 Citations2005Roberto J. Bayardo, R. Agrawal
This paper proposes and evaluates an optimization algorithm for the powerful de-identification procedure known as k-anonymization, and presents a new approach to exploring the space of possible anonymizations that tames the combinatorics of the problem, and develops data-management strategies to reduce reliance on expensive operations such as sorting.
Mondrian Multidimensional K-Anonymity
1,127 Citations2006Kristen LeFevre, David J. DeWitt +1 more
A new multidimensional model is proposed, which provides an additional degree of flexibility not seen in previous (single-dimensional) approaches, which leads to higher-quality anonymizations, as measured both by general-purpose metrics and more specific notions of query answerability.
Incognito
1,061 Citations2005Kristen LeFevre, David J. DeWitt +1 more
A set of algorithms for producing minimal full-domain generalizations are introduced, and it is shown that these algorithms perform up to an order of magnitude faster than previous algorithms on two real-life databases.
The new Casper: query processing for location services without compromising privacy
1,004 Citations2006Mohamed F. Mokbel, Chi-Yin Chow +1 more
Casper is presented; a new framework in which mobile and stationary users can entertain location-based services without revealing their location information while providing anonymity for both data and queries.
GeoInformaticaA Framework for Generating Network-Based Moving Objects
861 Citations2002Thomas Brinkhoff
In this paper, the most important properties of network-based moving objects are presented and discussed and a framework is proposed where the user can control the behavior of the generator by re-defining the functionality of selected object classes.
On the complexity of optimal K-anonymity
827 Citations2004Adam Meyerson, Ryan Williams
It is proved that two general versions of optimal k-anonymization of relations are NP-hard, including the suppression version which amounts to choosing a minimum number of entries to delete from the relation.
Generalizing data to provide anonymity when disclosing information (abstract)
777 Citations1998Pierangela Samarati, Latanya Sweeney
An algorithm is described that, given a table, efficiently computes a preferred minimal gcnoralization to provide anonymity and the notions of generalized table and of minimal generalization of a table are introduced with respect to a k-anonymity requirement.
Utility-based anonymization using local recoding
418 Citations2006Jian Xu, Wei Wang +4 more
This paper proposes a simple framework to specify utility of attributes and develops two simple yet efficient heuristic local recoding methods for utility-based anonymization, which outperform the state-of-the-art multidimensional global recode methods in both discernability and query answering accuracy.
Protecting Location Privacy Through Path Confusion
388 Citations2006Baik Hoh, Marco Gruteser
This work concentrates on a class of applications that continuously collect location samples from a large group of users, where just removing user identifiers from all samples is insufficient because an adversary could use trajectory information to track paths and follow users’ footsteps home.
Lecture notes in computer scienceProtecting Privacy Against Location-Based Personal Identification
337 Citations2005Cláudio Bettini, X. Sean Wang +1 more
It is argued that even if the user identity is not explicitly released to the service provider, the geo-localized history of user-requests can act as a quasi-identifier and may be used to access sensitive information about specific individuals.
Mining Frequent Spatio-Temporal Sequential Patterns
284 Citations2006Huiping Cao, Nikos Mamoulis +1 more
This paper proposes algorithms to find patterns by employing a newly proposed substring tree structure and improving a priori technique, and defines pattern elements as spatial regions around frequent line segments.
Achieving anonymity via clustering
277 Citations2006Gagan Aggarwal, Tomás Feder +5 more
This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k, and extends the algorithms to allow an ε fraction of points to remain unclustered, i.e., deleted from the anonymized publication.
Time series compressibility and privacy
106 Citations2007Spiros Papadimitriou, Li Fei-Fei +2 more
This paper formalize these notions, study the above trade-offs on real data and develop practical schemes which strike a good balance and can also be extended for on-the-fly data hiding in a streaming environment.
IEEE Transactions on Information TheoryOn Achieving Local View Capacity Via Maximal Independent Graph Scheduling
60 Citations2011Vaneet Aggarwal, A. Salman Avestimehr +1 more
This paper formalizes the increase of sum-rate with increased knowledge of the network state, and proposes to use the metric of normalized sum-capacity, which is the h -local view sum- capacity divided by global-view sum capacity.