Differentially Private Protection Of General Trajectory Data Publishing

Trajectory data,i.e.,human mobility traces,is extremely valuable for a wide range of mobile applications.The traces user made everyday,will be collected and published.So researchers can use these traces for data mining or somehthing else.However,pub-lishing raw trajectories without special sanitization poses serious threats to individual privacy.Differentially private,as a popular model in sercurity,gains extensive attention in privacy protection in data publishing.Recently,researchers begin to leverage dif-ferential privacy to solve this challenge.Nevertheless,existing mechanisms make an implicit assumption that the trajectories contain a lot of identical prefixes or n-grams,which is not true in many applications.This paper aims to remove this assumption and propose a differentially private publishing mechanism for more general time-series trajectories.One natural solution is to generalize the trajectories,i.e.,merge the locations at the same time.However,ordinary merging schemes may breach differential privacy.We,thus,propose the first differentially-private generalization algorithm for trajectories,which leverage a carefully-designed exponential mechanism to probabilistically merge nodes based on trajectory distances.Afterwards,we propose another efficient algorithm to release tra-jectories after generalization in a differential private manner.Our experiments with real-life trajectory data show that the proposed mechanism maintains high data utility and is scalable to large trajectory datasets.