# Releasing Differentially Private Trajectories with Optimized Data Utility
## 2 Related Work
### Trajectory Synthesis  
Trajectory synthesis is essentially an obfuscated trajectory generator, which fits the mobility patterns of actual trajectories and generates obfuscated trajectories in a private-protecting way. The location privacy protection algorithms based on trajectory synthesis are often used in scenarios such as offline data releasing. To protect privacy, the synthesis process will be perturbed under the guidance of some privacy notions such as \(k\)-anonymity or differential privacy. For example, [PERSON] et al. [19] first propose an end-to-end trajectory data releasing solution named DPT. It discretizes the area in which individuals move by a uniform grid and aggregates actual trajectories to grid trajectories. Based on that, a trajectory generator using a prefix tree is constructed and then a number of trajectories are generated. The advantage of DPT is good preservation of geographical utility, especially the moving speed and directions, due to the exploitation of multiple-level granularity grid (a.k.a. hierarchical reference systems). The trajectory generator is perturbed by injecting random noise into the prefix tree to ensure differential privacy. In subsequent work [6], [PERSON] et al. argue that solely relying on differential privacy cannot provide enough guarantee to thwart privacy attacks such as de-anonymization, since the obfuscated trajectories generated by previous works are still distinguishable. Therefore, they propose an attack-resilient trajectory releasing method called AdaTrace. First, in contrast with the DPT's uniform grid, AdaTrace discretizes the moving area by a location-density-aware grid to capture the complex spatial density and locality distributions, two types of the geographical utility. Second, the authors exploit a Markov model to capture the location transition patterns in actual trajectories. Third, a number of obfuscated trajectories are point-wisely sampled from the grid trajectories, where the sampling is perturbed by random noise calibrated by differential privacy. Finally, AdaTrace checks whether the indistinguishability of the obfuscated trajectories satisfies the given requirement. Except for the differential privacy, \(k\)-anonymity is also a widely used privacy notion to thwart privacy attacks. For instance, [PERSON] et al. [21] find that individual location privacy could be compromised when the sensitive semantics of locations, e.g, hospitals, are derived. To address this problem, the authors propose a \(k\)-anonymous privacy protection algorithm for releasing semantic trajectory data, which blurs an actual location, together with other \(k-1\) locations sharing similar semantics, into an anonymous area. The advantage is a well preservation of semantic utility. However, it independently anonymizes each actual location while taking into no consideration the data utility of whole the actual trajectory. [PERSON] et al. [22] propose to apply machine learning algorithms for clustering the actual trajectories and randomly sample the obfuscated trajectories to ensure that every trajectory in the obfuscated trajectory dataset is indistinguishable from at least \(k-1\) other trajectories. [PERSON] et al. [20] propose another privacy notion, statistical dissimilarity, measuring the indistinguishability between trajectories, which can simultaneously preserve data utility in terms of both geography and semantics. However, compared with differential privacy, the proposed privacy notion cannot provide a formal and provable guarantee of location privacy, so it will be hard for the data curators to determine a suitable privacy level for a certain data releasing task. In contrast, the privacy level, \(\epsilon\), of the differential privacy usually takes values in a widely-accepted interval, i.e., \(\epsilon\in[0.1,10]\), where less \(\epsilon\) indicates a higher privacy level.