# Releasing Differentially Private Trajectories with Optimized Data Utility
## 2 Related Work
### Location Perturbation  
Location perturbation usually indicates perturbing an actual location by blurring it into an area, replacing it with another location, or combining it with some indistinguishable dummy locations. Location privacy protection algorithms based on location perturba  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline  
tion can be applied to the scenarios where individual locations are continuously released, e.g., online location-based services. However, locations in the trajectory are perturbed independently and the spatial-temporal correlations within the whole trajectory are neglected, so privacy could be compromised by adversaries who have access to the correlations [23].  
An implementation of location perturbation is to blur the actual location into an area. For example, [PERSON] et al. [13] investigate the problem of privately releasing location data in an online manner. Given an actual location at some time instant, the authors blur the location into an area containing other \(k-1\) locations, which have similar geographical and semantic utility with the actual location. To improve the data utility, they model the trade-off between privacy and data utility as an optimization problem and solve it by an improved multi-objective optimization algorithm. However, the authors focus on the data utility of a single location while neglecting that of whole the trajectory. In addition, independently protecting each actual location without a comprehensive consideration of the correlations in the trajectory was subject to location inference attacks and de-anonymization attacks [23]. [PERSON] et al. [4] discover a specific applying scenario of location privacy protection, ride-sharing. They propose a private-protecting location release scheme called pShare, which applies a zone-based travel time estimation approach to reduce ride-sharing detouring waste while hiding each rider's actual location in the zone. However, changing the format of location data from point to area could lead to modification of the data analysis interfaces.  
Another implementation of location perturbation is to replace the actual location with another location. For instance, [PERSON] et al. [12] integrate the differential privacy with a privacy metric called conditional entropy to decrease adversary's correctness, together with a utility metric named worst loss for ensuring data utility. A remapping based on both metrics is appended to the output of the differential privacy, so obfuscated locations with higher utility, as well as higher privacy levels, can be produced.  
Instead of modifying the actual locations, another implementation of location perturbation is to combine the actual location with some indistinguishable dummy locations. For instance, to protect the actual locations of drivers on the internet of vehicles from being revealed by road restriction, [PERSON] et al. [16] propose a dummy-generation based location perturbation methods. The perturbed location sent to the data analyzer is composed of the actual location and several nearby fake locations following the road restriction, so it is hard for the adversary to distinguish the actual location from the dummies.