Locally Differentially Private Heavy Hitter Identification

By Tianhao Wang, Ninghui Li, Somesh Jha. 2017

133 citations recorded by the source corpus.

The notion of Local Differential Privacy (LDP) enables users to answer sensitive questions while preserving their privacy. The basic LDP frequency oracle protocol enables the aggregator to estimate the frequency of any value. But when the domain of input values is large, finding the most frequent values, also known as the heavy hitters, by estimating the frequencies of all possible values, is computationally infeasible. In this paper, we propose an LDP protocol for identifying heavy hitters. In our proposed protocol, which we call Prefix Extending Method (PEM), users are divided into groups, with each group reporting a prefix of her value. We analyze how to choose optimal parameters for the protocol and identify two design principles for designing LDP protocols with high utility. Experiments show that under the same privacy guarantee and computational cost, PEM has better utility on both synthetic and real-world datasets than existing solutions.

Subfields: Artificial Intelligence

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

1. Neil Zhenqiang Gong
2. Jinyuan Jia
3. Ninghui Li
4. Tianhao Wang
5. Somesh Jha
6. Jun Zhao
7. Bolin Ding
8. Xiaokui Xiao

Citations in the corpus

• 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”
• Answering Multi-Dimensional Analytical Queries under Local Differential Privacy (2019, background): “LDP mechanisms. e.g. e.g. other tasks, e.g. , finding heavy hitters [4, 6, 36], frequent item-set works [9, 12, 13], as we also support AVG aggregation function Releasing marginals privately.”
• Locally Differentially Private Data Collection and Analysis (2019, background): “So far most existing algorithms [21, 32, 5, 49, 48, 50] are designed for estimating the frequencies of categorical attributes while ensuring ǫ-LDP.”
• 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.”