mlsanityData to 14 Oct 2026

Dual Query: Practical Private Query Release for High Dimensional Data

arXiv 1402.1526 ↗First posted 6 Feb 2014cs.DS cs.CR cs.DBcited by 26

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 2; 2023: 6; 2024: 9; 2025: 0; 2026: 4.

26 papers.

Sort:

  1. 2023Machine Learning for Synthetic Data Generation: A Reviewcited by 120
  2. 2021Iterative Methods for Private Synthetic Data: Unifying Framework and New Methodscited by 59
  3. 2021Differentially Private Query Release Through Adaptive Projectioncited by 52
  4. 2021Leveraging Public Data for Practical Private Query Releasecited by 39
  5. 2023SoK: Privacy-Preserving Data Synthesiscited by 38
  6. 2022Private Synthetic Data for Multitask Learning and Marginal Queriescited by 35
  7. 2023Generating Private Synthetic Data with Genetic Algorithmscited by 18
  8. 2023Post-processing Private Synthetic Data for Improving Utility on Selected Measurescited by 9
  9. 2024Privacy-preserving data release leveraging optimal transport and particle gradient descentcited by 8
  10. 2024Joint Selection: Adaptively Incorporating Public Information for Private Synthetic Datacited by 8
  11. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7
  12. 2021Relaxed Marginal Consistency for Differentially Private Query Answeringcited by 6
14 more
  1. 2024Oracle-Efficient Differentially Private Learning with Public Datacited by 6
  2. 2024Tabular Data Synthesis with Differential Privacy: A Surveycited by 6
  3. 2024Private Regression via Data-Dependent Sufficient Statistic Perturbationcited by 4
  4. 2021Rejoinder: Gaussian Differential Privacycited by 2
  5. 2022Private Synthetic Data with Hierarchical Structurecited by 2
  6. 2023ResidualPlanner+: a scalable matrix mechanism for marginals and beyondcited by 2
  7. 2024Differentially Private Synthetic Data Generation for Relational Databasescited by 2
  8. 2024Privacy without Noisy Gradients: Slicing Mechanism for Generative Model Trainingcited by 2
  9. 2026Privately Learning Decision Lists and a Differentially Private Winnowcited by 1
  10. 2026Accurate and Scalable Matrix Mechanisms via Divide and Conquercited by 1
  11. 2023Partition-based differentially private synthetic data generationcited by 0
  12. 2024Differentially Private Synthetic High-dimensional Tabular Streamcited by 0
  13. 2026PATE-TabTransGAN: Differentially Private Synthetic Tabular Data Generation via Transformer-Based Student Discriminationcited by 0
  14. 2026Fixed-Parameter Tractability of Private Synthetic Data Generationcited by 0