# PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2016.

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

- [SoK: Privacy-Preserving Data Synthesis](https://mlsanity.com/paper/2307.02106/) (2023)
- [OCT-GAN: Neural ODE-based Conditional Tabular GANs](https://mlsanity.com/paper/2105.14969/) (2021)
- [Invertible Tabular GANs: Killing Two Birds with OneStone for Tabular Data Synthesis](https://mlsanity.com/paper/2202.03636/) (2022)
- [Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation](https://mlsanity.com/paper/2111.02356/) (2021)
- [Noise-Aware Statistical Inference with Differentially Private Synthetic Data](https://mlsanity.com/paper/2205.14485/) (2022)
- [On the Utility Recovery Incapability of Neural Net-based Differential Private Tabular Training Data Synthesizer under Privacy Deregulation](https://mlsanity.com/paper/2211.15809/) (2022)
- [Privacy-preserving data release leveraging optimal transport and particle gradient descent](https://mlsanity.com/paper/2401.17823/) (2024)
- [The Importance of Being Discrete: Measuring the Impact of Discretization in End-to-End Differentially Private Synthetic Data](https://mlsanity.com/paper/2504.06923/) (2025)
- [The Hitchhiker's Guide to Efficient, End-to-End, and Tight DP Auditing](https://mlsanity.com/paper/2506.16666/) (2025)
- [Algorithms with More Granular Differential Privacy Guarantees](https://mlsanity.com/paper/2209.04053/) (2022)
- [dpmm: Differentially Private Marginal Models, a Library for Synthetic Tabular Data Generation](https://mlsanity.com/paper/2506.00322/) (2025)
- [Two Views of Constrained Differential Privacy: Belief Revision and Update](https://mlsanity.com/paper/2303.00228/) (2023)
- [An Algorithm for Streaming Differentially Private Data](https://mlsanity.com/paper/2401.14577/) (2024)
- [HRNet: Differentially Private Hierarchical and Multi-Resolution Network for Human Mobility Data Synthesization](https://mlsanity.com/paper/2405.08043/) (2024)
- [Differentially Private Synthetic Data via APIs 4: Tabular Data](https://mlsanity.com/paper/2606.08259/) (2026)
- [Differentially Private Synthetic Data Using KD-Trees](https://mlsanity.com/paper/2306.13211/) (2023)
- [DPM: Clustering Sensitive Data through Separation](https://mlsanity.com/paper/2307.02969/) (2023)
- [Differentially Private Linear Regression and Synthetic Data Generation with Statistical Guarantees](https://mlsanity.com/paper/2510.16974/) (2025)
- [Understanding the Impact of Data Domain Extraction on Synthetic Data Privacy](https://mlsanity.com/paper/2504.08254/) (2025)
- [Beyond One-Size-Fits-All: Neural Networks for Differentially Private Tabular Data Synthesis](https://mlsanity.com/paper/2511.13893/) (2025)
- [SLDP: Semi-Local Differential Privacy for Density-Adaptive Analytics](https://mlsanity.com/paper/2602.18910/) (2026)
- [DPrivBench: Benchmarking LLMs' Reasoning for Differential Privacy](https://mlsanity.com/paper/2604.15851/) (2026)

## Abstract (arXiv)

Given a set D of tuples defined on a domain Omega, we study differentially private algorithms for constructing a histogram over Omega to approximate the tuple distribution in D. Existing solutions for the problem mostly adopt a hierarchical decomposition approach, which recursively splits Omega into sub-domains and computes a noisy tuple count for each sub-domain, until all noisy counts are below a certain threshold. This approach, however, requires that we (i) impose a limit h on the recursion depth in the splitting of Omega and (ii) set the noise in each count to be proportional to h. This leads to inferior data utility due to the following dilemma: if we use a small h, then the resulting histogram would be too coarse-grained to provide an accurate approximation of data distribution; meanwhile, a large h would yield a fine-grained histogram, but its quality would be severely degraded by the increased amount of noise in the tuple counts. To remedy the deficiency of existing solutions, we present PrivTree, a histogram construction algorithm that also applies hierarchical decomposition but features a crucial (and somewhat surprising) improvement: when deciding whether or not to split a sub-domain, the amount of noise required in the corresponding tuple count is independent of the recursive depth. This enables PrivTree to adaptively generate high-quality histograms without even asking for a pre-defined threshold on the depth of sub-domain splitting. As concrete examples, we demonstrate an application of PrivTree in modelling spatial data, and show that it can also be extended to handle sequence data (where the decision in sub-domain splitting is not based on tuple counts but a more sophisticated measure). Our experiments on a variety of real datasets show that PrivTree significantly outperforms the states of the art in terms of data utility.