---
_id: '18156'
abstract:
- lang: eng
  text: 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].
acknowledgement: "Monika Henzinger: This project has received funding from the European
  Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
  programme (MoDynStruct,No. 101019564) and the Austrian Science Fund (FWF) grant
  DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with
  additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nTeresa Anna
  Steiner: Supported by a research grant (VIL51463) from VILLUM FONDEN."
alternative_title:
- LIPIcs
article_number: '40'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: A. R.
  full_name: Sricharan, A. R.
  last_name: Sricharan
- first_name: Teresa Anna
  full_name: Steiner, Teresa Anna
  last_name: Steiner
citation:
  ama: 'Henzinger M, Sricharan AR, Steiner TA. Private counting of distinct elements
    in the turnstile model and extensions. In: <i>International Conference on Approximation
    Algorithms for Combinatorial Optimization Problems </i>. Vol 317. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2024. doi:<a href="https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40">10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>'
  apa: 'Henzinger, M., Sricharan, A. R., &#38; Steiner, T. A. (2024). Private counting
    of distinct elements in the turnstile model and extensions. In <i>International
    Conference on Approximation Algorithms for Combinatorial Optimization Problems
    </i> (Vol. 317). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik. <a href="https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>'
  chicago: Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Private Counting
    of Distinct Elements in the Turnstile Model and Extensions.” In <i>International
    Conference on Approximation Algorithms for Combinatorial Optimization Problems
    </i>, Vol. 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href="https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>.
  ieee: M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Private counting of distinct
    elements in the turnstile model and extensions,” in <i>International Conference
    on Approximation Algorithms for Combinatorial Optimization Problems </i>, London,
    United Kingdom, 2024, vol. 317.
  ista: 'Henzinger M, Sricharan AR, Steiner TA. 2024. Private counting of distinct
    elements in the turnstile model and extensions. International Conference on Approximation
    Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation
    Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40.'
  mla: Henzinger, Monika, et al. “Private Counting of Distinct Elements in the Turnstile
    Model and Extensions.” <i>International Conference on Approximation Algorithms
    for Combinatorial Optimization Problems </i>, vol. 317, 40, Schloss Dagstuhl -
    Leibniz-Zentrum für Informatik, 2024, doi:<a href="https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40">10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>.
  short: M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, International Conference
    on Approximation Algorithms for Combinatorial Optimization Problems , Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
  end_date: 2024-08-30
  location: London, United Kingdom
  name: 'APPROX: Conference on Approximation Algorithms for Combinatorial Optimization
    Problems'
  start_date: 2024-08-27
corr_author: '1'
date_created: 2024-09-29T22:01:38Z
date_published: 2024-09-16T00:00:00Z
date_updated: 2025-12-02T13:47:16Z
day: '16'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.APPROX/RANDOM.2024.40
ec_funded: 1
external_id:
  arxiv:
  - '2408.11637'
  isi:
  - '001545634500040'
file:
- access_level: open_access
  checksum: c08b41c896e4d8c69570044808b40e0b
  content_type: application/pdf
  creator: dernst
  date_created: 2024-10-01T10:07:14Z
  date_updated: 2024-10-01T10:07:14Z
  file_id: '18166'
  file_name: 2024_LIPICs_HenzingerM.pdf
  file_size: 973917
  relation: main_file
  success: 1
file_date_updated: 2024-10-01T10:07:14Z
has_accepted_license: '1'
intvolume: '       317'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
  grant_number: Z00422
  name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
  grant_number: P33775
  name: Fast Algorithms for a Reactive Network Layer
publication: 'International Conference on Approximation Algorithms for Combinatorial
  Optimization Problems '
publication_identifier:
  isbn:
  - '9783959773485'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Private counting of distinct elements in the turnstile model and extensions
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 317
year: '2024'
...