# Practical Locally Private Heavy Hitters

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jul 2017.

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

- [Harnessing large-language models to generate private synthetic text](https://mlsanity.com/paper/2306.01684/) (2023)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation](https://mlsanity.com/paper/2111.02356/) (2021)
- [User-Level Private Learning via Correlated Sampling](https://mlsanity.com/paper/2110.11208/) (2021)
- [Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy](https://mlsanity.com/paper/2202.10209/) (2022)
- [Private Frequency Estimation via Projective Geometry](https://mlsanity.com/paper/2203.00194/) (2022)
- [Federated Analytics: A survey](https://mlsanity.com/paper/2302.01326/) (2023)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming](https://mlsanity.com/paper/2104.01808/) (2021)
- [Group privacy for personalized federated learning](https://mlsanity.com/paper/2206.03396/) (2022)
- [Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints](https://mlsanity.com/paper/2106.08597/) (2021)
- [Training a Tokenizer for Free with Private Federated Learning](https://mlsanity.com/paper/2203.09943/) (2022)
- [Advancing Personalized Federated Learning: Group Privacy, Fairness, and Beyond](https://mlsanity.com/paper/2309.00416/) (2023)
- [Privacy-Preserving Conformal Prediction Under Local Differential Privacy](https://mlsanity.com/paper/2505.15721/) (2025)
- [Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error](https://mlsanity.com/paper/2105.15007/) (2021)
- [Differentially Private Algorithms for Clustering with Stability Assumptions](https://mlsanity.com/paper/2106.12959/) (2021)
- [Locally Differentially Private Bayesian Inference](https://mlsanity.com/paper/2110.14426/) (2021)
- [Training generative models from privatized data](https://mlsanity.com/paper/2306.09547/) (2023)
- [Better Locally Private Sparse Estimation Given Multiple Samples Per User](https://mlsanity.com/paper/2408.04313/) (2024)
- [Distributed Differentially Private Data Analytics via Secure Sketching](https://mlsanity.com/paper/2412.00497/) (2024)
- [Mitigating Data Poisoning Attacks to Local Differential Privacy](https://mlsanity.com/paper/2506.02156/) (2025)
- [Differential Privacy: What is all the noise about?](https://mlsanity.com/paper/2205.09453/) (2022)
- [Private Multi-Winner Voting for Machine Learning](https://mlsanity.com/paper/2211.15410/) (2022)
- [Privacy-Computation trade-offs in Private Repetition and Metaselection](https://mlsanity.com/paper/2410.19012/) (2024)
- [A Locally Differential Private Coding-Assisted Succinct Histogram Protocol](https://mlsanity.com/paper/2506.17767/) (2025)

## Abstract (arXiv)

We present new practical local differentially private heavy hitters algorithms achieving optimal or near-optimal worst-case error and running time -- TreeHist and Bitstogram. In both algorithms, server running time is tilde O(n) and user running time is tilde O(1), hence improving on the prior state-of-the-art result of Bassily and Smith [STOC 2015] requiring O(n5/2) server time and O(n3/2) user time. With a typically large number of participants in local algorithms (n in the millions), this reduction in time complexity, in particular at the user side, is crucial for making locally private heavy hitters algorithms usable in practice. We implemented Algorithm TreeHist to verify our theoretical analysis and compared its performance with the performance of Google's RAPPOR code.