Distributed Private Heavy Hitters

By Justin Hsu, Sanjeev Khanna, Aaron Roth. 2012

117 citations recorded by the source corpus.

In this paper, we give efficient algorithms and lower bounds for solving the heavy hitters problem while preserving differential privacy in the fully distributed local model. In this model, there are n parties, each of which possesses a single element from a universe of size N. The heavy hitters problem is to find the identity of the most common element shared amongst the n parties. In the local model, there is no trusted database administrator, and so the algorithm must interact with each of the n parties separately, using a differentially private protocol. We give tight information-theoretic upper and lower bounds on the accuracy to which this problem can be solved in the local model (giving a separation between the local model and the more common centralized model of privacy), as well as computationally efficient algorithms even in the case where the data universe N may be exponentially large.

Subfields: Artificial Intelligence, Computer Networks and Communications, Privacy & Security, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Privacy & Security

In Algorithms & Complexity

Citations in the corpus

Breaking the Communication-Privacy-Accuracy Trilemma (2020, background): “Frequency estimation is also closely related to heavy hitter estimation [10], [13], [17], [36], [37], [38], [39], where the goal is to discover symbols that appear frequently in a given data set and estimate their frequencies.”
Collecting Telemetry Data Privately (2017, background): “Recently, Bassily and Smith [4] gave asymptotically tight results for the problem in the worst-case model building on the works of [16].”
BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model (2017, background): “ticularly among practitioners [17, 35], fewer such algorithms are known [40, 19, 8, 13, 5].”
Discrete Distribution Estimation under Local Privacy (2016, background): “There is a rich literature on distribution estimation under local privacy (Chan et al., 2012; Hsu et al., 2012; Bassily & Smith, 2015), of which several works are particularly relevant herein.”
Local, Private, Efficient Protocols for Succinct Histograms (2015, methodology): “Our protocol differs from [14] in three respects.”
RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response (2014, background): “Our work ﬁts into the category of problems recently explored by [16, 18, 7, 20], where an untrusted aggre-gator wishes to learn the “heavy hitters” in the clients’ data or run certain types of learning algorithms on the aggregated data, while guaranteeing the privacy of each contributing client…”
Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries (2015, background): “Our work follows in a recent trend of using local differential privacy to learn a distribution’s heavy-hitters—the most significant categories in a distribution [17, 5, 11, 9].”
Heavy Hitters and the Structure of Local Privacy (2017, background): “This lower bound is known to be tight, as constructions of frequency oracles with matching error were presented in several works [2, 3, 14, 18].”
Efficient Private Statistics with Succinct Sketches (2015, background): “Work in [14, 42] address the problem of ﬁnding heavy hitters’ histograms while preserving privacy using a differentially private protocol.”
Privacy via the Johnson-Lindenstrauss Transform (2012, neutral): “[23]:”
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication (2018, background): “…tasks, the problem of ﬁnding the heavy hitters, and learning properties under local diﬀerential privacy under the assumption of public randomness, where the server can send communication to the clients to reduce communication from user end has received much attention recently [8, 7, 5, 30, 44, 11].”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “The problem of frequency/heavy hitter detection under εLDP has also received great attention (Hsu et al., 2012; Erlingsson et al., 2014; Bassily & Smith, 2015; Qin et al., 2016; Bassily et al., 2017; Ding et al., 2017; Bun et al., 2018).”
Calibrate: Frequency Estimation and Heavy Hitter Identification with Local Differential Privacy via Incorporating Prior Knowledge (2018, methodology): “We note that some studies [19], [5], [22], [6], [31] designed LDP algorithms to identify top-k heavy hitters, which are the k items that have the largest frequencies.”
Heavy Hitter Estimation over Set-Valued Data with Local Differential Privacy (2016, background): “[19] focus on es0 5 10 15 20 25 30 35 40 0 0.”
Manipulation Attacks in Local Differential Privacy (2019, background): “Computing heavy-hitters has been a focus of the past few years (Hsu et al., 2012; Bassily and Smith, 2015; Bassily et al., 2017; Bun et al., 2018), and it is central to systems deployed by Google (Erlingsson et al., 2014) and Apple (Apple Differential Privacy Team, 2017).”
Differentially Private Hierarchical Group Size Estimation (2018, background): “However, most of the heavy hitters work has been in the local privacy model, where each individual perturbs their data before sending them to the server [15, 6, 7, 20, 31].”