He, Xi, Cormode, Graham, Machanavajjhala, Ashwin, Procopiuc, Cecilia and Srivastava, Divesh (2015) DPT : differentially private trajectory synthesis using hierarchical reference systems. In: 41st International Conference on Very Large Data Bases, Hawaii, 31 Aug - 4 Sep 2015. Published in: Proceedings of the VLDB Endowment, 8 (11). pp. 1154-1165.

Preview

PDF WRAP_p1154-he_.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (3022Kb) | Preview

Request Changes to record.

Abstract

GPS-enabled devices are now ubiquitous, from airplanes and cars to smartphones and wearable technology. This has resulted in a wealth of data about the movements of individuals and populations, which can be analyzed for useful information to aid in city and traffic planning, disaster preparedness and so on. However, the places that people go can disclose extremely sensitive information about them, and thus their use needs to be filtered through privacy preserving mechanisms. This turns out to be a highly challenging task: raw trajectories are highly detailed, and typically no pair is alike. Previous attempts fail either to provide adequate privacy protection, or to remain sufficiently faithful to the original behavior.

This paper presents DPT, a system to synthesize mobility data based on raw GPS trajectories of individuals while ensuring strong privacy protection in the form of ε-differential privacy. DPT makes a number of novel modeling and algorithmic contributions including (i) discretization of raw trajectories using hierarchical reference systems (at multiple resolutions) to capture individual movements at differing speeds, (ii) adaptive mechanisms to select a small set of reference systems and construct prefix tree counts privately, and (iii) use of direction-weighted sampling for improved utility. While there have been prior attempts to solve the subproblems required to generate synthetic trajectories, to the best of our knowledge, ours is the first system that provides an end-to-end solution. We show the efficacy of our synthetic trajectory generation system using an extensive empirical evaluation.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH):	Global Positioning System, Geospatial data, Computer security
Journal or Publication Title:	Proceedings of the VLDB Endowment
Official Date:	2015
Dates:	Date Event 2015 Available
Date of first compliant deposit:	31 March 2016
Volume:	8
Number:	11
Page Range:	pp. 1154-1165
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access
Conference Paper Type:	Paper
Title of Event:	41st International Conference on Very Large Data Bases
Type of Event:	Conference
Location of Event:	Hawaii
Date(s) of Event:	31 Aug - 4 Sep 2015
Related URLs:	Open Access File

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads