Locally Differentially Private Frequency Estimation with Consistency
arXiv:1905.08320
Abstract
Local Differential Privacy (LDP) protects user privacy from the data collector. LDP protocols have been increasingly deployed in the industry. A basic building block is frequency oracle (FO) protocols, which estimate frequencies of values. While several FO protocols have been proposed, the design goal does not lead to optimal results for answering many queries. In this paper, we show that adding post-processing steps to FO protocols by exploiting the knowledge that all individual frequencies should be non-negative and they sum up to one can lead to significantly better accuracy for a wide range of tasks, including frequencies of individual values, frequencies of the most frequent values, and frequencies of subsets of values. We consider 10 different methods that exploit this knowledge differently. We establish theoretical relationships between some of them and conducted extensive experimental evaluations to understand which methods should be used for different query tasks.
arXiv commentNDSS 2020
References in corpus (4)
- Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
- Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation
- Mutual Information Optimally Local Private Discrete Distribution Estimation
- Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible
Cited by in corpus (6)
- Local Differential Privacy and Its Applications: A Comprehensive Survey
- Secure Federated Submodel Learning
- Information-theoretic metrics for Local Differential Privacy protocols
- Linear and Range Counting under Metric-based Local Differential Privacy
- Answering Multi-Dimensional Range Queries under Local Differential Privacy
- AHEAD: Adaptive Hierarchical Decomposition for Range Query under Local Differential Privacy