# Differentially private anonymized histograms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2019.

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

- [Algorithms for bounding contribution for histogram estimation under user-level privacy](https://mlsanity.com/paper/2206.03008/) (2022)
- [Anonymized Histograms in Intermediate Privacy Models](https://mlsanity.com/paper/2210.15178/) (2022)

## Abstract (arXiv)

For a dataset of label-count pairs, an anonymized histogram is the multiset of counts. Anonymized histograms appear in various potentially sensitive contexts such as password-frequency lists, degree distribution in social networks, and estimation of symmetric properties of discrete distributions. Motivated by these applications, we propose the first differentially private mechanism to release anonymized histograms that achieves near-optimal privacy utility trade-off both in terms of number of items and the privacy parameter. Further, if the underlying histogram is given in a compact format, the proposed algorithm runs in time sub-linear in the number of items. For anonymized histograms generated from unknown discrete distributions, we show that the released histogram can be directly used for estimating symmetric properties of the underlying distribution.