  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.
