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. Hence,
our goal is to provide a system to synthesize mobility data
based on raw GPS trajectories of individuals while ensuring strong
privacy protection in the form of ε-differential privacy.
Project Members at Duke
- DPT: Differentially
private trajectory synthesis using hierarchical reference systems.
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. Details can be found in
- Paper: Xi He, Graham Cormode, Ashwin Machanavajjhala, Cecilia M. Procopiuc, Divesh Srivastava, "DPT: Differentially
private trajectory synthesis using hierarchical reference systems", VLDB 2015 pdf
- Source code (updated by Aug 6, 2015): code without data sample, code with data sample
- Demo: Xi He, Nisarg Raval, Ashwin Machanavajjhala, "A Demonstration of VisDPT: visual exploration of differentially private
trajectories", VLDB 2016 (Best Demo).
- More ...