Locally Differentially Private Heavy Hitter Identification

Abstract

The notion of Local Differential Privacy (LDP) enables users to answer sensitive questions while preserving their privacy. The basic LDP frequent 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 on both synthetic and real-world datasets demonstrate the advantage of our proposed protocol.

References in corpus (3)

• Deep Learning with Differential Privacy
• Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy
• Practical Locally Private Heavy Hitters

Cited by in corpus (6)

• A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis
• Collecting and Analyzing Multidimensional Data with Local Differential Privacy
• Locally Differentially Private Data Collection and Analysis
• Data Poisoning Attacks to Local Differential Privacy Protocols
• Calibrate: Frequency Estimation and Heavy Hitter Identification with Local Differential Privacy via Incorporating Prior Knowledge
• Building a Collaborative Phone Blacklisting System with Local Differential Privacy