TraCS: Trajectory Collection in Continuous Space under Local Differential Privacy

Trajectory collection is fundamental for location-based services but often involves sensitive information, such as users' daily activities, raising significant privacy concerns. Local Differential Privacy (LDP) provides strong privacy guarantees for users, even when the data collector is untrusted. Existing trajectory collection methods under LDP are limited to discrete location spaces, where the number of locations affects both privacy guarantees and trajectory utility. Moreover, many real-world scenarios, such as flying trajectories or sensor trajectories of wearable devices, operate in continuous location spaces, making existing methods inadequate. This paper shifts the focus from discrete to continuous spaces for trajectory collection under LDP. We propose two novel methods: TraCS-D, which perturbs the direction and distance of locations, and TraCS-C, which perturbs the Cartesian coordinates of locations. Both methods are theoretically and experimentally analyzed for trajectory utility in continuous spaces. TraCS can also be applied to discrete spaces by rounding perturbed locations to the nearest discrete points. In this case, TraCS's privacy and utility guarantees are independent of the number of locations in the space, and has only $\Theta(1)$ time complexity in each perturbation generation. Evaluation results on discrete location spaces validate the efficiency advantage and show that TraCS outperforms state-of-the-art methods with improved trajectory utility, especially for large privacy parameters.