Collecting Individual Trajectories under Local Differential Privacy

In this paper, we tackle the problem of collecting individual trajectories under local differential privacy. The key challenge is how to achieve high utility of the collected trajectories while satisfying the strong privacy guarantee. To overcome this challenge, we present a novel approach, which is referred to as PrivTC. In PrivTC, we first design a locally differentially private grid construction method to instruct the aggregator to lay an appropriate grid on the given geospatial domain. Then we propose a locally differentially private spectral learning method to help the aggregator learn the Hidden Markov Model (HMM) from users' trajectories discretized by the constructed grid. Finally, the aggregator generates a synthetic trajectory dataset as a surrogate for the original one from the learned HMM. Extensive experiments on real datasets confirm the effectiveness of PrivTC.