Efficient Frequency-Based Randomization for Spatial Trajectories Under Differential Privacy

The uniqueness of trajectory data for user re-identification has received unprecedented attention as the increasing popularity of location-based services boosts the excessive collection of daily trajectories with sufficient spatiotemporal coverage. Consequently, leveraging or releasing personally-sensitive trajectories without proper protection severely threatens individual privacy despite simply removing IDs. Trajectory privacy protection is never a trivial task due to the trade-off between privacy protection, utility preservation, and computational efficiency. Furthermore, recovery attack, one of the most threatening attacks specific to trajectory data, has not been well studied in the current literature. To tackle these challenges, we propose a frequency-based randomization model with a rigorous differential privacy guarantee for privacy-preserving trajectory data publishing. In particular, two randomized mechanisms are introduced for perturbing the local/global frequency distributions of a limited number of significantly essential locations in trajectories by injecting special Laplace noises. To reflect the perturbed distributions on the trajectory level without losing privacy guarantee or data utility, we formulate the trajectory modification tasks as kNN search problems and design two hierarchical indices with powerful pruning strategies and a novel search algorithm to support efficient modification. Extensive experiments on a real-world dataset verify the effectiveness of our approaches in resisting individual re-identification and recovery attacks simultaneously while still preserving desirable data utility. The efficient performance on large-scale data demonstrates the feasibility and scalability in practice.