Differentially Private and Utility Preserving Publication of Trajectory Data

The universal popularity of GPS-enabled mobile devices and traffic navigation services has fueled the growth of trajectory data, as evidenced by Uber Movement and NYC taxi data release. Although trajectory data can generate valuable insights and value-added services for many, publishing this data while respecting mobile users' privacy has been a long-standing challenge. In this paper, we present DP-Star, a methodical framework for publishing trajectory data with differential privacy guarantee as well as high utility preservation. DP-Star relies on a novel combination of several components. First, DP-Star's normalization algorithm uses the Minimum Description Length metric to summarize raw trajectories using their representative points, thereby achieving a desirable trade-off between the preciseness and conciseness of their information content. Second, DP-Star constructs a density-aware grid which ensures spatial densities can be preserved despite the noise added to satisfy differential privacy. Third, DP-Star preserves the correlations between trajectories' end points through a private trip distribution, and intermediate points through a private Markov mobility model. Finally, DP-Star estimates users' trip lengths using a median length estimation method, and generates synthetic trajectories that preserve both differential privacy and high utility. Our experimental comparison shows that DP-Star significantly outperforms existing approaches in terms of trajectory utility and accuracy.