PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentially Private Grids for Geospatial Data

Wahbeh Qardaji, Weining Yang, Ninghui Li

arXiv:1209.1322v1cs.CRcs.DB

TL;DR

The paper addresses how to release accurate differentially private synopses for two-dimensional datasets when partition granularity creates competing noise and non-uniformity errors. It analyzes uniform grids to choose their size and introduces adaptive grids that refine dense regions, with experiments showing consistent gains over existing methods.

  • Problem

    Choosing partition granularity to balance noise error and non-uniformity error is the central challenge in differentially private two-dimensional synopsis methods.

  • Method

    The paper analyzes error dependence on grid size, selects a uniform-grid size, and adaptively subdivides coarse cells according to noisy counts.

  • Results

    Adaptive grids consistently and significantly outperform uniform grids and other state-of-the-art methods, while uniform grids perform as well as and often better than hierarchical methods.

  • Takeaways & Limitations

    Two-dimensional private synopsis accuracy can benefit from choosing granularity explicitly and using finer partitions in dense regions than in sparse regions.

Abstract

from arXiv · show

In this paper, we tackle the problem of constructing a differentially private synopsis for two-dimensional datasets such as geospatial datasets. The current state-of-the-art methods work by performing recursive binary partitioning of the data domains, and constructing a hierarchy of partitions. We show that the key challenge in partition-based synopsis methods lies in choosing the right partition granularity to balance the noise error and the non-uniformity error. We study the uniform-grid approach, which applies an equi-width grid of a certain size over the data domain and then issues independent count queries on the grid cells. This method has received no attention in the literature, probably due to the fact that no good method for choosing a grid size was known. Based on an analysis of the two kinds of errors, we propose a method for choosing the grid size. Experimental results validate our method, and show that this approach performs as well as, and often times better than, the state-of-the-art methods. We further introduce a novel adaptive-grid method. The adaptive grid method lays a coarse-grained grid over the dataset, and then further partitions each cell according to its noisy count. Both levels of partitions are then used in answering queries over the dataset. This method exploits the need to have finer granularity partitioning over dense regions and, at the same time, coarse partitioning over sparse regions. Through extensive experiments on real-world datasets, we show that this approach consistently and significantly outperforms the uniform-grid method and other state-of-the-art methods.

I. INTRODUCTION

The paper studies differentially private synopses for two-dimensional geospatial data, focusing on how partition granularity balances competing errors. It proposes principled uniform-grid sizing and an adaptive grid, with experiments showing strong performance against existing methods.

  • Problem and framework: Differentially private synopses release noisy cell counts to support queries while protecting individual tuples.The framework partitions a two-dimensional domain into cells and publishes their boundaries and noisy counts.
  • Core challenge: Partition granularity must balance noise error against non-uniformity error when answering queries.Noise depends on the number of cells used, while non-uniformity error arises from estimating partially intersected cells.
  • Uniform grid: The uniform-grid method applies an equi-width m × m grid, but its accuracy depends strongly on choosing m appropriately.The paper proposes selecting m based on how the two error sources depend on grid size.
  • Uniform-grid evaluation: 4 real-world datasets validate the proposed method for choosing m, while UG performs as well as and often better than state-of-the-art hierarchical methods.The experiments cover datasets of different sizes and features and report that c = 10 works well across tested settings.
  • Adaptive grid: The adaptive-grid method partitions dense regions more finely and sparse regions more coarsely using noisy counts at two partition levels.Extensive experiments show that it consistently and significantly outperforms uniform grids and other state-of-the-art methods.
  • Privacy foundation: The paper analyzes differential privacy as a worst-case privacy guarantee and accounts for composition through a total privacy budget.Combining mechanisms with budgets ǫ1, · · ·, ǫm yields a total budget equal to their sum.

B. Problem Definition

The synopsis answers rectangular count queries from noisy cell counts, but its partition granularity creates a fundamental trade-off. Finer cells reduce estimation error from non-uniformity while increasing accumulated noise.

  • Query answering: A rectangular count query sums noisy counts for fully covered cells and estimates partially covered cells assuming uniform point distribution.For example, half a cell’s area implies estimating half its points inside the query.
  • Noise error: Independent zero-mean cell noises produce query noise with variance qσ2 and standard deviation √qσ.Here q is the number of cells included in the query and σ is each cell noise’s standard deviation.
  • Noise error: Finer partitions increase noise error because queries include more cells.The noise error grows linearly in √q.
  • Non-uniformity error: Non-uniformity error occurs when partially intersected cells do not distribute points uniformly.Its magnitude depends on the data distribution and the partitioning.
  • Granularity trade-off: Reducing noise and non-uniformity errors imposes conflicting demands on partition granularity.Reconciling these demands is the central challenge of partition-based differentially private synopsis methods.

III. PREVIOUS APPROACHES AND RELATED WORK

Prior work mainly adapts recursive hierarchies, wavelets, or workload-specific mechanisms to private multidimensional release. The paper positions uniform-grid granularity selection as a promising alternative, especially in two dimensions.

  • Recursive partitioning: Most spatial synopsis methods recursively binary-partition the domain, producing deep hierarchical structures such as KD-trees and quadtrees.These methods emphasize how to perform successive partitions.
  • Recursive partitioning: KD-tree methods choose splits using uniformity or noisy medians, while KD-hybrid combines initial quad-tree levels with later KD-tree partitions.KD-hybrid also uses constrained inference and optimized privacy-budget allocation and reportedly outperforms the compared approaches.
  • Recursive partitioning: A general recursive framework balances partitions across dimensions and resembles a KD-tree based on noisy medians in two dimensions.Its balanced partitioning produces regions of similar size.
  • Dimensionality: Hierarchical methods provide limited benefit for two-dimensional datasets, motivating experimental comparison with KD-hybrid.The paper analyzes dimensionality as a factor affecting hierarchy effectiveness.
  • Hierarchical transformations: Wavelet and constrained-inference techniques improve one-dimensional query accuracy but provide only small improvements when applied to two-dimensional uniform grids.These techniques require the leaf cells, so they still depend on selecting an appropriate grid size.
  • Other approaches: Workload-specific matrix mechanisms select strategy queries for known workloads, whereas this paper targets a published synopsis for later queries.Interactive approaches likewise provide access through a privacy-aware database interface rather than a synopsis.

IV. THE ADAPTIVE PARTITIONING APPROACH

The uniform-grid approach addresses the partition-granularity problem by balancing differential-privacy noise against non-uniformity error when selecting grid size. Its guideline makes the grid size depend on dataset size, privacy budget, and a dataset-dependent constant.

  • Uniform Grid partitions the domain into m × m equal-sized cells and obtains a noisy count for each cell.
  • The key design problem is choosing m to minimize the combined noise and non-uniformity errors.Noise grows with the number of cells contributing to a query, while non-uniformity arises when partially intersected cells require uniform-density estimation.
  • Guideline 1 chooses the grid size from N, ǫ, and a dataset-dependent constant c.The supplied equation fragments state that N is the data size, ǫ is the total privacy budget, and c depends on the dataset.
  • Experiments suggest c = 10 works well across datasets of different sizes and privacy-budget choices.
  • The constant c reflects dataset uniformity: larger values suit uniform data, whereas smaller values suit highly non-uniform data.For completely uniform data, the optimal grid is 1×1; highly non-uniform data favors a smaller c.

B. The Adaptive Grids Approach - AG

Adaptive Grids use a coarse first-level partition and refine each cell according to its noisy count, producing finer partitions in dense regions and coarser ones in sparse regions. The two-level synopsis supports query answering through constrained inference and parameter guidelines.

  • Adaptive Grids avoid uniform over-partitioning of sparse regions and under-partitioning of dense regions.Sparse cells otherwise increase noise with little non-uniformity reduction, while dense cells can retain large non-uniformity error.
  • AG first lays an m1 × m1 coarse grid, privately counts its cells, and adaptively chooses each cell’s leaf-grid size from its noisy count N′.The privacy budget is split between first-level and leaf-cell counts using α.
  • Constrained inference combines first-level and leaf-level counts to reduce noise and propagates the adjustment to leaf nodes.The weighted average minimizes the standard deviation of the resulting count, and the difference is distributed among leaf nodes.
  • For queries including more than half of a refined cell’s leaf cells, constrained inference uses the first-level count minus excluded leaf-cell counts.
  • The choice of α is relatively insensitive, with experiments finding similar accuracy for α in [0.2, 0.6] and using α = 0.5.

C. Comparing with Existing Approaches

Compared with recursive hierarchical methods, UG and AG emphasize simple grid granularity, lower implementation cost, and suitability for large datasets. The paper argues that hierarchical benefits are limited in two dimensions and decrease as dimensionality rises.

  • Efficiency: UG and AG are conceptually simple, while UG needs one data scan and AG needs two scans.Their counters can operate on datasets too large to fit into memory.
  • Efficiency: Recursive partitioning methods commonly build deeper trees and require expensive computation to choose partition points.The paper notes that 16 levels is common for 1 million data points.
  • Effect of Dimensionality: In two dimensions, hierarchical methods provide limited benefit because query borders must be answered using leaf nodes.The border region occupies a larger portion of the query as dimensionality increases.
  • Effect of Dimensionality: The paper observes that hierarchical benefits can only decrease with higher dimensionality and conjectures they disappear in dimensions three and above.
  • Design Perspective: The proposed design shifts attention from choosing partition axes or points toward choosing partition granularity.For larger multidimensional subdivisions, the paper presents equi-width partitioning as the feasible differentially private choice.

A. Methodology

The methodology evaluates differentially private synopsis methods on four real-world geospatial datasets, using relative and absolute query error across varied query sizes. It compares grid and hierarchical approaches while examining dataset characteristics and experimental parameters.

  • Experimental Design: The study uses four real datasets and extensive experiments to validate the analysis underlying its parameter-selection guidelines.The experiments are explicitly described as comparing accuracy across methods and validating the parameter analysis.
  • Datasets: Four datasets—road, checkin, landmark, and storage—represent different sizes and spatial distributions, including dense regions, blank areas, and a small-data setting.The road, checkin, landmark, and storage datasets contain approximately 1.6M, 1M sampled, over 870k, and 9,000 points, respectively.
  • Error Metrics: The experiments primarily measure relative error and also include absolute error in final comparisons.Relative error compares the method’s query answer with the correct answer for a range query.
  • Query Workload: Queries use six sizes, with each successive size doubling both dimensions and quadrupling query area, while the largest covers one-quarter to one-half of the domain.For each query size, 200 queries are randomly generated and their errors are computed.
  • Algorithm Parameters: The evaluated methods include adaptive grids with a first-level m1 × m1 grid, noisy cell counts, and further m2 × m2 partitioning controlled by α and c2.Unless otherwise noted, α is set to 0.5.

B. Comparing KD-Tree with UG

The comparison examines KD-based hierarchical methods against uniform grids across query sizes and grid settings, then evaluates whether adding hierarchies improves uniform-grid accuracy. The results emphasize the importance of grid-size selection and show only limited gains from additional hierarchies.

  • KD-Tree versus UG: Relative errors are generally highest for middle-sized queries, with the maximizing query varying across datasets.The maximizing points are q5 for road, q4 for checkin, and q3 for landmark and storage.
  • KD-Tree versus UG: Uniform-grid performance is best across a range of grid sizes, while substantially larger or smaller grids produce steadily increasing error.This behavior indicates that selecting an appropriate grid size is important.
  • KD-Tree versus UG: The predicted best uniform-grid size generally falls within the experimentally optimal range, with two exceptions and reasonable performance near the observed range in the storage and road cases.For road with ǫ = 1, the prediction is 400 versus an observed optimal range of 96–192; for storage with ǫ = 1, it is 30 versus 32–64.
  • KD-Tree versus UG: The best uniform-grid method outperforms KD-hybrid on the road and storage datasets and performs very close to it on the other two datasets.This comparison concerns the experimentally best-performing UG configuration.
  • Effect of Hierarchies: Adding hierarchies to a 360 × 360 uniform grid yields only small accuracy benefits, while Privlet produces clearer improvements in the tested settings.The hierarchy experiments cover checkin and landmark datasets, excluding road as unusual and storage as too small to benefit.

C. Evaluating Adaptive Grids

The adaptive-grid experiments compare parameter settings with uniform-grid and Privlet baselines. Adaptive grids outperform both baselines across query sizes and remain effective over a wider range of first-level grid sizes.

  • Overall Comparison: Adaptive-grid methods outperform uniform-grid and Privlet methods across all tested query sizes.The comparison uses the best-performing grid sizes for the adaptive methods and the best-performing uniform-grid and same-grid Privlet configurations.
  • First-Level Grid Size: The adaptive-grid method is less sensitive than uniform grids to the first-level grid size m1 and performs well over a wider range of m1 values.The m1 suggested by Guideline 2 is either optimal or close to optimal.
  • Parameter Selection: Setting c2 = c/2 = 5 significantly outperforms c2 values of 10 and 15 in the tested parameter groups.The experiments vary α across 0.25, 0.5, and 0.75 while comparing multiple c2 values.

D. Final Comparison

Across relative- and absolute-error evaluations, adaptive-grid methods consistently and significantly outperform the other compared methods. Suggested grid sizes generally preserve strong performance, including on the highly uniform road dataset.

  • AG consistently and significantly outperforms KD-hybrid, UG, and Privlet across four datasets and two privacy settings.The comparison includes both experimentally optimized and suggested grid sizes.
  • UG with suggested sizes provides about the same accuracy as KD-hybrid, while AG with suggested sizes clearly outperforms all non-AG methods.
  • AG methods consistently and significantly outperform the other methods when evaluated using absolute error.Figure 6 uses a logarithmic scale because absolute-error ranges are large.
  • On the highly uniform road dataset, UG with suggested sizes outperforms UG sizes optimized for relative error under absolute-error evaluation.The suggested size differs substantially from the observed relative-error optimum for this dataset.

VI. CONCLUSION

The paper frames partition granularity as the central challenge in private two-dimensional synopsis construction and proposes uniform- and adaptive-grid solutions. Experiments support the methods, while the analysis explains why hierarchies offer limited benefit in two dimensions and predicts weaker performance at higher dimensions.

  • The key challenge is choosing partition granularity to balance noise error and non-uniformity error in private two-dimensional synopses.
  • The paper proposes an error-based grid-size methodology for UG and a novel adaptive-grid method with parameter-selection procedures.
  • Experiments on four real datasets validate the methodology and show that the proposed methods outperform existing approaches.
  • The dimensionality analysis indicates that hierarchical methods provide limited benefit in two dimensions and predicts they perform even worse at higher dimensions.
Loading 1209.1322v1…