License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.48
URN: urn:nbn:de:0030-drops-175513
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17551/
Epasto, Alessandro ;
Mao, Jieming ;
Medina, Andres Munoz ;
Mirrokni, Vahab ;
Vassilvitskii, Sergei ;
Zhong, Peilin
Differentially Private Continual Releases of Streaming Frequency Moment Estimations
Abstract
The streaming model of computation is a popular approach for working with large-scale data. In this setting, there is a stream of items and the goal is to compute the desired quantities (usually data statistics) while making a single pass through the stream and using as little space as possible.
Motivated by the importance of data privacy, we develop differentially private streaming algorithms under the continual release setting, where the union of outputs of the algorithm at every timestamp must be differentially private. Specifically, we study the fundamental ?_p (p ∈ [0,+∞)) frequency moment estimation problem under this setting, and give an ε-DP algorithm that achieves (1+η)-relative approximation (∀ η ∈ (0,1)) with polylog(Tn) additive error and uses polylog(Tn)⋅ max(1, n^{1-2/p}) space, where T is the length of the stream and n is the size of the universe of elements. Our space is near optimal up to poly-logarithmic factors even in the non-private setting.
To obtain our results, we first reduce several primitives under the differentially private continual release model, such as counting distinct elements, heavy hitters and counting low frequency elements, to the simpler, counting/summing problems in the same setting. Based on these primitives, we develop a differentially private continual release level set estimation approach to address the ?_p frequency moment estimation problem.
We also provide a simple extension of our results to the harder sliding window model, where the statistics must be maintained over the past W data items.
BibTeX - Entry
@InProceedings{epasto_et_al:LIPIcs.ITCS.2023.48,
author = {Epasto, Alessandro and Mao, Jieming and Medina, Andres Munoz and Mirrokni, Vahab and Vassilvitskii, Sergei and Zhong, Peilin},
title = {{Differentially Private Continual Releases of Streaming Frequency Moment Estimations}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {48:1--48:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17551},
URN = {urn:nbn:de:0030-drops-175513},
doi = {10.4230/LIPIcs.ITCS.2023.48},
annote = {Keywords: Differential Privacy, Continual Release, Sliding Window, Streaming Algorithms, Distinct Elements, Frequency Moment Estimation}
}
|
Keywords: |
|
Differential Privacy, Continual Release, Sliding Window, Streaming Algorithms, Distinct Elements, Frequency Moment Estimation |
|
Collection: |
|
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
01.02.2023 |
