A Privacy–Utility Balanced Trajectory Protection Scheme via Adaptive Perturbation of Markov Transition Matrices
TL;DR
Experimental results on the real-world Geolife dataset demonstrate that compared to three differential privacy baselines, this method reduces privacy leakage, improves POI Recall rates, and decreases average geographic errors.
Abstract
The widespread adoption of Location-Based Services (LBSs) has significantly enhanced daily convenience, yet the upload and storage of user trajectory data pose substantial privacy leakage risks. Addressing the limitations of existing privacy protection methods in achieving personalized adaptation and balancing privacy with utility, this paper proposes a personalized privacy protection strategy for location trajectories based on weighted Kullback–Leibler (KL) divergence. The approach first employs a Markov transition matrix to model user movement patterns, utilizes quadtree-based dynamic grid partitioning for adaptive encoding of the state space, and introduces sensitivity scores weighted by dwell duration and visit frequency to identify critical privacy-sensitive points. It then develops an exponential decay perturbation mechanism combining regularization parameters and distortion thresholds to preserve trajectory spatial usability while protecting sensitive transitions. By quantifying privacy leakage through weighted KL divergence and measuring data utility via distortion metrics, a linearly weighted composite index is constructed, enabling personalized parameter optimization via grid search. Experimental results on the real-world Geolife dataset demonstrate that compared to three differential privacy baselines, this method reduces privacy leakage (measured by weighted KL divergence), improves POI Recall rates, and decreases average geographic errors. Paired t-tests confirm that all improvements are statistically significant (p < 0.001) with large effect sizes, validating its effectiveness and superiority in balancing privacy protection and data usability.