# Releasing Differentially Private Trajectories with Optimized Data Utility
## 3 Preliminaries
### Mechanisms and Properties of Differential Privacy  
Note that the differential privacy is actually a goal of privacy protection, rather than a specific privacy protection algorithm. To build a specific privacy protection algorithm, e.g., the trajectory synthesis algorithm in this work, the differential privacy expresses the algorithm's access to the dataset as a series of queries on that dataset. For instance, the private location clustering of UDPT, see Section 4.2, is essentially a series of queries on the actual trajectory dataset with the objective function. Individual privacy is protected by injecting random noise into the query results. There are mainly two types of queries, namely, numeric queries and categorical queries. Previous studies have provided two general-purpose and differentially private algorithms, namely Laplace mechanism [7] and exponential mechanism [24], to generate random noise for a numeric query and a categorical query, respectively. We introduce the two mechanisms as follows. **Laplace mechanism. ** [PERSON] et al. [7] proposed this mechanism which takes as inputs a dataset \(D\), a privacy protection algorithm \(f\), and the privacy budget \(\epsilon\). Theorem 1 presents a formal definition It is designed for answering the numeric query whose output is real. It added a Laplace noise to the actual query result \(f(D)\). The Laplace noise is sampled from Laplace distribution \(Lap(b)\) with the probability density function \(Pr(x|\mu,b)=(2b)^{-1}e^{-b^{-1}|x-\mu|}\), where \(\mu\) is the location parameter and \(b\) is the scale parameter determined by sensitivity \(\Delta f\) and desired privacy budget \(\epsilon:b=\Delta f/\epsilon\). \(\mu\) is usually assigned 0. The sensitivity \(\Delta f\) indicates the maximum change of the actual query result \(f(D)\) when removing or adding one record from the dataset \(D\), which relies on the specific query. **Theorem 1**. : _For any privacy protection algorithm \(f:D\to R^{d}\), the following algorithm achieves \(\epsilon\)-differential privacy._  
\[A(D)=f(D)+Lap(\Delta f/\epsilon) \tag{2}\]  
**Exponential mechanism. ** For the query whose output is not real, i.e., the domain of output is categorical, [PERSON] et al. [24] proposed the exponential mechanism. Theorem 2 presents a formal definition of the exponential mechanism. It defines a score function \(q\) that assigns a real-valued utility score to each categorical output \(r\in R\). The exponential mechanism assigns exponentially higher probabilities of being selected to outputs of higher utility scores. \(\epsilon\) represents the privacy budget. The sensitivity of the score function \(\Delta q\) equals to the maximum change of the score function \(q\) when removing or adding one record from the dataset \(D\), which relies on the specific score function that we use. **Theorem 2**. : _For any privacy protection algorithm \(f:D\to R\), choosing an output \(r\in R\) with probability proportional to \(e^{\frac{\epsilon(D)}{2\Delta q}}\) ensures the algorithm \(\epsilon\)-differential privacy [24]._  
The properties of differential privacy define the composability between differentially private algorithms, e.g., the Laplace mechanism and the exponential mechanism, and enables the building of a complex algorithm. Given some differentially private algorithms \(f_{1},f_{2},\ldots,f_{n}\) that satisfies \(\epsilon_{1}\), \(\epsilon_{2},\ldots,\epsilon_{n}\)-differential privacy respectively, the properties of differential privacy also describe the relationship between the total privacy budget (indicating the overall privacy guarantee) and the privacy budget pieces of sub-algorithms. We introduce the two properties as follows. **Theorem 3** (sequential composition [24]).