# Releasing Differentially Private Trajectories with Optimized Data Utility
## 4 Trajectory Synthesis
### Privately Synthesizing Obfuscated Trajectories  
A common idea of existing trajectory synthesis methods is to build a trajectory generator that has learned the population movement patterns and then produce the obfuscated trajectory dataset \(D_{O}\) in a generative manner. However, individual movement patterns could be destroyed, so numerous data analysis tasks that rely on individual-level data utility, e.g., periodic patterns mining [9] could suffer poor performance. To tackle this issue, we synthesize the obfuscated trajectories for each individual, i.e., each actual trajectory, independently. In this case, the privacy budgets consumed by all individuals do not accumulate according to the differential privacy's parallel composition property. In other words, when the total privacy budget is fixed, we can spare a larger privacy budget for the trajectory synthesis of a single individual, resulting in less noise injection and thus better preservation of data utility. In addition, to defend against the de-anonymization attacks, for each actual trajectory, we privately synthesize more than one indistinguishably obfuscated trajectories that share the most similar data utility with the actual trajectory.  
In the previous section, for any actual trajectory \(I\), we obtained a sequence of candidate obfuscated location sets. To privately synthesize obfuscated trajectories for \(I\), first, to preserve the geographical and semantic utility, we capture individual movement patterns by the CRF. Second, we synthesize a set of candidate obfuscated trajectories by the CRF sequence decoding based on the sequence of candidate obfuscated location sets. Then, some candidates are privately selected as the (final) obfuscated trajectories. Since the obfuscated trajectories maintain similar data utility with the actual trajectory, they cannot be distinguished from each other, providing a defense against de-anonymization attacks. We formalize the aforementioned steps by the pseudocode in Algorithm 4.  
```
0: sequence of candidate obfuscated location sets \(\mathbf{L}^{(opt)}\), actual trajectory \(I\), sensitivity \(\Delta\Pr\), number of (final) obfuscated trajectories \(N\).
0: a set of (final) obfuscated trajectories \(\mathbf{L}_{o}\).
1: Construct the obfuscated trajectory synthesizer with \(I\).
2: // Produce a number of candidate obfuscated trajectories.
3:\(\mathbf{L}_{c}=\O\).
4:for\(i=1\) to \(N\)do
5:\(<I_{c}^{(i)},\Pr(I_{c}^{(i)}|I)>\longleftarrow\) Produce the \(i\)-th most probable candidate obfuscated trajectory and its probability with Viterbi, \(\mathbf{L}^{(opt)}\) and the synthesizer.
6: Add \(<I_{c}^{(i)},\Pr(I_{c}^{(i)}|I)>\) into \(\mathbf{L}_{c}\).
7:endfor
8: // Privately select the (final) obfuscated obfuscated trajectories from the candidates.
9:for\(i=1\) to \(N\)do
10: Calculate the probability of \(I_{c}^{(i)}\) being selected as the (final) obfuscated trajectory, i.e., \(\Pr(I_{c}^{(i)})\), with Equation (11).
11:endfor
12:\(\mathbf{L}_{o}\longleftarrow\) Randomly sample \(\lfloor N/2\rfloor\) candidate obfuscated trajectories from \(\mathbf{L}_{c}\) following its probability distribution without replacement.
13:return\(\mathbf{L}_{o}\).
```  
**Algorithm 4** Private synthesizing obfuscated trajectories.