Local, private, efficient protocols for succinct histograms

DOI10.1145/2746539.2746632MaRDI QIDQ2941496zbMATH OpenOpenAlexFDO

Authors

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.04686

zbMATH Keywords

algorithmscomplexitydifferential privacyheavy hitterslocal protocolssuccinct histograms

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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. If there are $n$ users whose items come from a universe of size $d$, our protocols run in time polynomial in $n$ and $log(d)$. With high probability, they estimate the accuracy of every item up to error $Oleft(sqrtlog(d)/(epsilo{n}^{2}n)ight)$ where $epsilon$ is the privacy parameter. Moreover, we show that this much error is necessary, regardless of computational efficiency, and even for the simple setting where only one item appears with significant frequency in the data set. Previous protocols (Mishra and Sandler, 2006; Hsu, Khanna and Roth, 2012) for this task either ran in time $Omega(d)$ or had much worse error (about $sqrt[6]log(d)/(epsilo{n}^{2}n)$), and the only known lower bound on error was $Omega(1/sqrtn)$. We also adapt a result of McGregor et al (2010) to the local setting. In a model with public coins, we show that each user need only send 1 bit to the server. For all known local protocols (including ours), the transformation preserves computational efficiency.

Recommendations

• Practical locally private heavy hitters
• Distributed private heavy hitters
• Heavy Hitters and the Structure of Local Privacy
• On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
• Fast Private Norm Estimation and Heavy Hitters

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(16)

• Scalable and Jointly Differentially Private Packing
• Empirical risk minimization in the non-interactive local model of differential privacy
• Optimal locally private estimation under \(\ell_p\) loss for \(1\le p\le 2\)
• Locally differentially private item-based collaborative filtering
• Fast Private Norm Estimation and Heavy Hitters
• Separating Local & Shuffled Differential Privacy via Histograms
• scientific article; zbMATH DE number 7415119 (Why is no real title available?)
• Distributed private heavy hitters
• Forty years of frequent items
• Comment
• Practical locally private heavy hitters
• The complexity of differential privacy
• On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
• Local differentially private frequency estimation based on learned sketches
• Buying data from privacy-aware individuals: the effect of negative payments
• Key-value data collection and statistical analysis with local differential privacy

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Local, private, efficient protocols for succinct histograms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941496)