# Dual Query: Practical Private Query Release for High Dimensional Data

arXiv: https://arxiv.org/abs/1402.1526 · HTML: https://mlsanity.com/paper/1402.1526/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2014.

## Built on by (most cited first, 26 of 26)

- [Machine Learning for Synthetic Data Generation: A Review](https://mlsanity.com/paper/2302.04062/) (2023)
- [Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods](https://mlsanity.com/paper/2106.07153/) (2021)
- [Differentially Private Query Release Through Adaptive Projection](https://mlsanity.com/paper/2103.06641/) (2021)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [SoK: Privacy-Preserving Data Synthesis](https://mlsanity.com/paper/2307.02106/) (2023)
- [Private Synthetic Data for Multitask Learning and Marginal Queries](https://mlsanity.com/paper/2209.07400/) (2022)
- [Generating Private Synthetic Data with Genetic Algorithms](https://mlsanity.com/paper/2306.03257/) (2023)
- [Post-processing Private Synthetic Data for Improving Utility on Selected Measures](https://mlsanity.com/paper/2305.15538/) (2023)
- [Privacy-preserving data release leveraging optimal transport and particle gradient descent](https://mlsanity.com/paper/2401.17823/) (2024)
- [Joint Selection: Adaptively Incorporating Public Information for Private Synthetic Data](https://mlsanity.com/paper/2403.07797/) (2024)
- [Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems](https://mlsanity.com/paper/2403.02912/) (2024)
- [Relaxed Marginal Consistency for Differentially Private Query Answering](https://mlsanity.com/paper/2109.06153/) (2021)
- [Oracle-Efficient Differentially Private Learning with Public Data](https://mlsanity.com/paper/2402.09483/) (2024)
- [Tabular Data Synthesis with Differential Privacy: A Survey](https://mlsanity.com/paper/2411.03351/) (2024)
- [Private Regression via Data-Dependent Sufficient Statistic Perturbation](https://mlsanity.com/paper/2405.15002/) (2024)
- [Rejoinder: Gaussian Differential Privacy](https://mlsanity.com/paper/2104.01987/) (2021)
- [Private Synthetic Data with Hierarchical Structure](https://mlsanity.com/paper/2206.05942/) (2022)
- [ResidualPlanner+: a scalable matrix mechanism for marginals and beyond](https://mlsanity.com/paper/2305.08175/) (2023)
- [Differentially Private Synthetic Data Generation for Relational Databases](https://mlsanity.com/paper/2405.18670/) (2024)
- [Privacy without Noisy Gradients: Slicing Mechanism for Generative Model Training](https://mlsanity.com/paper/2410.19941/) (2024)
- [Privately Learning Decision Lists and a Differentially Private Winnow](https://mlsanity.com/paper/2602.07370/) (2026)
- [Accurate and Scalable Matrix Mechanisms via Divide and Conquer](https://mlsanity.com/paper/2604.00868/) (2026)
- [Partition-based differentially private synthetic data generation](https://mlsanity.com/paper/2310.06371/) (2023)
- [Differentially Private Synthetic High-dimensional Tabular Stream](https://mlsanity.com/paper/2409.00322/) (2024)
- [PATE-TabTransGAN: Differentially Private Synthetic Tabular Data Generation via Transformer-Based Student Discrimination](https://mlsanity.com/paper/2605.26802/) (2026)
- [Fixed-Parameter Tractability of Private Synthetic Data Generation](https://mlsanity.com/paper/2606.11283/) (2026)

## Abstract (arXiv)

We present a practical, differentially private algorithm for answering a large number of queries on high dimensional datasets. Like all algorithms for this task, ours necessarily has worst-case complexity exponential in the dimension of the data. However, our algorithm packages the computationally hard step into a concisely defined integer program, which can be solved non-privately using standard solvers. We prove accuracy and privacy theorems for our algorithm, and then demonstrate experimentally that our algorithm performs well in practice. For example, our algorithm can efficiently and accurately answer millions of queries on the Netflix dataset, which has over 17,000 attributes; this is an improvement on the state of the art by multiple orders of magnitude.