PrivTrace: Differentially Private Trajectory Synthesis by Adaptive Markov Model

USENIX Security 2023

Haiming Wang1 Zhikun Zhang2 Tianhao Wang3 Shibo He1 Michael Backes2 Jiming Chen1 Yang Zhang2

1. Zhejiang University 2. CISPA Helmholtz Center for Information Security 3. University of Virginia

Abstract


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.

Resources


Citation 

 @inproceedings{WZWHBCZ23,
    author = {Haiming Wang and Zhikun Zhang and Tianhao Wang and Shibo He and Michael Backes and Jiming Chen and Yang Zhang},
    title = {{PrivTrace: Differentially Private Trajectory Synthesis by Adaptive Markov Model}},
    booktitle = {{USENIX Security}},
    publisher = {},
    year = {2023},
}