Differentially Private Spatial Decompositions

By Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, Entong Shen, Ting Yu. 2011

427 citations recorded by the source corpus.

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-understood how to release data based on counts and simple functions under this guarantee, it remains to provide general purpose techniques to release data that is useful for a variety of queries. In this paper, we focus on spatial data such as locations and more generally any multi-dimensional data that can be indexed by a tree structure. Directly applying existing differential privacy methods to this type of data simply generates noise. We propose instead the class of "private spatial decompositions'': these adapt standard spatial indexing methods such as quad trees 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 basic steps, 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. A major contribution of our work is to provide new techniques for parameter setting and post-processing the output to improve the accuracy of query answers. 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Functional Mechanism: Regression Analysis under Differential Privacy (2012, background): “In particular, Hay et al. [13], Li et al. [17], Xiao et al. [30], and Cormode et al. [6] present methods for minimizing the worst-case error of a given set of count queries; Barak et al. [2] and Ding et al. [8] consider the publication of data cubes; Xu et al. [31] and Li et al. [18] focus on…”
Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers (2019, neutral): “Interesting work has been done in both theCDPmodel [8, 22, 30, 33, 34, 39, 54– 56, 58, 70, 71, 75, 85, 89, 90, 100–102, 104, 105, 107] and the LDP model [13, 32, 42, 44, 91, 95–97, 108].”
Modeling Tabular data using Conditional GAN (2019, methodology): “Spatial data could be modeled with a spatial decomposition tree [8, 27].”
Differential Privacy Techniques for Cyber Physical Systems: A Survey (2018, background): “Similarly, the branch of differential privacy in perspective of dataset is also divided into two major subcategories: ( i ) Synopsis of Original Databases and Datasets [67]–[78].”
Differentially Private K-Means Clustering (2015, methodology): “Most non-interactive approaches aim at developing solutions to answer histogram or range queries accurately [10, 33, 14, 6].”
A Framework for Protecting Worker Location Privacy in Spatial Crowdsourcing (2014, methodology): “The budget is best distributed across levels according to the geometric allocation [4], where leaf nodes receive more budget than higher levels.”
Differentially Private Hierarchical Count-of-Counts Histograms (2018, background): “Other, more ﬂexible, partitioning of the data have also been studied (e.g., [34, 12, 32]).”
Optimizing error of high-dimensional statistical queries under differential privacy (2018, background): “We find that, depending on the workload and domain size, the second best error rate is achieved by a broad set of algorithms: Identity, HB, Quadtree, GreedyH are all second-best performers for some workload.”
Correlated network data publication via differential privacy (2013, methodology): “Instead, we use a standard quadtree with the geometric budget scheme [9] to derive a reasonably good estimate.”
The Staircase Mechanism in Differential Privacy (2015, background): “McSherry and Talwar [47] introduce the exponential mechanism which is a generic differentially private mechanism and can apply to general abstract settings.”
PrivBayes: private data release via bayesian networks (2014, background): “Since its proposal, there have been many efforts to develop mechanisms and processes for data release for different kinds of input database, and for different objectives for the end use.”
Blowfish privacy: tuning privacy-utility trade-offs using policies (2013, methodology): “Prior work has considered distributing the ✏ uniformly or geometrically [5].”
The Optimal Noise-Adding Mechanism in Differential Privacy (2012, neutral): “, [5], [11]–[47].”
The matrix mechanism: optimizing linear counting queries under differential privacy (2015, neutral): “Practical algorithms are presented to answer linear queries on 1dimensional databases [1,30] and 2-dimensional databases [4,29], respectively.”
Principled Evaluation of Differentially Private Algorithms using DPBench (2015, methodology): “While most algorithms are explicitly compared to a baseline like IDENTITY ( [4] is an exception), none of algorithms have been compared with a data-dependent baseline like UNIFORM.”
A Data- and Workload-Aware Query Answering Algorithm for Range Queries Under Differential Privacy (2014, methodology): “To support range queries, several mechanisms employ a hierarchical strategy [6, 13, 20].”
Application of Local Differential Privacy to Collection of Indoor Positioning Data (2018, background): “Private Spatial Decomposition (PSD) releases differentially private spatial histograms which are generated by partitioning a spatial domain into several regions and adding carefully designed random noises to the number of objects belonging to each region in a DP-compliant manner [3], [28], [33].”
Private spatial data aggregation in the local setting (2016, methodology): “Speciﬁcally, they adapt the approaches in [9], [10] to meet the speciﬁc requirements of the spatial crowdsourcing framework.”