Private collection of statistics from a large distributed population is an
important problem, and has led to large scale deployments from several leading
technology companies. The dominant approach requires each user to randomly
perturb their input, leading to guarantees in the local differential privacy
model. In this paper, we place the various approaches that have been suggested
into a common framework, and perform an extensive series of experiments to
understand the tradeoffs between different implementation choices. Our
conclusion is that for the core problems of frequency estimation and heavy
hitter identification, careful choice of algorithms can lead to very effective
solutions that scale to millions of users

By admin