An Efficient Local Differential Privacy Approach for Trajectory Publishing with High Utility

Trajectory data underpins many data-driven spatiotemporal applications, such as navigation or ride-hailing. However, privacy concerns hinder the collection and utilization of high-quality, large-scale trajectory data. Local Differential Privacy (LDP), injecting noise to trajectories for perturbation, has been proposed to protect its privacy. Yet, existing LDP-based mechanisms overlook widely adopted denoising pre-processings of trajectories (e.g., filtering, outlier detection and trajectory similarity measure), rendering noise injection in the whole domain unnecessary and incurring low utility and poor efficiency in practice. In this paper, we observe that various denoising pre-processings all lead to bringing thresholds to perturbation domain, which indicates the noise injected by LDP mechanisms may be useless. This provides an opportunity for enhancing utility of LDP mechanism by eliminating unnecessary noise injection. We propose t-LDP, a novel LDP-based mechanism for trajectory publishing. It integrates threshold into noise injection, eliminating redundant noise that could be denoised by trajectory pre-processing. Additionally, we devise an automaton-based algorithm for efficient perturbation. Experiments on real datasets demonstrate the effectiveness and efficiency of our approach. Especially in extensive perturbation domains, our method shows a 20% improvement of utility and a 600-fold increase in speed compared to existing methods while maintaining robust privacy protection.