# Federated Heavy Hitters Discovery with Differential Privacy

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

## Key facts

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

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

- [Personalized Federated Learning using Hypernetworks](https://mlsanity.com/paper/2103.04628/) (2021)
- [Personalized Federated Learning with Gaussian Processes](https://mlsanity.com/paper/2106.15482/) (2021)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [Eliminating Domain Bias for Federated Learning in Representation Space](https://mlsanity.com/paper/2311.14975/) (2023)
- [Personalizing Federated Medical Image Segmentation via Local Calibration](https://mlsanity.com/paper/2207.04655/) (2022)
- [Stronger Privacy for Federated Collaborative Filtering with Implicit Feedback](https://mlsanity.com/paper/2105.03941/) (2021)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Federated Learning with Heterogeneous Architectures using Graph HyperNetworks](https://mlsanity.com/paper/2201.08459/) (2022)
- [Federated Select: A Primitive for Communication- and Memory-Efficient Federated Learning](https://mlsanity.com/paper/2208.09432/) (2022)
- [Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation](https://mlsanity.com/paper/2111.02356/) (2021)
- [FedWalk: Communication Efficient Federated Unsupervised Node Embedding with Differential Privacy](https://mlsanity.com/paper/2205.15896/) (2022)
- [Federated Analytics: A survey](https://mlsanity.com/paper/2302.01326/) (2023)
- [Samplable Anonymous Aggregation for Private Federated Data Analysis](https://mlsanity.com/paper/2307.15017/) (2023)
- [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)
- [Hierarchical Federated Learning with Privacy](https://mlsanity.com/paper/2206.05209/) (2022)
- [Swan: A Neural Engine for Efficient DNN Training on Smartphone SoCs](https://mlsanity.com/paper/2206.04687/) (2022)
- [Towards Heterogeneous Clients with Elastic Federated Learning](https://mlsanity.com/paper/2106.09433/) (2021)
- [Differentially Private Heavy Hitter Detection using Federated Analytics](https://mlsanity.com/paper/2307.11749/) (2023)
- [The Gift of Feedback: Improving ASR Model Quality by Learning from User Corrections through Federated Learning](https://mlsanity.com/paper/2310.00141/) (2023)
- [Private Cross-Silo Federated Learning for Extracting Vaccine Adverse Event Mentions](https://mlsanity.com/paper/2103.07491/) (2021)
- [Secure Bayesian Federated Analytics for Privacy-Preserving Trend Detection](https://mlsanity.com/paper/2107.13640/) (2021)
- [An Experimental Study on Private Aggregation of Teacher Ensemble Learning for End-to-End Speech Recognition](https://mlsanity.com/paper/2210.05614/) (2022)
- [Federated Learning with Only Positive Labels by Exploring Label Correlations](https://mlsanity.com/paper/2404.15598/) (2024)
- [Better Locally Private Sparse Estimation Given Multiple Samples Per User](https://mlsanity.com/paper/2408.04313/) (2024)
- [PAPAYA Federated Analytics Stack: Engineering Privacy, Scalability and Practicality](https://mlsanity.com/paper/2412.02340/) (2024)
- [Improving the Algorithm of Deep Learning with Differential Privacy](https://mlsanity.com/paper/2107.05457/) (2021)
- [Private Multi-Winner Voting for Machine Learning](https://mlsanity.com/paper/2211.15410/) (2022)
- [When approximate design for fast homomorphic computation provides differential privacy guarantees](https://mlsanity.com/paper/2304.02959/) (2023)
- [Private Federated Frequency Estimation: Adapting to the Hardness of the Instance](https://mlsanity.com/paper/2306.09396/) (2023)

## Abstract (arXiv)

The discovery of heavy hitters (most frequent items) in user-generated data streams drives improvements in the app and web ecosystems, but can incur substantial privacy risks if not done with care. To address these risks, we propose a distributed and privacy-preserving algorithm for discovering the heavy hitters in a population of user-generated data streams. We leverage the sampling and thresholding properties of our distributed algorithm to prove that it is inherently differentially private, without requiring additional noise. We also examine the trade-off between privacy and utility, and show that our algorithm provides excellent utility while also achieving strong privacy guarantees. A significant advantage of this approach is that it eliminates the need to centralize raw data while also avoiding the significant loss in utility incurred by local differential privacy. We validate our findings both theoretically, using worst-case analyses, and practically, using a Twitter dataset with 1.6M tweets and over 650k users. Finally, we carefully compare our approach to Apple's local differential privacy method for discovering heavy hitters.