# Releasing Differentially Private Trajectories with Optimized Data Utility
## 3 Preliminaries
### Problem Statement  
**Notations.** Consider that a set of individuals \(\mathcal{U}=\{u_{1},u_{2},\dots\}\) move in a geographic space, which is denoted by a set of discrete geographical locations, \(\mathcal{L}=\{l_{1},l_{2},\dots\}\), where a location is represented by a vector of GPS coordinates, e.g., \((-73.989308,40.741895)\). The (actual) trajectory of any individual \(u\in\mathcal{U}\) is represented by a sequence of location records, \(\mathbf{l}=(l_{1},l_{2},\dots,l_{t},\dots)\), which \(u\) has visited over a period of time \(\mathcal{T}=\{1,2,3,\dots\}\), where \(l_{t}\) records \(u\)'s location at the time instant \(t\in\mathcal{T},l_{1},l_{2},\dots\in\mathcal{L}\).  
**Problem to tackle.** Suppose that a data curator, e.g., the New York City Taxi & Limousine Commission [2], has collected a dataset of actual trajectories of the individuals, \(D_{A}=\{\mathbf{l}_{u}|u\in\mathcal{U}\}\). The data curator would like to publish the dataset to some (potentially untrusted) analyzers, e.g., insurance companies and academic institutions, for facilitating data-mining purposes. Meanwhile, it also hopes to keep individual whereabouts private from the analyzers. To this end, the data curator employs a location privacy protection algorithm to obfuscate actual trajectories \(D_{A}\), resulting in an offline dataset of obfuscated trajectories \(D_{O}\). After that, \(D_{O}\) is published to the data analyzers.  
**Design objectives.** The data curator expects that the location privacy protection algorithm should achieve the following two objectives. (i) 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. (ii) Effective prevention from the location inference attacks and the de-anonymization attacks. In other words, the chance that any actual location or individual identity is derived by observing the released dataset \(D_{O}\) should be restricted to some magnitude specified by the data curator.  
The location privacy protection algorithm, denoted by \(f\): \(D_{A}\to D_{O}\), is a randomized function that outputs the obfuscated trajectory dataset \(D_{O}\) given the actual trajectory dataset \(D_{A}\). In this work, the \(f\) is implemented by UDPT, a privacy-protecting and utility-optimized trajectory synthesis algorithm. \(P(f)\) measures the privacy security of the algorithm. The obfuscation usually leads to a loss of data utility, denoted by \(Q(f)\). The computation of \(P(f)\) and \(Q(f)\) depends on specified metrics, which will be elaborated in our experimental Section 5.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Symbol** & **Meaning** \\ \hline \(u\) & individual \\ \hline \(\mathcal{U}\) & set of individuals \\ \hline \(\mathcal{T}\) & set of time instants \\ \hline \(\mathcal{L}\) & geographical space \\ \hline \(\mathbf{l}\) & trajectory \\ \hline \(l_{t}\) & location record at the time instant \(t\) \\ \hline \(D_{A}\) & actual trajectory dataset \\ \hline \(D_{O}\) & obfuscated trajectory dataset \\ \hline \(f\) & location privacy protection algorithm \\ \hline \(P(f)\) & privacy metric \\ \hline \(Q(f)\) & utility metric \\ \hline \hline \end{tabular}
\end{table}
Table 2: List of notations.