Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams

By T-H. Hubert Chan, Mingfei Li, Elaine Shi, Wenchang Xu. 2012

127 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Science Applications

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 Science Applications

Citations in the corpus

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.”
RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response (2014, background): “Our work fits into a category of recently-explored problems where an untrusted aggregator 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, and, in some cases, restri”
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].”
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].”
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.”
Efficient Use of Differentially Private Binary Trees (2015, methodology): “They are central to the algorithm of Dwork et al (2010) for releasing private streaming data, and used in numerous adaptations of this problem, such as Chan et al (2012), Cao et al (2013), and Thakurta and Smith (2013).”
Preserving differential privacy in convolutional deep belief networks (2017, background): “…studied, from both the theoretical perspective, e.g., [15, 35], and the application perspective, e.g., data collection [22], data streams [13], stochastic gradient descents [69], recommendation [49], regression [15], online learning [33], publishing contingency tables [74], and spectral…”
Learning Differentially Private Recurrent Language Models (2017, methodology): “entially 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]. For this work, we simpliﬁed the problem by pre-selecting a dictionary of the most frequent 1”
Adaptive Laplace Mechanism: Differential Privacy Preservation in Deep Learning (2017, background): “, data collection [19], spatiotemporal correlations [20, 21], data streams [22], stochastic gradient descents [23], recommendation [7], regression [6], online learning [24], publishing contingency tables [25], and spectral graph analysis [26].”
Locally Differentially Private Frequent Itemset Mining (2018, background): “An FO protocol can identify only values that are very frequent in the population, because the scale of the added noises is linear to square root of the population size [11].”
Differentially Private Event Sequences over Infinite Streams (2014, background): “Chan et al. [7] report the heavy hitters instead of the counter values in various settings, such as sliding windows and multiple streams with untrusted aggregators.”
Locally Differentially Private Heavy Hitter Identification (2017, background): “The problem has been studied in the centralized DP setting [7], [25].”
Monitoring web browsing behavior with differential privacy (2014, background): “Since then, various works have adopted this deﬁnition for publishing histograms [27], search logs [18], mining data streams [6], and record linkage [3].”
Privacy at Scale: Local Differential Privacy in Practice (2018, background): “can identify only values that are very frequent in the population, because the scale of the added noise is proportional to square root of the population size [5].”