# Releasing Differentially Private Trajectories with Optimized Data Utility
###### Abstract  
The ubiquity of GPS-enabled devices has resulted in an abundance of data about individual trajectories. Releasing trajectories enables a range of data analysis tasks, such as urban planning, but it also poses a risk in compromising individual location privacy. To tackle this issue, a number of location privacy protection algorithms are proposed. However, existing works are primarily concerned with maintaining the trajectory data geographic utility and neglect the semantic utility. Thus, many data analysis tasks relying on utility, e.g., semantic annotation, suffer from poor performance. Furthermore, the released trajectories are vulnerable to location inference attacks and de-anonymization attacks due to insufficient privacy guarantee. In this paper, to design a location privacy protection algorithm for releasing an offline trajectory dataset to potentially untrusted analyzers, we propose a utility-optimized and differentially private trajectory synthesizer (UDPT) with two novel features. First, UDPT simultaneously preserves both geographical utility and semantic utility by solving a data utility optimization problem with a genetic algorithm. Second, UDPT provides a formal and provable guarantee against privacy attacks by synthesizing obfuscated trajectories in a differentially private manner. Extensive experimental evaluations on real-world datasets demonstrate UDPT's outperformance against state-of-the-art works in terms of data utility and privacy. location-based services; mobile computing; data release; location privacy protection; data utility +
Footnote †: journal: Medical  
of obfuscated trajectories in a generative fashion. To protect location privacy, the process of trajectory synthesis is perturbed by random noise calibrated by some privacy notions, e.g., differential privacy [7], a de facto notion for protecting privacy due to its strong privacy guarantee. However, existing works based on trajectory synthesis can neither well preserve the data utility nor effectively thwart the privacy attacks. The reasons are as follows. First, existing location privacy protection algorithms merely focus on the geographical utility in trajectories while neglecting the simultaneous preservation of semantic utility, resulting in poor performance of numerous data analysis tasks. Specifically, the data utility in individual trajectories consists of two aspects, namely geography and semantics. The geographical utility represents the superficially spatial-temporal regularity of population movement, e.g., trajectory diameter distribution [6]. Early trajectory data analysis tasks solely rely on the geographical utility. In this case, existing location privacy protection algorithms can already satisfy the analyzer's requirement. However, recently, a large number of popular analysis tasks have emerged, e.g., semantic annotation [8], trajectory prediction [9], providing great convenience to people's daily life. These emerging data analysis tasks not only require the geographical utility but also heavily rely on deep-level regularity implied in the individual trajectories, especially the semantics that motivates individual movement, e.g., periodic movement patterns [9] and location categories [10]. Nonetheless, simultaneously preserving both kinds of data utility on the condition of ensuring location privacy is an intractable problem since there exist conflicts between them [10]. For instance, AdaTrace [6] protects location privacy by differentially private trajectory synthesis, which solely focuses on the geographical utility while neglects the location semantics that motivates human movement. As a result, the data analysis tasks such as semantic annotation suffer from low precision. Second, existing location privacy protection algorithms cannot provide a strong privacy guarantee due to the negligence of privacy attacks using data utility as side channels.