Local, Private, Efficient Protocols for Succinct Histograms

Understand

We give efficient protocols and matching accuracy lower bounds for frequency estimation in the local model for differential privacy.

• In this model, individual users randomize their data themselves, sending differentially private reports to an untrusted server that aggregates them.
• We study protocols that produce a succinct histogram representation of the data.
• A succinct histogram is a list of the most frequent items in the data (often called "heavy hitters") along with estimates of their frequencies; the frequency of all other items is implicitly estimated as 0.