# Differentially Private Synthetic Data Using KD-Trees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 31 references that are in the map.
- First posted on arXiv 19 Jun 2023.

## Builds on (most cited first, 14 of 14)

- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Differentially Private Generative Adversarial Network](https://mlsanity.com/paper/1802.06739/) (2018)
- [Data Synthesis based on Generative Adversarial Networks](https://mlsanity.com/paper/1806.03384/) (2018)
- [DP-CGAN: Differentially Private Synthetic Data and Label Generation](https://mlsanity.com/paper/2001.09700/) (2020)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [DP-MERF: Differentially Private Mean Embeddings with Random Features for Practical Privacy-Preserving Data Generation](https://mlsanity.com/paper/2002.11603/) (2020)
- [Synthetic Data -- what, why and how?](https://mlsanity.com/paper/2205.03257/) (2022)
- [Differentially Private Generative Adversarial Networks for Time Series, Continuous, and Discrete Open Data](https://mlsanity.com/paper/1901.02477/) (2019)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions](https://mlsanity.com/paper/1601.03229/) (2016)
- [Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation](https://mlsanity.com/paper/1305.6000/) (2013)
- [Differentially Private Database Release via Kernel Mean Embeddings](https://mlsanity.com/paper/1710.01641/) (2017)
- [Closed-form Expressions for Maximum Mean Discrepancy with Applications to Wasserstein Auto-Encoders](https://mlsanity.com/paper/1901.03227/) (2019)

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

- [Six Levels of Privacy: A Framework for Financial Synthetic Data](https://mlsanity.com/paper/2403.14724/) (2024)

## Abstract (arXiv)

Creation of a synthetic dataset that faithfully represents the data distribution and simultaneously preserves privacy is a major research challenge. Many space partitioning based approaches have emerged in recent years for answering statistical queries in a differentially private manner. However, for synthetic data generation problem, recent research has been mainly focused on deep generative models. In contrast, we exploit space partitioning techniques together with noise perturbation and thus achieve intuitive and transparent algorithms. We propose both data independent and data dependent algorithms for ε-differentially private synthetic data generation whose kernel density resembles that of the real dataset. Additionally, we provide theoretical results on the utility-privacy trade-offs and show how our data dependent approach overcomes the curse of dimensionality and leads to a scalable algorithm. We show empirical utility improvements over the prior work, and discuss performance of our algorithm on a downstream classification task on a real dataset.