2026-08-01T14:28:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21033 2024-09-16T06:02:39Z ddc:004 open_access

Private Counting of Distinct Elements in the Turnstile Model and Extensions Henzinger, Monika Sricharan, A. R. Steiner, Teresa Anna differential privacy turnstile model counting distinct elements 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 (ε,δ)-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 (ε,δ)-differential privacy and item-level ε-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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Monika Henzinger and A. R. Sricharan and Teresa Anna Steiner 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40 urn:nbn:de:0030-drops-210335 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.40 eng https://creativecommons.org/licenses/by/4.0/legalcode