Differentially Private Synthetic Data Using KD-Trees
Eleonora Kreačić Navid Nouri Vamsi K. Potluru Tucker Balch Manuela Veloso
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 $\epsilon$-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.