Optimizing error of high-dimensional statistical queries under differential privacy

Abstract

Differentially private algorithms for answering sets of predicate counting queries on a sensitive database have many applications. Organizations that collect individual-level data, such as statistical agencies and medical institutions, use them to safely release summary tabulations. However, existing techniques are accurate only on a narrow class of query workloads, or are extremely slow, especially when analyzing more than one or two dimensions of the data. In this work we propose HDMM, a new differentially private algorithm for answering a workload of predicate counting queries, that is especially effective for higher-dimensional datasets. HDMM represents query workloads using an implicit matrix representation and exploits this compact representation to efficiently search (a subset of) the space of differentially private algorithms for one that answers the input query workload with high accuracy. We empirically show that HDMM can efficiently answer queries with lower error than state-of-the-art techniques on a variety of low and high dimensional datasets.

References in corpus (4)

• The Geometry of Differential Privacy: the Sparse and Approximate Cases
• DPCube: Differentially Private Histogram Release through Multidimensional Partitioning
• PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions
• Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy

Cited by in corpus (22)

• An Economic Analysis of Privacy Protection and Statistical Accuracy as Social Choices
• Chorus: a Programming Framework for Building Scalable Differential Privacy Mechanisms
• Leveraging Public Data for Practical Private Query Release
• Randomness Concerns When Deploying Differential Privacy
• Differentially Private Query Release Through Adaptive Projection
• Capacity Bounded Differential Privacy
• HDPView: Differentially Private Materialized View for Exploring High Dimensional Relational Data
• DP-Cryptography: Marrying Differential Privacy and Cryptography in Emerging Applications
• Budget Sharing for Multi-Analyst Differential Privacy
• Benchmarking Differentially Private Tabular Data Synthesis
• Turbo: Effective Caching in Differentially-Private Databases
• Optimizing Fitness-For-Use of Differentially Private Linear Queries
• Relaxed Marginal Consistency for Differentially Private Query Answering
• AHEAD: Adaptive Hierarchical Decomposition for Range Query under Local Differential Privacy
• HTF: Homogeneous Tree Framework for Differentially-Private Release of Location Data
• Prior-Aware Distribution Estimation for Differential Privacy
• Answering Multi-Dimensional Range Queries under Local Differential Privacy
• Online Differentially Private Synthetic Data Generation
• Designing Differentially Private Estimators in High Dimensions
• Answering Summation Queries for Numerical Attributes under Differential Privacy
• Adjusting Queries to Statistical Procedures Under Differential Privacy
• Construction of Differentially Private Summaries over Fully Homomorphic Encryption