The Library
Frequency estimation under multiparty differential privacy : one-shot and streaming
Tools
Tools
Tools
Huang, Ziyue, Qiu, Yuan, Yi, Ke and Cormode, Graham (2022) Frequency estimation under multiparty differential privacy : one-shot and streaming. Proceedings of the VLDB Endowment, 15 (10). pp. 2058-2070. doi:10.14778/3547305.3547312 ISSN 2150-8097.
|
PDF
3547305.3547312.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (1244Kb) | Preview |
Official URL: http://dx.doi.org/10.14778/3547305.3547312
Abstract
We study the fundamental problem of frequency estimation under both privacy and communication constraints, where the data is distributed among k parties. We consider two application scenarios: (1) one-shot, where the data is static and the aggregator conducts a one-time computation; and (2) streaming, where each party receives a stream of items over time and the aggregator continuously monitors the frequencies. We adopt the model of multiparty differential privacy (MDP), which is more general than local differential privacy (LDP) and (centralized) differential privacy. Our protocols achieve optimality (up to logarithmic factors) permissible by the more stringent of the two constraints. In particular, when specialized to the ε-LDP model, our protocol achieves an error of √k/(εΘ(ε) − 1) using O(k max{ε, log 1/ε}) bits of communication and O(k log u) bits of public randomness, where u is the size of the domain.
| Item Type: | Journal Article | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | H Social Sciences > HD Industries. Land use. Labor Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TK Electrical engineering. Electronics Nuclear engineering |
||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Computer algorithms, Telecommunication systems, Computer networks , Streaming technology (Telecommunications), Data protection, Data privacy | ||||||||||||||||||
| Journal or Publication Title: | Proceedings of the VLDB Endowment | ||||||||||||||||||
| Publisher: | ACM | ||||||||||||||||||
| ISSN: | 2150-8097 | ||||||||||||||||||
| Official Date: | 7 September 2022 | ||||||||||||||||||
| Dates: |
|
||||||||||||||||||
| Volume: | 15 | ||||||||||||||||||
| Number: | 10 | ||||||||||||||||||
| Page Range: | pp. 2058-2070 | ||||||||||||||||||
| DOI: | 10.14778/3547305.3547312 | ||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||
| Publication Status: | Published | ||||||||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||||||||
| Date of first compliant deposit: | 7 October 2022 | ||||||||||||||||||
| Date of first compliant Open Access: | 7 October 2022 | ||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
