Research map / Federated learning and privacy / Differential privacy

Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model

ICML 2025 · Federated learning and privacy › Differential privacy · approach: Privacy accounting and mechanisms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first sublinear-space differentially private continual-release algorithm for counting distinct elements in the turnstile model, using KSET sketches, a binary mechanism, and occurrency-based blocklisting.

Problem

Counting distinct elements under event-level differential privacy in the turnstile continual release model, where prior algorithms require linear space and error grows with flippancy.

Approach

Combine a KSET distinct-sample dictionary (with an added capacity check so it fails deterministically when over capacity) with a Gaussian binary-tree mechanism over distinct-count changes, and blocklist items whose occurrency exceeds a threshold W = T^{2/3}, so sensitivity depends only on occurrency rather than flippancy.

Key results

• Achieves (1+eta)-relative approximation with additive error and space Õ(T^{1/3}) for arbitrary turnstile streams under approximate zCDP, improving over linear-space prior work.
• When occurrency bound W is known, additive error and space are Õ(sqrt(W)), matching prior linear-space error asymptotically.
• Shows a blocklisting space lower bound of Ω̃(T/W), implying optimality up to log factors for blocklisting-based approaches (with W=T^{2/3} giving Ω̃(T^{1/3})).

Measured effects reported in the paper

Limitations

• Space lower bound applies only to blocklisting-based techniques, not to all DP continual release algorithms.
• Additive error T^{1/3} for arbitrary streams is above the known Ω(T^{1/4}) lower bound; gap left open.
• Relies on multiplicative (1+eta) approximation and the algorithm's guarantees are approximate zCDP with a failure probability beta.

Experimental setup

Metrics: additive error relative approximation factor space

Baselines: Dong et al. turnstile DP distinct elements (flippancy-based) insertion-only DP distinct elements continual release

Builds on: binary tree mechanism KSET data structure zero-concentrated differential privacy flippancy-based DP distinct counting

Closest papers by meaning

• Private Continual Counting of Unbounded Streams (NeurIPS 2025 · similarity 0.89)
• Differentially Private Set Representations (NeurIPS 2024 · similarity 0.87)
• Lightweight Protocols for Distributed Private Quantile Estimation (ICML 2025 · similarity 0.86)
• Continual Counting with Gradual Privacy Expiration (NeurIPS 2024 · similarity 0.86)
• Privately Counting Partially Ordered Data (ICLR 2025 · similarity 0.86)
• On Fine-Grained Distinct Element Estimation (ICML 2025 · similarity 0.86)