# Releasing Differentially Private Trajectories with Optimized Data Utility
###### Abstract
For instance, the geographical utility could reveal the individual identity, so individuals could be distinguished from each other, which is known as de-anonymization attacks, e.g., four spatial-temporal points are enough to uniquely identify 95% of the anonymized individuals [11]. Most of existing work cannot thwart the de-anonymization attacks because they protect the single location without a comprehensive consideration of whole the trajectory. For example, MLCE [12] protects location privacy by independently perturbing each actual location into a nearby location. In addition, the semantic utility could reveal individuals' sensitive locations such as home and workplace, resulting in location inference attacks [3]. Figure 1 depicts an example where the periodic movement patterns and location categories, two types of semantic utility, are used to deduce home and workplace. Existing work cannot provide a formal and provable privacy guarantee to thwart the privacy attacks. For instance, [PERSON] et al. [13] protects privacy by blurring the actual location into a \(k\)-anonymous area. Since there is not provable correlation between the privacy parameter \(k\) and the privacy guarantee, the data curator cannot determine \(k\) for a specific scenario. In this work, given an actual trajectory dataset, we aim to address the following problem, i.e., designing a location privacy protection algorithm for releasing an offline and obfuscated version on the conditions that (a) simultaneous preservation of both geographical as well as semantic utility of the actual data, and (b) effective prevention from the location inference and de-anonymization attacks. To tackle this issue, we propose a utility-optimized and differentially private trajectory synthesis algorithm named UDPT, which is composed of three sequential phases as follows. (i) To provide an effective defense against the location inference attacks, locations in the actual trajectories are blurred into regions by private location clustering. (ii) To simultaneously preserve both the geographical utility and semantic utility, we privately select a sequence of utility-optimized candidate obfuscated location sets from the clusters. We model the selection as a multi-objective optimization problem and tackle it with a differentially private genetic algorithm. (iii) Based on the utility-optimized candidate obfuscated location sets, to defend against the de-anonymization attacks, we construct an obfuscated trajectory synthesizer based on the Conditional Random Fields (CRF) and privately select the (final) obfuscated trajectories by the sequence decoding of CRF. We conclude the contributions as follows:  
* We propose a location privacy protection algorithm, UDPT. It enables the data curator to release an offline trajectory dataset for data-mining purposes in a utility-optimized and differentially private manner. The data analysis applications, e.g., semantic annotation and trajectory prediction, which heavily rely on trajectory data geographical utility as well as the semantic utility can be benefited. * UDPT can preserve the data utility in terms of geography as well as semantics, simultaneously, by a multiple-objective optimization algorithm, so the released dataset can improve the performance of numerous data analysis tasks. * UDPT can provide a formal and provable privacy guarantee by differentially private and generative trajectory synthesis. To our best knowledge, it is the first work which ensures differential privacy and preserves both types of data utility. * Extensive evaluations on real-world datasets demonstrate that UDPT not only can outperform state-of-the-art works, in terms of multiple data utility metrics, but can also effectively prevent the de-anonymization attacks and location inference attacks. The structure of this work is as follows. We summarize related work in Section 2. Section 3 presents preliminaries, including problem statement and the differential privacy. In Section 4, we elaborate on three main phases of UDPT.