Adaptive Differential Privacy Mechanism for Aggregated Mobility Dataset

Ammar Haydari, H. Michael Zhang, Chen-Nee Chuah, Jane MacFarlane, Sean Peisert

Abstract

Location data is collected from users continuously to understand their mobility patterns. Releasing the user trajectories may compromise user privacy. Therefore, the general practice is to release aggregated location datasets. However, private information may still be inferred from an aggregated version of location trajectories. Differential privacy (DP) protects the query output against inference attacks regardless of background knowledge. This paper presents a differential privacy-based privacy model that protects the user's origins and destinations from being inferred from aggregated mobility datasets. This is achieved by injecting Planar Laplace noise to the user origin and destination GPS points. The noisy GPS points are then transformed into a link representation using a link-matching algorithm. Finally, the link trajectories form an aggregated mobility network. The injected noise level is selected using the Sparse Vector Mechanism. This DP selection mechanism considers the link density of the location and the functional category of the localized links. Compared to the different baseline models, including a k-anonymity method, our differential privacy-based aggregation model offers query responses that are close to the raw data in terms of aggregate statistics at both the network and trajectory-levels with maximum 9% deviation from the baseline in terms of network length.

Introduction

Location data is a goldmine for urban planners and researchers, but it is a minefield for privacy. Even when data is "aggregated" (e.g., showing total flows between zones), clever attackers can often reconstruct individual trajectories or identify sensitive locations like homes and workplaces.

The traditional solution is Differential Privacy (DP)—adding statistical noise to the data. However, mobility data has a unique "utility" problem: a naive GPS perturbation of just 50 meters might accidentally move a vehicle from a local street onto a restricted highway or the wrong side of a one-way road. This "utility loss" makes the resulting data useless for transportation studies. The challenge is finding a way to add enough noise to hide individuals without breaking the underlying logic of the road network.

Methodology

The authors propose DP-ANI (Differentially Private Adaptive Noise Injection). The pipeline works in three main stages:

  1. Private Bounding Range Selection: Instead of adding a fixed amount of noise everywhere, the algorithm looks at the local road density. In a dense city center, a small noise radius is enough to hide a user among many possible streets. In sparse rural areas, a larger radius is needed. To prevent the "noise level" itself from leaking information, they use the Sparse Vector Technique (SVT) to select this radius privately.
  2. Planar Laplace Noise: Once the radius is set, they apply Planar Laplace noise to the GPS coordinates of trip origins and destinations. This is a 2D version of the standard DP noise mechanism.
  3. Link-Matching and Aggregation: The noisy GPS points are snapped back to the nearest logical road segment using a link-matching algorithm. These "privatized" trajectories are then aggregated into a final mobility network.
The DP-ANI framework pipeline for generating private aggregated mobility networks.

This approach is "network-aware," meaning it respects the functional category of roads (e.g., arterial vs. local) during the matching process to preserve the traffic characteristics of the original dataset.

Experimental Evaluation

The study evaluated the model using a real-world dataset of fleet and consumer GPS trajectories from the San Francisco Bay Area (January to February 2019). For computational tractability, the researchers focused on a subset of data from the Berkeley area during a specific one-hour window (1 PM to 2 PM).

Results and Discussion

The core insight of this work is that privacy requirements are density-dependent. The amount of noise required to achieve "indistinguishability" is inversely proportional to the number of nearby alternatives (road links). By using SVT to pick the noise radius, the system only "pays" for the privacy cost when the density threshold changes.

Key results include:

  • Network Length Utility: The DP-ANI model resulted in a maximum of 9% deviation from the baseline network length, significantly outperforming standard DP methods and $k$-anonymity approaches which often saw much higher divergence.
  • OD Link Preservation: At a privacy level of $\epsilon = 0.1$, the model preserved more than 75% of the original origin-destination links, meaning the "noisy" trips still started and ended in logically similar areas.
  • Distributional Similarity: Using the Wasserstein distance metric, the authors showed that DP-ANI maintains the statistical distribution of road functional classes much better than non-adaptive baselines.
Comparison of network length utility across different epsilon values for DP-ANI and baseline models.

Conclusion

While DP-ANI shows promise, several hurdles remain for real-world deployment. In sparse datasets, high perturbation is still required, which can obscure subtle patterns. Additionally, even with adaptive noise, a point might still "jump" to the other side of a divided highway. Future work will focus on decentralized local differential privacy models to reduce computational costs and risks associated with centralized data collection, as well as addressing distinct movement patterns in fleet vs. consumer data.

Summary updated

Abstract

Location data is collected from users continuously to understand their mobility patterns. Releasing the user trajectories may compromise user privacy. Therefore, the general practice is to release aggregated location datasets. However, private information may still be inferred from an aggregated version of location trajectories. Differential privacy (DP) protects the query output against inference attacks regardless of background knowledge. This paper presents a differential privacy-based privacy model that protects the user's origins and destinations from being inferred from aggregated mobility datasets. This is achieved by injecting Planar Laplace noise to the user origin and destination GPS points. The noisy GPS points are then transformed into a link representation using a link-matching algorithm. Finally, the link trajectories form an aggregated mobility network. The injected noise level is selected using the Sparse Vector Mechanism. This DP selection mechanism considers the link density of the location and the functional category of the localized links. Compared to the different baseline models, including a k-anonymity method, our differential privacy-based aggregation model offers query responses that are close to the raw data in terms of aggregate statistics at both the network and trajectory-levels with maximum 9% deviation from the baseline in terms of network length.
BibTeX
@misc{haydari2021adaptive,
  author = {Ammar Haydari and H. Michael Zhang and Chen-Nee Chuah and Jane MacFarlane and Sean Peisert},
  title = {{Adaptive Differential Privacy Mechanism for Aggregated Mobility Dataset}},
  year = {2021},
  eprint = {2112.08487},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.08487},
}

Loading related content...

Figure