2026-07-22T22:18:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17558 2024-03-06T10:59:54Z ddc:004 open_access

Private Counting of Distinct and k-Occurring Items in Time Windows Ghazi, Badih Kumar, Ravi Nelson, Jelani Manurangsi, Pasin Differential Privacy Algorithms Distinct Elements Time Windows In this work, we study the task of estimating the numbers of distinct and k-occurring items in a time window under the constraint of differential privacy (DP). We consider several variants depending on whether the queries are on general time windows (between times t₁ and t₂), or are restricted to being cumulative (between times 1 and t₂), and depending on whether the DP neighboring relation is event-level or the more stringent item-level. We obtain nearly tight upper and lower bounds on the errors of DP algorithms for these problems. En route, we obtain an event-level DP algorithm for estimating, at each time step, the number of distinct items seen over the last W updates with error polylogarithmic in W; this answers an open question of Bolot et al. (ICDT 2013). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Badih Ghazi and Ravi Kumar and Jelani Nelson and Pasin Manurangsi 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.55 urn:nbn:de:0030-drops-175580 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.55 eng https://creativecommons.org/licenses/by/4.0/legalcode