Releasing Correlated Trajectories : Towards High Utility and Optimal Differential Privacy

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

19 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)1109-1123
Journal / PublicationIEEE Transactions on Dependable and Secure Computing
Issue number5
Online published10 Jul 2018
Publication statusPublished - Sep 2020


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.

Research Area(s)

  • Constrained optimization problems, Correlation, Differential Privacy, Lagrange Multiplier Method, Markov processes, Optimization, Privacy, Trajectory, Mutual-trajectory correlation