Publishing Location Dataset Differential Privately with Isotonic Regression

Chengfang Fang, Ee-Chien ChangarXiv 2011 · OpenReview

Abstract

We consider the problem of publishing location datasets, in particular 2D spatial pointsets, in a differentially private manner. Many existing mechanisms focus on frequency counts of the points in some a priori partition of the domain that is difficult to determine. We propose an approach that adds noise directly to the point, or to a group of neighboring points. Our approach is based on the observation that, the sensitivity of sorting, as a function on sets of real numbers, can be bounded. Together with isotonic regression, the dataset can be accurately reconstructed. To extend the mechanism to higher dimension, we employ locality preserving function to map the dataset to a bounded interval. Although there are fundamental limits on the performance of locality preserving functions, fortunately, our problem only requires distance preservation in the "easier" direction, and the well-known Hilbert space-filling curve suffices to provide high accuracy. The publishing process is simple from the publisher's point of view: the publisher just needs to map the data, sort them, group them, add Laplace noise and publish the dataset. The only parameter to determine is the group size which can be chosen based on predicted generalization errors. Empirical study shows that the published dataset can also exploited to answer other queries, for example, range query and median query, accurately.

Introduction

Publishing location data is a significant privacy challenge. Even when datasets are anonymized, individuals can often be re-identified using background knowledge. Differential Privacy (DP) provides a robust mathematical framework for privacy by adding noise to data, but its application to spatial pointsets is non-trivial.

Traditional methods often rely on 'equi-width' histograms, which divide a map into a fixed grid and add noise to the point counts in each cell. However, selecting an optimal grid size is difficult: a grid that is too fine results in noise overwhelming the signal, while a grid that is too coarse loses critical spatial detail. This paper proposes a method to 'publish data, not the data mining result,' creating a flexible, differentially private version of the original pointset suitable for various downstream tasks like range queries or median estimation.

Methodology

The proposed pipeline transforms sensitive 2D coordinates into a private 1D representation through several key steps:

  1. Dimensionality Reduction: A Hilbert space-filling curve maps 2D coordinates to a 1D interval [0, 1]. This curve is locality-preserving, ensuring that points close in 2D space generally remain close in the 1D mapping.
  2. Sorting and Grouping: The 1D points are sorted. To mitigate noise impact, points are clustered into groups of size k.
  3. Noise Addition: Laplace noise is added to the sum of each group. The core theoretical insight is that the $L_1$ sensitivity of a sorted sequence is exactly 1, allowing for significantly less noise than naive approaches.
  4. Isotonic Regression: On the client side, the noisy data is denoised using isotonic regression. Because the original data was sorted (non-decreasing), this technique finds the closest non-decreasing sequence to the noisy output, effectively filtering out random perturbations.
  5. Inverse Mapping: The reconstructed 1D points are mapped back to 2D coordinates. A small post-processing 'diffusion' step is applied to preserve visual clusters for visualization or analysis.

Experimental Setup

The method was evaluated using both synthetic and real-world datasets, most notably the Twitter Location Dataset, which contains 183,072 tuples representing user locations in North America.

The Twitter location dataset, showing the spatial distribution of 183,072 points across North America.

Other datasets included Kaluža’s movement tracking data and various synthetic sets designed to test the limits of the noise model and identify regression biases.

Key Results

The study demonstrates that the isotonic regression approach offers several advantages over traditional wavelet or histogram-based methods:

  • High Reconstruction Fidelity: The reconstructed sequence closely matches the original data distribution, as shown in the 1D mapping comparison.
Comparison of the original 1D sequence and the reconstructed sequence after noise addition and isotonic regression.
  • Query Accuracy: The method achieved superior accuracy for range queries compared to standard wavelet-based approaches, largely because it avoids 'bin-alignment' issues where query boundaries do not align with fixed grid cells.
  • Efficient Median Finding: For datasets with high local sensitivity, this method provided more accurate median estimates than specialized smooth-sensitivity algorithms while maintaining $O(n)$ computational efficiency.
  • Density Estimation: The approach outperformed equi-width histograms in estimating probability density functions, showing lower $L_1$ and $L_2$ errors.

Discussion and Limitations

While effective, the method has certain limitations. Isotonic regression introduces a slight bias, particularly at the 'tails' of the distribution (pulling lower values down and higher values up). Additionally, while the Hilbert curve is generally good at preserving locality, it is not perfect; some 2D neighbors may end up far apart in 1D, causing 'smearing' in the final 2D reconstruction.

Future work includes exploring hybrid methods that combine coarse equi-width histograms for sparse regions with the isotonic method for dense areas, as well as applying this technique to non-spatial multidimensional data like census records.

Summary updated

Abstract

We consider the problem of publishing location datasets, in particular 2D spatial pointsets, in a differentially private manner. Many existing mechanisms focus on frequency counts of the points in some a priori partition of the domain that is difficult to determine. We propose an approach that adds noise directly to the point, or to a group of neighboring points. Our approach is based on the observation that, the sensitivity of sorting, as a function on sets of real numbers, can be bounded. Together with isotonic regression, the dataset can be accurately reconstructed. To extend the mechanism to higher dimension, we employ locality preserving function to map the dataset to a bounded interval. Although there are fundamental limits on the performance of locality preserving functions, fortunately, our problem only requires distance preservation in the "easier" direction, and the well-known Hilbert space-filling curve suffices to provide high accuracy. The publishing process is simple from the publisher's point of view: the publisher just needs to map the data, sort them, group them, add Laplace noise and publish the dataset. The only parameter to determine is the group size which can be chosen based on predicted generalization errors. Empirical study shows that the published dataset can also exploited to answer other queries, for example, range query and median query, accurately.
BibTeX
@misc{fang2011publishing,
  author = {Chengfang Fang and Ee-Chien Chang},
  title = {{Publishing Location Dataset Differential Privately with Isotonic Regression}},
  year = {2011},
  eprint = {1111.6677},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1111.6677},
}
Figure