AIセキュリティポータル K Program
Private Counting of Distinct Elements in the Turnstile Model and Extensions
Share
Abstract
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].
Detecting ddos attacks on isp networks
Aditya Akella, Ashwin Bharambe, Mike Reiter, Srinivasan Seshan
Published: 2003
Private decayed predicate sums on streams
Jean Bolot, Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, Nina Taft
Published: 2013
Dashing: fast and accurate genomic distances with hyperloglog
Daniel N Baker, Ben Langmead
Published: 2019
Fingerprinting codes and the price of approximate differential privacy
Mark Bun, Jonathan R. Ullman, Salil P. Vadhan
Published: 2018
Ddos detection in P4 using HYPERLOGLOG and COUNTMIN sketches
Vera Clemens, Lars-Christian Schulz, Marten Gartner, David Hausheer
Published: 2023
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith
Published: 2006
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
Published: 2009
Bitmap algorithms for counting active flows on high-speed links
Cristian Estan, George Varghese, Michael E. Fisk
Published: 2006
Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm
Philippe Flajolet, Eric Fusy, Olivier Gandouet, Frédéric Meunier
Published: 2007
Differentially private algorithms for graphs under continual observation
Hendrik Fichtenberger, Monika Henzinger, Lara Ost
Published: 2021
Probabilistic counting algorithms for data base applications
Philippe Flajolet, G. Nigel Martin
Published: 1985
Private counting of distinct and k-occurring items in time windows
Badih Ghazi, Ravi Kumar, Jelani Nelson, Pasin Manurangsi
Published: 2023
Differentially private histogram, predecessor, and set cardinality under continual observation
Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner
Published: 2023
Counting distinct elements in the turnstile model with differential privacy under continual observation
Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith
Published: 2023
An optimal algorithm for the distinct elements problem
Daniel M. Kane, Jelani Nelson, David P. Woodruff
Published: 2010
Hyperlogloglog: Cardinality estimation with one log more
Matti Karppa, Rasmus Pagh
Published: 2022
Understanding the sparse vector technique for differential privacy
Min Lyu, Dong Su, Ninghui Li
Published: 2017
Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic
Ahmed Metwally, Divyakant Agrawal, Amr El Abbadi
Published: 2008
Locating highly connected clusters in large networks with hyperloglog counters
Lotte Weedage, Nelly Litvak, Clara Stegehuis
Published: 2021
Better cardinality estimators for hyperloglog, pcsa, and beyond
Dingyu Wang, Seth Pettie
Published: 2023
Share