# Frequency Estimation under Local Differential Privacy [Experiments, Analysis and Benchmarks]

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2021.

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

- [Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming](https://mlsanity.com/paper/2104.01808/) (2021)
- [Locally Differentially Private Bayesian Inference](https://mlsanity.com/paper/2110.14426/) (2021)
- [Consistent Estimation of Numerical Distributions under Local Differential Privacy by Wavelet Expansion](https://mlsanity.com/paper/2509.19661/) (2025)
- [Near-optimal algorithms for private estimation and sequential testing of collision probability](https://mlsanity.com/paper/2504.13804/) (2025)

## Abstract (arXiv)

Private collection of statistics from a large distributed population is an important problem, and has led to large scale deployments from several leading technology companies. The dominant approach requires each user to randomly perturb their input, leading to guarantees in the local differential privacy model. In this paper, we place the various approaches that have been suggested into a common framework, and perform an extensive series of experiments to understand the tradeoffs between different implementation choices. Our conclusion is that for the core problems of frequency estimation and heavy hitter identification, careful choice of algorithms can lead to very effective solutions that scale to millions of users