Frequency Estimation under Local Differential Privacy [Experiments, Analysis and Benchmarks]

Abstract

Private collection of statistics from a large distributed population is an important problem, and has led to large scale deployments from several leading technology companies. The dominant approach requires each user to randomly perturb their input, leading to guarantees in the local differential privacy model. In this paper, we place the various approaches that have been suggested into a common framework, and perform an extensive series of experiments to understand the tradeoffs between different implementation choices. Our conclusion is that for the core problems of frequency estimation and heavy hitter identification, careful choice of algorithms can lead to very effective solutions that scale to millions of users

arXiv comment13 pages; Updated figures (7,8,10) and minor corrections

References in corpus (5)

• RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response
• Local, Private, Efficient Protocols for Succinct Histograms
• Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
• Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
• Local Differential Privacy and Its Applications: A Comprehensive Survey

Cited by in corpus (8)

• LDP-IDS: Local Differential Privacy for Infinite Data Streams
• LDPTrace: Locally Differentially Private Trajectory Synthesis
• Improving the utility of locally differentially private protocols for longitudinal and multidimensional frequency estimates
• On the Risks of Collecting Multidimensional Data Under Local Differential Privacy
• Multi-Freq-LDPy: Multiple Frequency Estimation Under Local Differential Privacy in Python
• Revealing the True Cost of Locally Differentially Private Protocols: An Auditing Perspective
• Locally Differentially Private Bayesian Inference
• SpaceSaving${}^{\pm }$: An Optimal Algorithm for Frequency Estimation and Frequent items in the Bounded Deletion Model