# Local, Private, Efficient Protocols for Succinct Histograms

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2015.

## Built on by (most cited first, 30 of 36)

- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [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)
- [XRand: Differentially Private Defense against Explanation-Guided Attacks](https://mlsanity.com/paper/2212.04454/) (2022)
- [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)
- [Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming](https://mlsanity.com/paper/2104.01808/) (2021)
- [Universal Exact Compression of Differentially Private Mechanisms](https://mlsanity.com/paper/2405.20782/) (2024)
- [A Systematic and Formal Study of the Impact of Local Differential Privacy on Fairness: Preliminary Results](https://mlsanity.com/paper/2405.14725/) (2024)
- [(Local) Differential Privacy has NO Disparate Impact on Fairness](https://mlsanity.com/paper/2304.12845/) (2023)
- [Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages](https://mlsanity.com/paper/2404.10201/) (2024)
- [Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints](https://mlsanity.com/paper/2106.08597/) (2021)
- [Algorithms with More Granular Differential Privacy Guarantees](https://mlsanity.com/paper/2209.04053/) (2022)
- [Transfer Learning In Differential Privacy's Hybrid-Model](https://mlsanity.com/paper/2201.12018/) (2022)
- [Adversary for Social Good: Leveraging Adversarial Attacks to Protect Personal Attribute Privacy](https://mlsanity.com/paper/2306.02488/) (2023)
- [P2NIA: Privacy-Preserving Non-Iterative Auditing](https://mlsanity.com/paper/2504.00874/) (2025)
- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)
- [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)
- [Locally Differentially Private Distributed Deep Learning via Knowledge Distillation](https://mlsanity.com/paper/2202.02971/) (2022)
- [One-bit Submission for Locally Private Quasi-MLE: Its Asymptotic Normality and Limitation](https://mlsanity.com/paper/2202.07194/) (2022)
- [On the Utility Gain of Iterative Bayesian Update for Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2307.07744/) (2023)
- [Evaluating the Impact of Local Differential Privacy on Utility Loss via Influence Functions](https://mlsanity.com/paper/2309.08678/) (2023)
- [Extracting Spatiotemporal Data from Gradients with Large Language Models](https://mlsanity.com/paper/2410.16121/) (2024)
- [Distributed Differentially Private Data Analytics via Secure Sketching](https://mlsanity.com/paper/2412.00497/) (2024)
- [PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors](https://mlsanity.com/paper/2503.11897/) (2025)
- [Mitigating Data Poisoning Attacks to Local Differential Privacy](https://mlsanity.com/paper/2506.02156/) (2025)
- [Towards Confidential and Efficient LLM Inference with Dual Privacy Protection](https://mlsanity.com/paper/2509.09091/) (2025)

## Abstract (arXiv)

We give efficient protocols and matching accuracy lower bounds for frequency estimation in the local model for differential privacy. In this model, individual users randomize their data themselves, sending differentially private reports to an untrusted server that aggregates them. We study protocols that produce a succinct histogram representation of the data. A succinct histogram is a list of the most frequent items in the data (often called "heavy hitters") along with estimates of their frequencies; the frequency of all other items is implicitly estimated as 0. If there are n users whose items come from a universe of size d, our protocols run in time polynomial in n and log(d). With high probability, they estimate the accuracy of every item up to error Oleft(√log(d)/(ε2n)right) where ε is the privacy parameter. Moreover, we show that this much error is necessary, regardless of computational efficiency, and even for the simple setting where only one item appears with significant frequency in the data set. Previous protocols (Mishra and Sandler, 2006; Hsu, Khanna and Roth, 2012) for this task either ran in time Omega(d) or had much worse error (about √[6]log(d)/(ε2n)), and the only known lower bound on error was Omega(1/√n). We also adapt a result of McGregor et al (2010) to the local setting. In a model with public coins, we show that each user need only send 1 bit to the server. For all known local protocols (including ours), the transformation preserves computational efficiency.