LDPTrace: Locally Differentially Private Trajectory Synthesis

Abstract

Trajectory data is beneficial for many real-world applications, such as monitoring the spread of the disease through people’s movement patterns and tailoring to location-based services with population’s travel preference. However, public concerns over privacy and data protection have limited the extent to which this data is shared and exploited. Local differential privacy enables people to share a perturbed version of their data, which is an ideal technique for privacy since no one except data owners keeps the real data. Nonetheless, existing point-based perturbation mechanisms are not applicable to real-world scenarios because of poor utility, external knowledge dependence, expensive computational overhead, and vulnerability to attacks. To address these drawbacks, we propose the first locally differentially private trajectory synthesis framework, called LDPTrace, which mainly considers three important patterns estimated from synthesize trajectories that are highly similar to real trajectories with little computational cost. We also present a new method to help select a proper grid granularity without consuming privacy budget. Extensive experiments, using real-world data, a series of utility metrics and attacks, demonstrate the effectiveness and efficiency of LDPTrace.