# Releasing Differentially Private Trajectories with Optimized Data Utility
## 4 Trajectory Synthesis
### Overview  
**Overall ideas. ** Recall the design objectives in Section 3.1. (i) One of the design objectives is to achieve that the chance that any actual location or individual identity is derived by observing the released dataset should be restricted to some magnitude specified by the data curator, we employ the differential privacy as the privacy notion of UDPT. An \(\epsilon\)-differentially private algorithm can ensure that the output is insensitive to the change of any location record in the actual trajectory, so the location inferenceattacks on actual locations can be thwarted. The privacy guarantee can be tuned by the data curator with the privacy budget \(\epsilon\). However, the differential privacy cannot prevent the de-anonymization attacks on individual identity [6]. Our remedy is to synthesize a number of indistinguishable and obfuscated trajectories for each actual trajectory in a generative manner, so the attacker cannot rebuild the linkage between individual identities and obfuscated trajectories. (ii) The other objective is to achieve simultaneous preservation of geographical utility as well as semantic utility. In other words, the obfuscated locations should be close to the actual locations and have similar semantics to the actual location as much as possible. To this end, we model the preservation of both types of utility as a multiple-objective optimization problem. In general, UDPT is a location privacy protection algorithm, which takes as input an actual trajectory dataset of individuals, together with a (total) privacy budget \(\epsilon\), and then produces an obfuscated trajectory dataset. It enables the trajectory data curator to release an offline trajectory dataset to public or other analyzers for data-analysis purposes in a privacy-protecting and utility-preserving fashion. Although the privacy protection will obfuscate the actual data and thus deteriorate the data utility, the data curator can control the trade-off between privacy and data utility by tuning the (total) privacy budget \(\epsilon\) to achieve the requirements of individuals and data analyzers. The pseudocode in Algorithm 1 presents a skeleton of UDPT. We also provide an illustrative example in Figure 2.  
```
1:actual trajectory dataset \(D_{A}\), (total) privacy budget \(\epsilon\). 2:obfuscated trajectory dataset \(D_{O}\). 3:Divide the total privacy budget \(\epsilon\) into 3 pieces, namely, \(\epsilon_{1}\), \(\epsilon_{2}\), and \(\epsilon_{3}\). 4:Let clusters \(\{C_{1},C_{2},\dots\}\longleftarrow\) Private location clustering with Algorithm 2, \(D_{A}\) and \(\epsilon_{1}\). 5:Let \(D_{O}\longleftarrow\O\). 6:for each \(I\) in \(D_{A}\)do
7:for each \(l_{t}\in I\)do
8: Let \(L_{t}^{(opt)}\longleftarrow\) Privately selecting utility-optimized candidate obfuscated locations for \(l_{t}\) with Algorithm 3, clusters \(\{C_{1},C_{2},\dots\}\), and \(\epsilon_{2}\). 9:endfor
10: Let \(L^{(opt)}\longleftarrow(L_{1}^{(opt)},L_{2}^{(opt)},\dots)\). 11: Let \(L_{o}\longleftarrow\) Privately select obfuscated trajectories with Algorithm 4, \(L^{(opt)}\), and \(\epsilon_{3}\). 12: Let \(D_{O}\longleftarrow D_{O}\cup L_{o}\). 13:endfor
14:return\(D_{O}\). ```  
**Algorithm 1** Utility-optimized and differentially private trajectory synthesis (UDPT). UDPT is composed of three sequential phases, where each phase is a differentially private sub-algorithm. In line 1, we divide the (total) privacy budget into three pieces and each phase (or sub-algorithm) consumes one piece. In the first phase, as shown in line 2, in order to defend against the location inference attacks, locations that occur in the actual trajectory dataset \(D_{A}\) are blurred into clusters by the private location clustering algorithm 2. Since this sub-algorithm is essentially iteratively updating a numeric objective function, UDPT exploits the Laplace mechanism to ensure \(\epsilon_{1}\)-differentially private. The sub-algorithm finally produces a set of clusters \(\{C_{1},C_{2},\dots\}\).