# Releasing Differentially Private Trajectories with Optimized Data Utility
## 4 Trajectory Synthesis
### Privately Synthesizing Obfuscated Trajectories
#### 4.4.2 Privately Selecting Obfuscated Trajectories  
As given by line 2 to line 6 of Algorithm 4, with the obfuscated trajectory synthesizer, we produce the (final) obfuscated trajectories by sequence decoding of the synthesizer. The sequence decoding refers to finding the most probable trajectories corresponding to a given mobility feature sequence, which can be solved by the Viterbi algorithm. An improved version [32] can produce a number of most probable trajectories that share similar movement patterns, which inspires us to produce a number of indistinguishably obfuscated trajectories to prevent de-anonymization attacks. The trajectories produced by Viterbi are called by candidate obfuscated trajectories, represented by \(\mathbf{L}_{c}\). Let \(N\) denote the number of candidate obfuscated trajectories, thus we have \(\mathbf{L}_{c}=\{I_{c}^{(1)},\ldots,I_{c}^{(N)}\}\). The Viterbi algorithm can be further improved by restricting the sample space to the Cartesian product of the candidate obfuscated location sets in \(\mathbf{L}^{(opt)}\), because the locations that cannot well preserve the data utility of the actual locations have been pruned after the utility optimization in Section 4.3.2. As shown in line 5, we exploit the improved Viterbi algorithm to produce the \(i\)-th most probable candidate obfuscated trajectory \(I_{c}^{(i)}\), together with its probability \(\Pr(I_{c}^{(i)}|I)\), where \(i=1,2,\ldots,N\). \(\Pr(I_{c}^{(i)}|I)\) represents the possibility that Viterbi regards \(\mathbf{I}_{c}^{(i)}\) as the actual trajectory \(I\), which also indicates to what extent \(I_{c}^{(i)}\) can preserve the movement patterns in \(I\). The probability can be directly calculated by the improved Viterbi algorithm. We omit the computational details, which can be found in [32]. In line 6 of Algorithm 4, we collect the produced candidate obfuscated trajectories with the set \(\mathbf{L}_{c}\) i, where \(|\mathbf{L}_{c}|=N\). The Viterbi algorithm is essentially a query that takes as input \(\mathbf{L}^{(opt)}\) and the synthesizer, and then produces categorical outputs, i.e., a number of candidate obfuscated trajectories. Note that the above synthesizer is constructed based on the actual trajectory \(I\) without any privacy-protecting measure. In this case, the query result is sensitive to the change of a single location in the actual trajectory \(I\). A location inference attacker could derive the actual location by observing the query result. To tackle this issue, we exploit the exponential mechanism to perturb the outputs of the Viterbi algorithm. Recall the exponential mechanism in Theorem 2, the idea is to consider the probability \(\Pr(I_{c}^{(i)}|I)\) as the score of the candidate obfuscated trajectory \(I_{c}^{(i)}\), and then to select the (final) obfuscated trajectory \(I_{o}^{(i)}\) from the candidates \(\mathbf{L}_{c}\) with the probability proportional to \(\exp(\frac{\epsilon_{3}\Pr(I_{o}^{(i)}|I)}{2\Delta\Pr})\). The normalized probability over all possible outputs is defined in Equation (11). \[\Pr(I_{o}^{(i)})=\frac{\exp\left(\frac{\epsilon_{3}\Pr(I_{o}^{(i)}|I)}{2\Delta \Pr}\right)}{\sum_{I_{o}^{(i)}\in\mathbf{L}_{c}}\exp\left(\frac{\epsilon_{3}\Pr(I_ {o}^{(i)}|I)}{2\Delta\Pr}\right)} \tag{11}\]  
where \(\epsilon_{3}\) is the privacy budget of the exponential mechanism, which is determined by the data curator, as shown in line 1 of Algorithm 1. \(\Delta\Pr\) represents the maximum change of the score when removing or adding a single location from the actual trajectory \(I\), according to the definition of differential privacy. Since the probability \(\Pr(I_{o}^{(i)}|I)\) takes values in \([0,1]\), we have \(\Delta\Pr=1\). As show in line 8 to 12 of Algorithm 4, we randomly sample \(\lfloor N/2\rfloor\) candidates from \(\mathbf{L}_{v}\) without replacement to constitute the set of final obfuscated trajectories, \(\mathbf{L}_{o}\) following the probability distribution in Equation (11).