mlsanityData to 7 Oct 2026

Practical Locally Private Heavy Hitters

arXiv 1707.04982 ↗First posted 17 Jul 2017cs.DScited by 28

Not on the map. Why?

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.

Key facts. Cited by 28 papers in the map (data through 7 Oct 2026). First posted on arXiv 17 Jul 2017.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 11; 2022: 6; 2023: 6; 2024: 3; 2025: 2.

28 papers.

Sort:

  1. 2023Harnessing large-language models to generate private synthetic textcited by 65
  2. 2021Generalized Linear Bandits with Local Differential Privacycited by 29
  3. 2021Lossless Compression of Efficient Private Local Randomizerscited by 27
  4. 2021Optimal Compression of Locally Differentially Private Mechanismscited by 22
  5. 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimationcited by 22
  6. 2021Locally Private k-Means in One Roundcited by 19
  7. 2021Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregationcited by 10
  8. 2021User-Level Private Learning via Correlated Samplingcited by 9
  9. 2022Private Frequency Estimation via Projective Geometrycited by 9
  10. 2023Federated Analytics: A surveycited by 9
  11. 2023On Differential Privacy and Adaptive Data Analysis with Bounded Spacecited by 9
  12. 2021Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streamingcited by 8
16 more
  1. 2022Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacycited by 7
  2. 2022Group privacy for personalized federated learningcited by 5
  3. 2021Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraintscited by 4
  4. 2022Training a Tokenizer for Free with Private Federated Learningcited by 4
  5. 2023Advancing Personalized Federated Learning: Group Privacy, Fairness, and Beyondcited by 2
  6. 2025Privacy-Preserving Conformal Prediction Under Local Differential Privacycited by 2
  7. 2021Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Errorcited by 1
  8. 2021Differentially Private Algorithms for Clustering with Stability Assumptionscited by 1
  9. 2021Locally Differentially Private Bayesian Inferencecited by 1
  10. 2023Training generative models from privatized datacited by 1
  11. 2024Better Locally Private Sparse Estimation Given Multiple Samples Per Usercited by 1
  12. 2024Distributed Differentially Private Data Analytics via Secure Sketchingcited by 1
  13. 2022Differential Privacy: What is all the noise about?cited by 0
  14. 2022Private Multi-Winner Voting for Machine Learningcited by 0
  15. 2024Privacy-Computation trade-offs in Private Repetition and Metaselectioncited by 0
  16. 2025A Locally Differential Private Coding-Assisted Succinct Histogram Protocolcited by 0