# Releasing Differentially Private Trajectories with Optimized Data Utility
## 4 Trajectory Synthesis
### Privately Selecting Utility-Optimized Candidate Obfuscated Locations
#### 4.3.1 Modeling Utility Optimization Problem  
Given any actual location \(l_{t}\) in the actual trajectory \(I\), there are two objectives for selecting candidate obfuscated location, namely, (i) preserving the geographical utility of the actual location as much as possible, and (ii) maintaining the semantic utility of the actual location to the most extent. On the one hand, in order to preserve the geographical utility, a solution that has been proved feasible by existing work [12] is to select the location nearby the actual location as the obfuscated location. In this work, we borrow this solution. On the other hand, to preserve the semantic utility, we prefer to select the locations sharing the same (or similar) semantics with the actual location as the obfuscated location. However, there exist conflicts between the two objectives since nearby locations do not always have similar semantics [10]. Therefore, an optimal decision needs to be taken in the presence of trade-offs between the two conflicting objectives, which is known as a multi-objective optimization problem. Generally, the way to solve the problem is formalizing the objectives as functions and then finding the optimal solution over the objective functions by optimization algorithms such as genetic algorithm. We formalize the two objectives as follows. The first objective, i.e., (i) preserving the geographical utility of the actual location as much as possible, is defined as selecting \(M\) candidate obfuscated locations, denoted by \(L_{t}^{(geo)}\), which are closest to the actual location \(l_{t}\). Equation (6) presents a formal expression, which means minimizing the total Euclidean distance between \(M\) candidate obfuscated locations and the actual location \(l_{t}\). \[L_{t}^{(geo)}=arg\ min\sum_{i=1,l_{i}\in\mathcal{L}}^{M}\|l_{t}-l_{i}\|_{2} \tag{6}\]  
Before formalizing the second objective, we need to acquire the location semantics and define the semantic distance measure. The acquirement of location semantics can be achieved by the application programming interfaces (APIs) of many LBS providers, such as Foursquare and Google Maps. Foursquare also provides a hierarchical tree representation of location categories [27], which contains ten coarse-grained categories in the first level and hundreds of fine-grained ones in the second level. The path distance between two category nodes in the tree indicates their discrepancy in semantics, which inspires us to propose a graph-theory-based distance metric to measure the discrepancy between the categories of the candidate obfuscated location \(l_{c}\) and the actual location \(l_{l}\). We denote the semantic distance by \(dist_{sem}(\cdot,\cdot)\) and give its definition by Equation (7). \[dist_{sem}(l_{t},l_{c})=\frac{d(l_{t},l_{c})}{d(root,l_{t})+d(root,l_{c})} \tag{7}\]  
where \(d(\cdot,\cdot)\) denotes the length of the shortest path between the categories of two locations on the semantic tree, \(root\) represents the root node of the tree. In particular, if two categories are equal, their semantic distance is 0, while if they have the same parent category, the distance is 2. The semantic difference between two categories will be normalized by the sum of the nodes' depths; that is, the distance to the root node. The second objective, i.e., (ii) maintaining the semantic utility of the actual location to the most extent, is defined as selecting \(M\) candidate obfuscated locations, denoted by \(L_{t}^{(sem)}\), which are most similar to the actual location \(l\) in terms of location semantics. Then, the second objective is formulated as minimizing the semantic distances between the candidate obfuscated locations and the actual location, which is given by Equation (8).