Releasing Correlated Trajectories : Towards High Utility and Optimal Differential Privacy

Mutual correlation between trajectories of two users is very helpful to real-life applications such as product recommendation and social media. While providing tremendous benefits, the releasing of correlated trajectories may leak sensitive social relations, due to potential links between mutual correlations and social relations. To the best of our knowledge, we take the first step to propose a mathematically rigorous n-body Laplace framework, satisfying ε-differential privacy, which efficiently prevents social relations inference through the mutual correlation between n-node trajectories of two users. The problem is mathematically formulated by defining a trajectory correlation score to measure the social relation between two users. Then, under the n-body Laplace framework, we propose two Lagrange Multiplier-based Differentially Private (LMDP) approaches to optimize the privacy budgets, for the given data utility measured by location distances and the data utility measured by location correlations, i.e., UD-LMDP and UC-LMDP. Also, we present detailed privacy and data utility analyses, as well as adversary knowledge analysis of LMDP. Finally, we perform experimental studies with a real-life dataset. Our experimental results show that our proposed approaches achieve better privacy and data utility than the existing approaches.