Source-linked AI summary
Differentially Private Spatial Decompositions
Graham Cormode, Magda Procopiuc, Entong Shen, Divesh Srivastava, Ting Yu
TL;DR
Spatial data and other tree-indexable data need private releases that remain useful rather than becoming masses of noisy counts. The paper introduces private spatial decompositions, combines private structure construction with geometric noise allocation and post-processing, and reports query-error reductions of up to an order of magnitude. These techniques provide a general framework for privately representing spatial data and answering queries accurately.
Problem
Existing differential privacy methods provide count-based releases, but directly applying them to spatial data can produce mostly noisy counts with poor query utility.
Method
The paper adapts quadtrees, kd-trees, and R-trees into private spatial decompositions, using private structural choices, non-uniform noise allocation, and post-processing of noisy counts.
Results
Up to an order of magnitude lower absolute query error is achieved by the two novel techniques across experiments on real and synthetic data.
Takeaways & Limitations
Private spatial decompositions can provide a practical framework for privately representing spatial data and answering diverse queries with improved accuracy.
Takeaways & Limitations
Sampling is not useful for noisy counts because it has linear-time cost like exact counting while introducing more inaccuracy.
Abstract
from arXiv · showhide
Differential privacy has recently emerged as the de facto standard for private data release. This makes it possible to provide strong theoretical guarantees on the privacy and utility of released data. While it is well-known how to release data based on counts and simple functions under this guarantee, it remains to provide general purpose techniques to release different kinds of data. In this paper, we focus on spatial data such as locations and more generally any data that can be indexed by a tree structure. Directly applying existing differential privacy methods to this type of data simply generates noise. Instead, we introduce a new class of "private spatial decompositions": these adapt standard spatial indexing methods such as quadtrees and kd-trees to provide a private description of the data distribution. Equipping such structures with differential privacy requires several steps to ensure that they provide meaningful privacy guarantees. Various primitives, such as choosing splitting points and describing the distribution of points within a region, must be done privately, and the guarantees of the different building blocks composed to provide an overall guarantee. Consequently, we expose the design space for private spatial decompositions, and analyze some key examples. Our experimental study demonstrates that it is possible to build such decompositions efficiently, and use them to answer a variety of queries privately with high accuracy.
1 Introduction
The paper addresses how to release spatial and tree-indexable data with differential privacy without reducing the output to mostly uninformative noise. It introduces private spatial decompositions and techniques that improve query accuracy while preserving privacy.
- Motivation: Fine-grid releases can produce mostly 0-or-1 noisy counts, causing huge errors for queries covering many cells.A query covering 1% of the area may include over 10^9 noisy counts.
- Approach: Private spatial decompositions partition space into regions, report private statistics within them, and answer queries by intersecting query regions with the decomposition.Compact regions containing sufficiently many points and having more uniform distributions are expected to improve accuracy.
- Challenges: Data-dependent structures require private region descriptions as well as noisy counts, so building an exact tree and merely perturbing its counts is insufficient.This issue arises for structures such as kd-trees whose splits depend on the data.
- Techniques: Non-uniform noise parameters can improve accuracy under the same privacy guarantee by increasing geometrically from root to leaves.The paper presents this as a first analysis of non-uniform noise parameters in this setting.
- Techniques: Post-processing noisy counts computes minimum-variance query answers over a broad class of non-uniform noise parameters.The method generalizes earlier post-processing limited to uniform noise.
- Results: The framework privately builds kd-trees, R-trees, and quadtrees in multiple dimensions, while experiments evaluate design choices on real and synthetic data.The two novel techniques reduce query absolute error by up to an order of magnitude.
2 Related Work
Prior privacy work developed formal guarantees and mechanisms for releasing statistics, but comparatively little work directly addressed spatial data. Existing spatial approaches relied on grids or approximate private partitioning methods with limited accuracy.
- Privacy foundations: Differential privacy replaced earlier syntactic privacy definitions with a semantic guarantee about output distributions when an individual is present or absent.The guarantee limits how much an individual tuple can affect released information.
- Private release: Non-interactive differential privacy releases selected statistics through mechanisms such as noisy tables, histograms, and other count-based representations.Prior work studied accuracy for different released statistics.
- Private mechanisms: General mechanisms including the exponential, geometric, and smoothed-sensitivity approaches were applied to tables, time series, and recommender systems.These methods adapt privacy-preserving noise or selection to different query settings.
- Spatial privacy: Spatial data received limited direct attention, with prior private kd-tree work using an approximate mean as a surrogate for the median.The paper treats that approach as a special case and reports better private median-selection methods.
- Spatial privacy: The other directly spatial approach imposed a fixed-resolution grid, built a kd-tree from noisy grid counts, and was observed to be inferior to other framework methods.Its procedure split nodes judged non-uniform and populated final leaves with fresh noisy counts.
3 Preliminaries
The preliminaries define differential privacy, spatial decompositions, and the main data-independent, data-dependent, and hybrid tree families. They then explain how private counts and composition produce private spatial decompositions.
- Differential privacy: The paper defines neighboring datasets as differing by one tuple, using presence or absence of that tuple as its concrete convention.The alternative interpretation changes guarantees by at most a constant factor.
- Differential privacy: Differential privacy requires the output distribution to remain nearly unchanged whether an individual tuple is present or absent.The paper introduces randomized algorithms over datasets and arbitrary output sets.
- Differential privacy: The Laplace mechanism releases a numeric function plus noise scaled by its sensitivity and privacy parameter.For a count, sensitivity is 1 because neighboring dataset cardinalities differ by one.
- Spatial decompositions: Spatial decompositions hierarchically partition geometric space into smaller areas, assigning data points to leaves in a generally complete tree.Spatial indexes support efficient aggregate, especially range, queries.
- Tree families: Data-independent quadtrees use domain-based equal splits, while data-dependent kd-trees and Hilbert R-trees adapt their partitions to the input.Hybrid trees use data-dependent splits for an initial number of levels and data-independent splits afterward.
- Building PSDs: A simple private spatial decomposition releases noisy counts for a data-independent tree, while data-dependent and hybrid structures must also perturb their structures.Privacy accounting composes private counts along root-to-leaf paths; off-path counts do not affect one another's guarantees.
4 Allocating Noise Parameters
The paper allocates a fixed privacy budget across tree levels and processes queries by combining noisy node counts. Geometric budgeting and post-processing target the variance and representation choices that determine query error.
- Budget allocation: A budget strategy assigns level-specific parameters ε_i whose sum along a tree path equals the total privacy budget ε.The objective is to minimize query errors.
- Error and processing: The query error measure is the variance of the unbiased private answer, and under standard processing it equals the sum of variances of contributing noisy counts.Thus, error approximately increases with the number of included noisy counts.
- Query processing: Standard range-query processing recursively intersects query regions with tree nodes, using fully contained noisy counts and uniformity estimates for partially intersected leaves.The number of contributing nodes is n(Q)=∑_i n_i.
- Query processing: For two-dimensional trees, boundary intersections grow by at most a factor of the fanout every two levels, yielding bounds on the number of contributing nodes.The proof applies the boundary argument to all four query extents.
- Budget strategies: Geometric budgeting increases ε_i toward the leaves, where counts receive the highest accuracy, and its worst-case error grows more slowly than uniform budgeting.The comparison uses Err_unif(h) and Err_geom(h) for queries touching the maximum number of counts at each level.
- Budget strategies: Budget can also be concentrated at leaves, withheld from selected levels, or assigned unevenly across nodes when the query workload is known in advance.Any node-specific allocation must preserve the total budget along every path.
5 Optimizing Query Accuracy
The section improves query accuracy by post-processing noisy hierarchical counts and allocating noise non-uniformly. Ordinary least squares produces consistent, minimum-error query estimates and can be computed in linear time.
- Post-processing example: In a four-child example with uniform noise, weighting the root and leaf sums 4/5 and 1/5 reduces root variance to 4/5 of the direct estimate.Equal averaging instead produces variance 5/4 times the direct root estimate, whereas the OLS weighting improves accuracy.
- Generalization: The framework supports level-dependent noise parameters, including uniform and geometric budgeting, while retaining the same linear-time solution.The generalization applies when all nodes at level i share Laplace parameter ε_i.
- Post-processing: Post-processing converts noisy counts into consistent estimates that minimize query error without changing the privacy guarantee.The method takes the differentially private output as input, so it preserves privacy while minimizing variance.
- Post-processing: The ordinary least squares estimator is unbiased and has smaller error than the original noisy counts for every range query.Among unbiased linear estimators derived from the noisy counts, OLS achieves minimum error for all range queries.
- Efficient computation: A linear-time algorithm computes the OLS estimator by exploiting the tree structure instead of explicitly solving large linear systems.The algorithm uses three tree traversals after pre-computing an array of height h + 1 entries.
- Evaluation: Experiments support the theoretical result and show significant query-accuracy improvement from OLS.The evaluation appears in Section 8.2.
6 Data-Dependent and Hybrid Trees
Data-dependent and hybrid trees must privatize both their counts and their structure, especially the split locations. The section compares private median methods and combines data-dependent splitting with privacy-aware budgeting strategies.
- Private splits: Data-dependent trees require private split locations because releasing exact medians can reveal private information.A tuple can affect true medians at nodes outside its root-to-leaf path, complicating composition.
- Private median methods: The paper compares private-median approaches and analyzes their behavior, including smooth sensitivity, the exponential mechanism, cell-based medians, and noisy means.The comparison is empirical and includes methods developed in prior work as well as new analysis.
- Private median methods: Under the 80/20 data-dispersion condition, smooth sensitivity and the exponential mechanism have constant probability of selecting a split leaving a constant fraction of points on each side.Smooth sensitivity additionally requires n to be sufficiently large.
- Privacy budgeting: Median and count privacy budgets are allocated separately because their noise affects tree accuracy differently.Count noise increases uncertainty in touched regions, whereas median noise changes the regions themselves.
- Tree design: Flattening a 2D kd-tree skips every other level so it can be compared with a quadtree using the same fanout of 4.The motivation is that an ordinary kd-tree has twice the height, dividing the privacy budget across twice as many levels.
7 Further Enhancements
Sampling accelerates private computation, while pruning avoids noisy subdivision of sparse regions. Sampling provides a formal privacy amplification result but is not useful for noisy counts because it adds inaccuracy without reducing asymptotic computation time.
- Sampling: Sampling an ε-differentially private algorithm at rate p yields 2pe^ε-differential privacy.This extends an earlier privacy-amplification result for subsampling.
- Sampling: Sampling makes private-median methods an order of magnitude faster, marginally worsens exponential-mechanism accuracy, and improves smooth-sensitivity accuracy.The paper applies sampling to smooth sensitivity and exponential-mechanism medians for data-dependent and hybrid trees.
- Sampling: Sampling is not useful for noisy counts because exact counting and independently sampled counting both require linear time, while sampling adds inaccuracy.The cell-based median method is likewise implemented without sampling.
- Pruning: Pruning cuts off sparse or empty branches because further subdivision can accumulate descendant-count noise for intersecting queries.The stopping decision cannot be based on the true private count.
8 Experimental Study
Experiments evaluate private spatial decompositions across median selection, query accuracy, efficiency, and record matching. Geometric budgeting and post-processing improve accuracy, while optimized quadtrees and hybrid kd-trees show strong query performance across settings.
- Budget and post-processing: Geometric budgeting and post-processing each improve quadtree query accuracy, reducing relative error by up to an order of magnitude together.The combined optimization performs especially well when ε = 0.1, so subsequent PSD results use both techniques.
- Quality of private medians: The exponential mechanism is the most accurate private-median method, while sampling makes median computation about an order of magnitude faster.Sampling improves smooth sensitivity accuracy but produces a speed-oriented trade-off for the exponential mechanism; the latter becomes the default method.
- Comparison of kd-trees: Noise in private splitting medians affects kd-tree query accuracy more than noisy counts, with kd-true remaining below 1% relative error.Poor splitting points create unevenly populated leaves, explaining the weak performance of the noisy-mean kd-tree.
- Comparison of kd-trees: All kd-tree variants achieve small relative errors below 10% even at ε = 0.1, with kd-hybrid the most reliably accurate overall.Kd-cell performs best on small square queries, but loses its advantage as query area grows.
- Comparison of PSDs: Across representative PSDs, the optimized quadtree has the best accuracy at depth 10, while the hybrid kd-tree matches it for larger queries at lower depth.Cell-based kd-trees perform well for small square queries but worst for larger queries; Hilbert R-trees are accurate on some queries and much worse on others.
- Scalability: PSD construction is generally not a bottleneck, with domain-only structures fastest, hybrid kd-trees taking around a minute, and cell-based and Hilbert structures slower.The experiments treat construction as typically a one-time cost.
9 Concluding Remarks
The paper presents a comprehensive framework for private spatial decompositions, combining private versions of established spatial structures with techniques that improve query accuracy. Experiments support the framework’s efficiency and accuracy under strong differential privacy.
- The framework produces differentially private versions of quadtrees, kd-trees, and Hilbert R-trees.
- Non-uniform hierarchical noise parameters are designed to minimize query error.
- Post-processing recomputes node counts from initial noisy counts to optimize query accuracy.The authors state that this technique applies to a large class of other privacy settings.
- The paper surveys private-median techniques, derives theoretical results for two accurate methods, and combines these with sampling and other techniques under one privacy guarantee.
- For most PSDs, relative query errors are in single-digit percentages while strong differential privacy is guaranteed.The experiments also report significant improvements in query accuracy, running time, or both from the proposed techniques.