TGM: A Generative Mechanism for Publishing Trajectories With Differential Privacy

We describe a new generative algorithm called trajectory generative mechanism (TGM) for publishing trajectory datasets with epsilon-differential privacy guarantee, which achieves substantially higher computational efficiency and utility (practical) than the state-of-the-art algorithms. Our algorithm first encodes (models) the data as a graphical generative model and accurately captures the statistics of moving object trajectories. Using this model, TGM then privately generates synthetic trajectories such that the noise is optimally added to capture the movement direction of an object. Our algorithm preserves both the spatial and temporal information of trajectories in the generated dataset, requires less memory and computation than the competing approaches, and preserves the properties of real trajectory data in terms of traveled distance and stay location. We demonstrate the performance of TGM on both real and simulated datasets with a wide range of settings. Our experimental results show that TGM achieves high utility and efficiency by using the properties of the data.