Privately counting distinct elements in a stream is a fundamental data
analysis problem with many applications in machine learning. In the turnstile
model, Jain et al. [NeurIPS2023] initiated the study of this problem
parameterized by the maximum flippancy of any element, i.e., the number of
times that the count of an element changes from 0 to above 0 or vice versa.
They give an item-level $(\epsilon,\delta)$-differentially private algorithm
whose additive error is tight with respect to that parameterization. In this
work, we show that a very simple algorithm based on the sparse vector technique
achieves a tight additive error for item-level $(\epsilon,\delta)$-differential
privacy and item-level $\epsilon$-differential privacy with regards to a
different parameterization, namely the sum of all flippancies. Our second
result is a bound which shows that for a large class of algorithms, including
all existing differentially private algorithms for this problem, the lower
bound from item-level differential privacy extends to event-level differential
privacy. This partially answers an open question by Jain et al. [NeurIPS2023].
参考文献
Workshop on Management and Processing of Data Streams
Detecting ddos attacks on isp networks
Aditya Akella, Ashwin Bharambe, Mike Reiter, Srinivasan Seshan
Published: 2003
International Conference on Database Theory (ICDT)
Private decayed predicate sums on streams
Jean Bolot, Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, Nina Taft
Published: 2013
Genome Biol.
Dashing: fast and accurate genomic distances with hyperloglog
Daniel N Baker, Ben Langmead
Published: 2019
SIAM J. Comput.
Fingerprinting codes and the price of approximate differential privacy
Mark Bun, Jonathan R. Ullman, Salil P. Vadhan
Published: 2018
Network Operations and Management Symposium (NOMS)
Ddos detection in P4 using HYPERLOGLOG and COUNTMIN sketches
Vera Clemens, Lars-Christian Schulz, Marten Gartner, David Hausheer
Published: 2023
Theory of Cryptography
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith
Published: 2006
Proceedings of the 41st Annual ACM Symposium on Theory of Computing
On the complexity of differentially private data release: efficient algorithms and hardness results
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, Salil P. Vadhan