# Releasing Differentially Private Trajectories with Optimized Data Utility
## 4 Trajectory Synthesis
### Private Location Clustering
In line 5 to 12, we assign each location in the geographical space \(\mathcal{L}\) to their closest cluster centroid. Specifically, first, in line 6, given a location \(l_{i}\in\mathcal{L}\), let \(k^{*}\) denote the index of the cluster centroid which is closest to \(l_{i}\). In particular, if there were more than one closest centroids, we uniformly chose one from them at random. Next, we add the location \(l_{i}\) into the cluster \(C_{k^{*}}\), as shown in line 7. Then, to facilitate the calculation of objective function, we introduce an indicator of the relation between locations and clusters, which is defined in Equation (3). Let \(\gamma_{i,k}=1\) indicate the fact that the location \(l_{i}\) belongs to the cluster \(C_{k}\), and \(\gamma_{i,k}=0\) otherwise. In this case, we have \(\gamma_{i,k^{*}}=1\), as shown in line 8. We also have \(\gamma_{i,k}=0\) for \(k\
eq k^{*}\), as shown in line 10. \[\gamma_{i,k}= \begin{cases}1,&\text{if }l_{i}\in C_{k}\\ 0,&\text{otherwise}\.\end{cases}  \tag{3}\]  
In line 13, we calculate the objective function of the private location clustering, \(g\), which is defined in Equation (4), \(K\) the number of clusters, \(l_{i}\) the \(i\)-th location in \(\mathcal{L}\), \(c_{k}\) the \(k\)-th cluster centroid, \(Lap(\frac{p\Delta g}{\epsilon_{1}})\) the random Laplace noise generated by the Laplace mechanism in Theorem 1. \[g=\sum_{i=1}^{|\mathcal{L}|}\sum_{k=1}^{K}\gamma_{i,j}\|l_{i}-c_{k}\|_{2}+Lap( \frac{p\Delta g}{\epsilon_{1}}) \tag{4}\]  
In Equation (4), the maximum number of iterations, \(p\), is a hyperparameter of the algorithm. A larger \(p\) theoretically results in a better performance of clustering. However, since we need to divide the privacy budget \(\epsilon_{1}\) into \(p\) pieces, a larger number of iterations could inject larger noise to a single iteration. The iteration often ends in advance, i.e., the actual number of iterations is likely less than \(p\), so we can leave the unused privacy budget to the following steps including the Sections 4.3 and 4.4. We will discuss this hyperparameter in our experiments. In addition, in Equation (4), \(\epsilon_{1}\) represents the privacy budget allocated to the private location clustering algorithm. It controls the trade-off between privacy and data utility, where a smaller value indicates a stronger guarantee of privacy while a poor preservation of data utility. Previous studies suggest that taking values in the interval \([0.1,10]\) often brings about a reasonable trade-off between privacy and data utility [7]. In Equation (4), the Laplace noise, \(Lap(\frac{p\Delta g}{\epsilon_{1}})\), is actually a random variable following the Laplace distribution, a.k.a., double exponential distribution. Its probability density function is defined in Equation (5), where \(x\) represents a possible noise value, \(pdf(x)\) means the probability density w.r.t. \(x\), and \(\Delta g\) is the sensitivity of the objective function. According to the Laplace mechanism [7], the sensitivity indicates the maximum change of \(\sum_{i=1}^{|\mathcal{L}|}\sum_{k=1}^{K}\gamma_{i,j}\|l_{i}-c_{k}\|_{2}\) when removing or adding one location record from the actual trajectory dataset \(D_{A}\). Therefore, we define the sensitivity \(\Delta g\) as the maximum distance between locations in the geographical space \(\mathcal{L}\); that is, \(\Delta g=max\{\|l_{i}-l_{j}\|_{2}\mid\forall\,l_{i},l_{j}\in\mathcal{L}\}\). In this case, we can ensure that the output of the private location clustering algorithm is insensitive to the change of a single record in the actual dataset. In other words, we achieve the differential privacy for our private location clustering algorithm. \[pdf(x)=\frac{\epsilon_{1}}{2p\Delta g}\exp(-\frac{\epsilon_{1}|x|}{p\Delta g} ),\ x\in\mathbb{R} \tag{5}\]  
In line 14, we check whether the objective function \(g\) converges. If the change of objective function values between consecutive iterations is not greater than some threshold, we say that the objective function converges.