  With the popularity of GPS-enabled devices, a huge amount of trajectory data
has been continuously collected and a variety of location-based services have
been developed that greatly benefit our daily life. However, the released
trajectories also bring severe concern about personal privacy, and several
recent studies have demonstrated the existence of personally-identifying
information in spatial trajectories. Trajectory anonymization is nontrivial due
to the trade-off between privacy protection and utility preservation.
Furthermore, recovery attack has not been well studied in the current
literature. To tackle these issues, we propose a frequency-based randomization
model with a rigorous differential privacy guarantee for trajectory data
publishing. In particular, we introduce two randomized mechanisms to perturb
the local/global frequency distributions of significantly important locations
in trajectories by injecting Laplace noise. We design a hierarchical indexing
along with a novel search algorithm to support efficient trajectory
modification, ensuring the modified trajectories satisfy the perturbed
distributions without compromising privacy guarantee or data utility. Extensive
experiments on a real-world trajectory dataset verify the effectiveness of our
approaches in resisting individual re-identification and recovery attacks and
meanwhile preserving desirable data utility as well as the feasibility in
practice.
