Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch
ACM SIGMOD Record · 14.05.2024 · 53 (1) · 7-14
DOI: 10.1145/3665252.3665255 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGMOD Record, online erschienen am 14.05.2024. Verfasst von Christian Janos Lebeda und 1 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 17 Literaturangaben.
Abstract (Originalsprache)
We consider the problem of computing differentially private approximate histograms and heavy hitters in a stream of elements. In the non-private setting, this is often done using the sketch of Misra and Gries [Science of Computer Programming, 1982]. Chan, Li, Shi, and Xu [PETS 2012] describe a differentially private version of the Misra-Gries sketch, but the amount of noise it adds can be large and scales linearly with the size of the sketch; the more accurate the sketch is, the more noise this approach has to add. We present a better mechanism for releasing a Misra-Gries sketch under (ε, δ)-differential privacy. It adds noise with magnitude independent of the size of the sketch; in fact, the maximum error coming from the noise is the same as the best known in the private non-streaming setting, up to a constant factor. Our mechanism is simple and likely to be practical. In the full version of the paper we also give a simple post-processing step of the Misra-Gries sketch that does not increase the worst-case error guarantee. It is sufficient to add noise to this new sketch with less than twice the magnitude of the non-streaming setting. This improves on the previous result for "-differential privacy where the noise scales linearly to the size of the sketch.
Zitieren
APA
Lebeda, C. J., & Tetek, J. (2024). Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch. ACM SIGMOD Record, 53(1), 7-14. https://doi.org/10.1145/3665252.3665255
Vancouver
Lebeda CJ, Tetek J. Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch. ACM SIGMOD Record. 2024;53(1):7-14. doi:10.1145/3665252.3665255
BibTeX
@article{Lebeda2024,
author = {Lebeda, Christian Janos and Tetek, Jakub},
title = {Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch},
journal = {ACM SIGMOD Record},
year = {2024},
volume = {53},
number = {1},
pages = {7--14},
doi = {10.1145/3665252.3665255}
}
EUVIMED