Heavy Hitters

By Raef Bassily, Kobbi Nissim, Uri Stemmer, Abhradeep Thakurta. 2009

268 citations recorded by the source corpus.

Subfields: Management, Monitoring, Policy and Law, 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 Management, Monitoring, Policy and Law

In Algorithms & Complexity

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “While LDP protocols are effective at enforcing privacy and have theoretical justifications [156, 135, 136], a number of results have shown that achieving local differential privacy while preserving utility is challenging particularly, especially in high-dimensional data settings [229, 388, 219, 51, ”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “, (Bassily et al., 2017)) as well as unsupervised machine learning tasks such as clustering (e.”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “Once these estimated counts are computed, [8] simply identiﬁed the input items p ∈ { 0 , 1 } b with large multiplicities in the data.”
Federated Heavy Hitters Discovery with Differential Privacy (2019, background): “…of fundamental work shows that in the context of learning distributions and heavy hitters, local DP often leads to a signiﬁcant reduction in utility (Kairouz et al., 2014; Wang et al., 2017; Bassily et al., 2017; Kairouz et al., 2016; Ye and Barg, 2018; Duchi et al., 2013; Cormode et al., 2018).”
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity (2018, methodology): “However, our protocol can be extended to the collection of multi-valued data or even data strings by building on existing techniques [EPK14, App17, BNST17].”
Differentially-Private "Draw and Discard" Machine Learning (2018, background): “Since the focus on differentially private computations in the local model is recent, most, if not all, efforts to date have been limited to learning aggregate statistics, rather than trainng more complex machine learning models [18], [2], [5], [4], [7].”
Collecting Telemetry Data Privately (2017, background): “In the context of telemetry collection one typically considers algorithms that exhibit differential privacy in the local model [12, 14, 7, 5, 3, 18], also called randomized response model [19], γ-amplification [13], or FRAPP [1].”
Marginal Release Under Local Differential Privacy (2017, methodology): “Apple’s implementation uses sketching to reduce the dimensionality of a massive domain [2, 5, 10].”
Prochlo: Strong Privacy for Analytics in the Crowd (2017, background): “Local differential privacy is the approach taken by our RAPPOR software monitoring system for the Chrome Web browser [28].”
Collecting and Analyzing Multidimensional Data with Local Differential Privacy (2019, background): “Various data analytics and machine learning problems have been studied under LDP, such as probability distribution estimation [15], [23], [30], [32], [42], heavy hitter discovery [4], [7], [33], [39], frequent new term discovery [37], frequency estimation [5], [38], frequent itemset mining [40], mar”
Learning Differentially Private Language Models Without Losing Accuracy (2017, methodology): “Training a fully differentially private language model from scratch requires a private mechanism to discover which words are frequent across the corpus, for example using techniques like distributed heavy-hitter estimation [7, 4].”
Heavy Hitters and the Structure of Local Privacy (2017, methodology): “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].”
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, methodology): “We enforce local differential privacy by randomizing the one-hot encoding of the item, as well as using the private count-sketch algorithm [16], [7], which has been demonstrated to work well over distributions with a very large support.”
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication (2018, methodology): “In the context of private estimation tasks, the problem of finding 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 atte”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, methodology): “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).”
Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints (2021, methodology): “For instance, if we use count-sketch based methods as in the heavy-hitter literature (Bassily et al., 2017; Bun et al., 2019), we can only localize to the resolution level α = O (√ (log n+ log d)/n ) 5, which is not enough to get the O ( s n2b ) rate.”
An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors (2018, background): “We refer the reader to [8, 6] for more details about the heavy hitters problem in the LDP setting.”
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].”