REVIEW 2 major objections 6 minor 17 references
Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model
T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper establishes the first differentially private continual-release algorithms for counting distinct elements in turnstile streams that use sublinear space, achieving $\tilde O(T^{1/3})$ space and additive error on arbitrary streams…
desk verdict First sublinear-space DP algorithm for turnstile distinct counting, with a new occurrency measure and a tight blocklisting lower bound; the flagged Lemma-2 coupling concern dissolves, leaving a one-line tau-vs-k typo as the only real fix. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The paper replaces the stateful notion of flippancy with occurrency, the stateless count of how many times an item appears (as insertion or deletion), and builds the algorithm from three pieces. The KSET ($k$-set) data structure is a low-space dictionary that returns the exact set of present items whenever at most $k$ distinct items are stored and returns NIL otherwise, giving a sublinear-space distinct sample. The blocklist stores items sampled with probability $p=\log(T^{1/3}L/\beta)/T^{2/3}$ so that, except with small failure probability, no item can appear more than $T^{2/3}$ times without being suppressed; this keeps the sensitivity of the tracked stream bounded. BinaryMechanism-CD is a binary-tree mechanism with Gaussian noise that privately accumulates the difference between consecutive KSET outputs, with noise scaled to an occurrency-based sensitivity bound. The algorithm runs $L=\lceil\log T\rceil$ copies on hash-subsampled streams with geometrically decreasing sampling rates and selects the coarsest copy whose noisy count is neither TOO-HIGH nor below threshold. Privacy is argued by coupling the KSET version to an exact-dictionary version (COUNTING-DICT) with identical thresholding, whose sensitivity is bounded in terms of occurrency.
What would settle it
Run BinaryMechanism-CD with a fixed random seed on the two two-timestep sequences $(+1,-1)$ and $(-1,+1)$, and compare the released noisy counts; if they differ, the order-insensitivity asserted in Lemma 2 is false. The direct end-to-end check is to simulate Algorithm 2 (COUNTING-KSET) and Algorithm 5 (COUNTING-DICT) on a stream whose distinct count rises above capacity $k$ and later falls back below $k$, and verify that the released estimates are identical once the KSET resumes returning a set.
Extended reading notes
Core claim
The paper's central claim is that approximate distinct-element counting in the turnstile model does not require linear memory even when privacy is enforced at every timestep. Formally, for every $\eta>0$, $\beta\in(0,1)$, stream length $T$, and universe $|U|=\mathrm{poly}(T)$, there is a $2\beta$-approximate $\rho$-zCDP algorithm that with probability at least $1-2\beta$ outputs a $(1\pm\eta,\ \max\{O(\gamma/\eta), O(\lambda/\eta^2)\})$-approximation to the number of distinct elements using $O(T^{1/3}\cdot\mathrm{polylog}(T/\beta))\cdot\mathrm{poly}(1/(\rho\eta))$ space, with $\gamma=O(T^{1/3}\sqrt{(\log T)^3\log(\log T/\beta)/\rho})$ and $\lambda=O(\log(\log T/\beta))$. When a promised bound $W$ on the occurrency of the stream is available, the same construction gives $\tilde O(\sqrt W)$ space and additive error. The paper also proves an information-theoretic space lower bound showing that any algorithm using the blocklisting approach must spend $\tilde\Omega(T^{1/3})$ space on arbitrary streams.
Load-bearing premise
The load-bearing premise is that feeding the binary mechanism two compressed sequences with the same total sum and same total length produces the same output under fixed randomness, regardless of the order of the $+1$, $-1$, and $0$ updates in each sequence; the coupling that transfers privacy from the exact-dictionary algorithm to the KSET-based algorithm depends on this, and the paper does not prove it.
Editorial extensions
If this is right
- Private turnstile distinct counting no longer needs to store the stream or the universe: the worst-case space is $\tilde O(T^{1/3})$ up to privacy factors, down from linear memory.
- For streams with a known bound $W$ on per-item appearances, the algorithm achieves $\tilde O(\sqrt W)$ space and additive error, matching the error of prior linear-space mechanisms.
- The blocklisting lower bound implies that any mechanism that controls occurrency or flippancy by ignoring high-occurrence items needs $\tilde\Omega(T^{1/3})$ space on arbitrary streams, so better space will require a different privacy strategy.
- The gap between the achieved $\tilde O(T^{1/3})$ additive error and the known $\tilde\Omega(T^{1/4})$ lower bound is now a concrete target for future work.
Reading between the lines
- The occurrency measure is stateless and may transfer to other turnstile problems whose sensitivity comes from flippancy, such as frequency moments or heavy hitters, giving a recipe for low-space private continual-release algorithms there.
- A workload with a few very hot items and a long tail would stress the blocklist: the worst-case $T^{1/3}$ bounds may be loose in practice, and experiments on such skew could reveal whether the sampling threshold or the number of substreams should be tuned.
- If Lemma 2's order-insensitivity of the binary mechanism fails, the coupling at the heart of the privacy proof would need repair; one possible repair is to feed KSET updates in timestamp order, which would preserve the space bounds only if that ordering can be maintained without extra memory.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper gives the first sublinear-space differentially private algorithms for counting distinct elements in the turnstile streaming model under continual release. It introduces a stateless notion of occurrency, combines the KSET data structure with a Gaussian binary mechanism, and handles unbounded-occurrency streams via a blocklisting procedure. For streams with promised occurrency bound W it claims O~(sqrt(W)) space and additive error; for arbitrary streams it claims O~(T^{1/3}) space and additive error. It also proves an information-theoretic space lower bound for the auxiliary blocklisting problem and claims a matching lower bound for algorithms that use blocklisting techniques. The upper-bound proofs are structured around a coupling between the space-efficient COUNTING-KSET and an exact COUNTING-DICT; the high-level approach is plausible, but one central threshold mismatch in the coupling lemma needs repair, and the scope of the lower-bound claim is overstated.
Significance. If the proof issues are corrected, the upper bounds would resolve an open question from JKR+23 in the affirmative, giving the first sublinear-space private algorithms in the turnstile continual-release model with nontrivial additive error. The paper contributes a new stateless measure (occurrency), a careful use of the KSET data structure in a DP context, a blocklisting framework with upper and lower bounds for the blocklisting subproblem, and a nontrivial coupling argument. These are useful techniques beyond the specific result. The lower-bound contribution, however, is formally only for the blocklisting problem unless a reduction to count-distinct algorithms is supplied; the abstract and Section 5.1 currently claim more.
major comments (2)
- [Appendix C.1 (Lemma 2 and Lemma 6)] The coupling proof of Lemma 2 defines the bad event E2 as "there exists a timestep where the true count is > k and the noisy count of COUNTING-DICT_i is ≤ k", and then states that Lemma 6 bounds E2. Lemma 6 only bounds the event "noisy count < τ when true count > k" (and its mirror). Since k > τ, the event in E2 is not covered: when the true count is k+1, a noise draw below -1 has non-negligible probability, so E2 cannot be bounded by the tail bound in Lemma 6. This is load-bearing because Case 2 of the coupling needs COUNTING-DICT_i to output TOO-HIGH, which only requires the noisy count to exceed τ. The fix is local: define E2 with τ in place of k, so that Lemma 6 applies directly and the existing gap k−τ is sufficient. I also checked the order-dependence objection to Case 3 of Lemma 2: it does not land, since Algorithm 4's output at a fixed internal time equals the prefix sum plus a noise term that depends only on the time and the fixed randomness, so two input sequences with the same total sum and same number of updates yield identical outputs.
- [Section 5.1 / Theorem 14 / abstract] The formal lower bound in Theorem 14 is for the auxiliary blocklisting problems blocklistflip(W) and blocklistocc(W). The text then asserts that this "extends to any algorithm for count distinct estimation that uses blocklisting methods" and the abstract claims that "any algorithm that uses similar techniques must use space Ω~(T^{1/3})". No reduction or formal definition is supplied: a count-distinct algorithm that internally maintains a blocklist does not necessarily solve blocklistocc(W), because its only output is the estimated distinct count, not the per-item blocklist decisions. As written, the matching-space claim for the main distinct-count problem is therefore not established; the authors should either provide a formal reduction/definition of the class of "blocklisting-based" algorithms or explicitly restrict the lower-bound claim to the blocklisting problem.
minor comments (6)
- [Definition 4] The displayed definition of δ-approximate ρ-zCDP uses a per-α disjunction; this is not the standard [BS16] definition, and the composition theorem cited (Theorem 4) is stated for the standard version. Please correct the definition or explain the variant.
- [Lemma 3 proof] The assertion that Si,B and S'i,B are "indeed neighboring" after hashing and blocklisting is false; by Lemma 9 they can differ in T^{2/3}+1 positions. The proof should cite Lemma 7/Lemma 9 for the bounded-difference sensitivity analysis rather than claiming the processed streams are neighboring.
- [Algorithm 1 / Corollary 7] The algorithm's accuracy theorem is stated for η ∈ (0, 0.5), while Corollary 7 states "for all η > 0"; please align the ranges.
- [Lemma 9 proof] There is a typo in the last paragraph: "S'i,B can differ from S'i,B" should read "Si,B can differ from S'i,B".
- [Theorem 5] The displayed formula for δ' is garbled; please reset and typeset the expression correctly.
- [Section 1.1] The comparison with [JKR+23]'s additive error mixes the two algorithms' parameters; please clarify the claimed "matches" statement and the role of the footnote about the multiplicative factor.
Circularity Check
No significant circularity: the central privacy, accuracy, and space claims are derived from independent primitives and information-theoretic arguments, not from fitted parameters or load-bearing self-citation.
full rationale
The paper's derivation chain is self-contained. CountDistinct fixes the occurrency cutoff W = T^{2/3} and the blocklist sampling rate p = log(T^{1/3}L/β)/T^{2/3} as explicit design choices, then proves privacy by coupling COUNTING-KSET to an exact COUNTING-DICT (Lemma 2) whose sensitivity is bounded through the occurrency W (Lemmas 3, 7, 9). No parameter is fitted to the target output; the accuracy bound (Theorem 11) is obtained from independent concentration bounds (Lemmas 10-12) and not read off the algorithm's own thresholds. The space bound (Theorem 13) is a direct accounting of the KSET capacity, the binary mechanism's O(log T) space, and the bounded blocklist size. The blocklisting lower bound (Theorem 14) is an information-theoretic hardness argument over an explicit stream distribution, and it does not rely on the upper-bound algorithm's parameters, so the near-matching claim in Corollary 15 is not circular. Self-citations to [EMM+23] appear only as related prior work and are not load-bearing for the turnstile result. I note one localized proof gap that is not circularity: in Lemma 2 the bad event E2 is defined using the threshold k, while Lemma 6 bounds the corresponding event at the threshold τ; since k > τ, the stated union bound does not go through as written. This is a correctness/repair issue in the proof, not a reduction of the claimed result to its own inputs, and it does not change the circularity verdict.
Assumptions & free parameters
free parameters (3)
- W (internal occurrency bound when ob=false) =
T^{2/3}
- p (blocklist sampling probability) =
log(T^{1/3} L/β) / T^{2/3}
- γ, λ, τ, k (algorithmic thresholds) =
Analytical expressions in W, T, ρ, η, β
assumptions (5)
- domain assumption Event-level DP: neighboring streams differ in at most one update.
- domain assumption Universe size |U| = poly(T).
- standard math KSET data structure properties from Lemma 1 (based on [Gan07]).
- standard math λ-wise independent hash functions exist with log T seed length.
- standard math Binary mechanism (CSS11, DNPR10) with Gaussian noise has the claimed accuracy/privacy.
Cite this review
Pith. "Pith review of Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model." pith.science (2026). https://pith.science/paper/45EVMEI6
@misc{pith2026250523682,
author = {Pith},
title = {Pith review of: Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model},
year = {2026},
howpublished = {\url{https://pith.science/paper/45EVMEI6}},
note = {Machine review of arXiv:2505.23682}
}
abstract
The turnstile continual release model of differential privacy captures scenarios where a privacy-preserving real-time analysis is sought for a dataset evolving through additions and deletions. In typical applications of real-time data analysis, both the length of the stream $T$ and the size of the universe $|U|$ from which data come can be extremely large. This motivates the study of private algorithms in the turnstile setting using space sublinear in both $T$ and $|U|$. In this paper, we give the first sublinear space differentially private algorithms for the fundamental problem of counting distinct elements in the turnstile streaming model. Our algorithm achieves, on arbitrary streams, $\tilde{O}_{\eta}(T^{1/3})$ space and additive error, and a $(1+\eta)$-relative approximation for all $\eta \in (0,1)$. Our result significantly improves upon the space requirements of the state-of-the-art algorithms for this problem, which is linear, approaching the known $\Omega(T^{1/4})$ additive error lower bound for arbitrary streams. Moreover, when a bound $W$ on the number of times an item appears in the stream is known, our algorithm provides $\tilde{O}_{\eta}(\sqrt{W})$ additive error, using $\tilde{O}_{\eta}(\sqrt{W})$ space. This additive error asymptotically matches that of prior work which required instead linear space. Our results address an open question posed by [Jain, Kalemaj, Raskhodnikova, Sivakumar, Smith, Neurips23] about designing low-memory mechanisms for this problem. We complement these results with a space lower bound for this problem, which shows that any algorithm that uses similar techniques must use space $\tilde{\Omega}(T^{1/3})$ on arbitrary streams.
Reference graph
Works this paper leans on
-
[1]
Upper Tail: Pr[X ≥ (1 + η) · µ] ≤ exp − η2µ 2+η for all η >0
-
[2]
Lemma 5 (Chernoff Bound of Gaussian Random Variable)
Lower Tail: Pr[X ≤ (1 − η) · µ] ≤ exp − η2µ 3 for all 0 < η <1. Lemma 5 (Chernoff Bound of Gaussian Random Variable) . For X ∼ N(0, σ2), Pr(|X| > t) ≤ 2 exp(−t2/2σ2). A.2 Information theory basics We provide some basic information theory definitions and facts that are used in Section 5. In this paper, we use log to refer to the base 2 logarithm. Definitio...
-
[3]
H(X) ≤ log |supp(X)|
-
[4]
Data processing inequality: for a deterministic function f (X), I(X; Y |Z) ≥ I(f (X); Y |Z)
-
[5]
I(X; Y |Z) ≥ 0. 25 B Additional details on KSET We describe the TESTSINGLETON data structure (Algorithm 6) which is a building block of the KSET data structure in more detail. Algorithm 6 TEST-SINGLETON data structure Input: Input stream x1, x2, . . . , xT 1: Initialize m → 0, U→ 0, V→ 0 2: TSUPDA TE(xt): 3: if xt is an insertion of item i then 4: m ← m +...
-
[6]
An update operation, TSUPDATE(xt), which updates three counters — mT S, U , and V (all initialized to zero) preserving the following invariants throughout the stream: mT S= X a∈U fa, U = X a∈U fa · a, V = X a∈U fa · a2. More precisely, for an non-empty update xt corresponding to data item a, TSUPDATE(xt) performs the following update: mT S:= mT S+ 1, U = ...
-
[7]
A check operation, TSCARD(), which determines whether the TESTSINGLETON data structure: (1) is empty, (2) contains a single element, or (3) has more than a single element. The function returns, in each case respectively: (1) EMPTY (this happens if mT S= 0); (2) the triplet SINGLETON, the element, and its frequency (this happens if U 2 = mT S· V ); or (3) ...
-
[8]
ρ/L-zCDP, if ob = true
Show all 17 references
-
[9]
β/L-approximate ρ/L-zCDP, if ob = f alse. Proof. We will prove the privacy claim for the more general case when ob = f alse. Note that when ob = true, we do not need to deal with the failure event associated with blocklisting (Lemma 8) and thus β = 0 and COUNTING-DICTi (Algori...
-
[11]
That is, for all i ∈ [L], we have |Fi(t) − ˆsi(t)| ≤γ = q 4(W +1)(log T +1)3 log(10(log T +1)/β) ρ with probability 1 − β/5
BinaryMechanism-CD (Algorithm 4) is accurate (Lemma 11). That is, for all i ∈ [L], we have |Fi(t) − ˆsi(t)| ≤γ = q 4(W +1)(log T +1)3 log(10(log T +1)/β) ρ with probability 1 − β/5. 32
-
[12]
Plug- ging in β/5L into Lemma 6 yields that if Fi(t) ≤ 16 max{γ/η, 32λ/η2}, then COUNTING- DICTi will not output TOO-HIGH, i.e
For any stream i, if the correct number of distinct elements in the subtream i is below a certain threshold then COUNTING-DICTi will not output TOO-HIGH (Lemma 6). Plug- ging in β/5L into Lemma 6 yields that if Fi(t) ≤ 16 max{γ/η, 32λ/η2}, then COUNTING- DICTi will not output ...
-
[13]
In all substreams i ∈ [L], the correct number of distinct elements in the substream i by hashing, denoted Fi(t), is also a good estimator for the number of distinct elements in the entire stream at timestep t, denoted F (t) (Lemma 10). That is, for all i ∈ [L], the following t...
-
[14]
That is, for all i ∈ [L], we have |Fi(t) − ˆsi(t)| ≤γ = q 4(W +1)(log T +1)3 log(10(log T +1)/β) ρ with probability at least 1 − β/5
BinaryMechanism-CD (Algorithm 4) is accurate (Lemma 11). That is, for all i ∈ [L], we have |Fi(t) − ˆsi(t)| ≤γ = q 4(W +1)(log T +1)3 log(10(log T +1)/β) ρ with probability at least 1 − β/5
-
[15]
We plug β/5L into Lemma 6 to obtain that, if Fi(t) ≤ 16 max{γ/η, 32λ/η2}, then COUNTING- DICTi will not output TOO-HIGH, i.e
For any stream i, if the correct number of distinct elements in the subtream i is below a certain threshold then COUNTING-DICTi will not output TOO-HIGH (Lemma 6). We plug β/5L into Lemma 6 to obtain that, if Fi(t) ≤ 16 max{γ/η, 32λ/η2}, then COUNTING- DICTi will not output TO...
-
[16]
With probability at least 1 − β/5, the size of the blocklist is bounded by 3 T 1/3 log(T 1/3⌈log T ⌉/β)
The blocklist has bounded size (Lemma 12). With probability at least 1 − β/5, the size of the blocklist is bounded by 3 T 1/3 log(T 1/3⌈log T ⌉/β). Conditioned on these good events and plugging in W = T 2/3, by Lemmas 11 and 12, for each instance of BinaryMechanism-CD, the ove...
-
[17]
∀i ∈ [L] with F (t) ≥ 2i · 4λ η2 , we have (1 − η) F (t) 2i ≤ Fi(t) ≤ (1 + η) F (t) 2i
-
[18]
∀i ∈ [L] with F (t) < 2i · 4λ η2 , we have F (t) 2i − 4λ η ≤ Fi(t) ≤ F (t) 2i + 4λ η . Proof. We start with the case of F (t) ≥ 2i · 4λ η2 . Applying Lemma 4 to the Fi(t) as a sum of F (t) λ-wise independent Bernoulli (2−i) random variables, and with µ = F (t) 2i , A= η · F (t...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.