Frequency estimation under local differential privacy
Authors:
Open Access
- 1 July 2021
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 14 (11) , 2046-2058
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.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Small Summaries for Big Data2020
- Locally Differentially Private Heavy Hitter IdentificationIEEE Transactions on Dependable and Secure Computing, 2019
- Answering range queries under local differential privacyProceedings of the VLDB Endowment, 2019
- Privacy at Scale2018
- PrivTrie: Effective Frequent Term Discovery under Local Differential Privacy2018
- Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data DictionariesProceedings on Privacy Enhancing Technologies, 2016
- Local, Private, Efficient Protocols for Succinct Histograms2015
- RAPPOR2014
- An improved data stream summary: the count-min sketch and its applicationsJournal of Algorithms, 2005
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970