PrivTrace: Differentially Private Trajectory Synthesis by Adaptive Markov Models


Haiming Wang, Zhejiang University; Zhikun Zhang, CISPA Helmholtz Center for Information Security; Tianhao Wang, University of Virginia; Shibo He, Zhejiang University; Michael Backes, CISPA Helmholtz Center for Information Security; Jiming Chen, Zhejiang University; Yang Zhang, CISPA Helmholtz Center for Information Security


Publishing trajectory data (individual's movement information) is very useful, but it also raises privacy concerns. To handle the privacy concern, in this paper, we apply differential privacy, the standard technique for data privacy, together with Markov chain model, to generate synthetic trajectories. We notice that existing studies all use Markov chain model and thus propose a framework to analyze the usage of the Markov chain model in this problem. Based on the analysis, we come up with an effective algorithm PrivTrace that uses the first-order and second-order Markov model adaptively. We evaluate PrivTrace and existing methods on synthetic and real-world datasets to demonstrate the superiority of our method.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.