# Locally Differentially Private Heavy Hitter Identification

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Aug 2017.

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

- [DPIS: An Enhanced Mechanism for Differentially Private SGD with Importance Sampling](https://mlsanity.com/paper/2210.09634/) (2022)
- [Differentially Private Heavy Hitter Detection using Federated Analytics](https://mlsanity.com/paper/2307.11749/) (2023)
- [Mitigating Data Poisoning Attacks to Local Differential Privacy](https://mlsanity.com/paper/2506.02156/) (2025)
- [Local Differential Privacy for Smart Meter Data Sharing](https://mlsanity.com/paper/2311.04544/) (2023)
- [DP-Hype: Federated Differentially Private Hyperparameter Search](https://mlsanity.com/paper/2510.04902/) (2025)
- [ABC: Numerical Data Collection under Local Differential Privacy without Prior Knowledge](https://mlsanity.com/paper/2608.05737/) (2026)

## Abstract (arXiv)

The notion of Local Differential Privacy (LDP) enables users to answer sensitive questions while preserving their privacy. The basic LDP frequent oracle protocol enables the aggregator to estimate the frequency of any value. But when the domain of input values is large, finding the most frequent values, also known as the heavy hitters, by estimating the frequencies of all possible values, is computationally infeasible. In this paper, we propose an LDP protocol for identifying heavy hitters. In our proposed protocol, which we call Prefix Extending Method (PEM), users are divided into groups, with each group reporting a prefix of her value. We analyze how to choose optimal parameters for the protocol and identify two design principles for designing LDP protocols with high utility. Experiments on both synthetic and real-world datasets demonstrate the advantage of our proposed protocol.