With the increasing prevalence of location-aware devices, trajectory data has been generated and collected in various application domains. Trajectory data carries rich in- formation that is useful for many data analysis tasks. Yet, improper publishing and use of trajectory data could jeopardize individual privacy. However, it has been shown that existing privacy-preserving trajectory data publishing methods derived from partition-based privacy models, for example k-anonymity, are unable to provide sufficient privacy protection. In this paper, motivated by the data publishing scenario at the Societe de transport de Montreal (STM), the public transit agency in Montreal area, we study the problem of publishing trajectory data under the rigorous differential privacy model. We propose an efficient data-dependent yet differentially private sanitization algorithm, which is applicable to different types of trajectory data. The efficiency of our approach comes from adaptively narrowing down the output domain by building a noisy prefix tree based on the underlying data. Moreover, as a post-processing step, we make use of the inherent constraints of a prefix tree t o conduct constrained inferences, which lead to better utility. This is the first paper to introduce a practical solution for publi shing large volume of trajectory data under differential privacy. We examine the utility of sanitized data in terms of count queries and frequent sequential pattern mining. Extensive experiments on real-life trajectory data from the STM demonstrate that our approach maintains high utility and is scalable to large trajectory datasets.
In the last few years, differential privacy has been employed in various applications. Currently most of the research on differential privacy concentrates on the with the goal of either reducing the magnitude of added noise @cite_5 , @cite_20 , @cite_13 , @cite_17 or releasing certain data mining results @cite_14 @cite_38 @cite_27 @cite_18 @cite_7 . Dwork @cite_2 provides an overview of recent works on differential privacy.
@cite_38 @cite_18 @cite_14 @cite_7 @cite_27 @cite_2 @cite_5 @cite_13 @cite_20 @cite_17
2613416506 58212258 2809701319 2005107218
Differential privacy has emerged as an important standard for privacy preserving computation over databases containing sensitive information about individuals. Research on differential privacy spanning a number of research areas, including theory, security, database, networks, machine learning, and statistics, over the last decade has resulted in a variety of privacy preserving algorithms for a number of analysis tasks. Despite maturing research efforts, the adoption of differential privacy by practitioners in industry, academia, or government agencies has so far been rare. Hence, in this tutorial, we will first describe the foundations of differentially private algorithm design that cover the state of the art in private computation on tabular data. In the second half of the tutorial we will highlight real world applications on complex data types, and identify research challenges in applying differential privacy to real world applications. Differential privacy has taken the privacy community by storm. Computer scientists developed this technique to allow researchers to submit queries to databases without being able to glean sensitive information about the individuals described in the data. Legal scholars champion differential privacy as a practical solution to the competing interests in research and confidentiality, and policymakers are poised to adopt it as the gold standard for data privacy. It would be a disastrous mistake. This Article provides an illustrated guide to the virtues and pitfalls of differential privacy. While the technique is suitable for a narrow set of research uses, the great majority of analyses would produce results that are beyond absurd: average income in the negative millions, or correlations well above 1, for example. The legal community has been misled into thinking that differential privacy can offer the benefits of data research without sacrificing privacy. In fact, differential privacy will usually produce either very wrong research results or very useless privacy protections. Policymakers and data stewards will have to rely on a mix of approaches: perhaps differential privacy where it is well-suited to the task, and other disclosure prevention techniques in the great majority of situations where it isn’t. Differential privacy has emerged as the main definition for private data analysis and machine learning. The global model of differential privacy, which assumes that users trust the data collector, provides strong privacy guarantees and introduces small errors in the output. In contrast, applications of differential privacy in commercial systems by Apple, Google, and Microsoft, use the local model. Here, users do not trust the data collector, and hence randomize their data before sending it to the data collector. Unfortunately, local model is too strong for several important applications and hence is limited in its applicability. In this work, we propose a framework based on trusted processors and a new definition of differential privacy called Oblivious Differential Privacy, which combines the best of both local and global models. The algorithms we design in this framework show interesting interplay of ideas from the streaming algorithms, oblivious algorithms, and differential privacy. Privacy-preserving data publishing addresses the problem of disclosing sensitive data when mining for useful information. Among the existing privacy models, ∈-differential privacy provides one of the strongest privacy guarantees and has no assumptions about an adversary's background knowledge. Most of the existing solutions that ensure ∈-differential privacy are based on an interactive model, where the data miner is only allowed to pose aggregate queries to the database. In this paper, we propose the first anonymization algorithm for the non-interactive setting based on the generalization technique. The proposed solution first probabilistically generalizes the raw data and then adds noise to guarantee ∈-differential privacy. As a sample application, we show that the anonymized data can be used effectively to build a decision tree induction classifier. Experimental results demonstrate that the proposed non-interactive anonymization algorithm is scalable and performs better than the existing solutions for classification analysis.