Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model
Authors: Rachel Cummings
Alessandro Epasto
Jieming Mao
Tamalika Mukherjee
Tingting Ou
Peilin Zhong
Venue: ICML 2025 poster (2025)
Keywords: differential privacy
counting distinct elements
streaming data
turnstile
continual observation
continual release
sublinear space
Primary area: social_aspects->privacy

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 $|\mathcal{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 $|\mathcal{U}|$.  In this paper, we give the first sublinear space differentially private algorithms for the fundamental problems of counting distinct elements in the turnstile streaming model. Our algorithm achieves, on arbitrary streams, $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 $O_{\eta}(\sqrt{W})$ additive error, using $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 et al. about designing low-memory mechanisms for this problem. We complement this results with a space lower bound for this problem, which shows that any algorithm that uses similar techniques must use space $\Omega(T^{1/3})$.

Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model
Rachel Cummings
11
Alessandro Epasto
Jieming Mao Peilin Zhong" 22
Tamalika Mukherjee Tingting Ou
Abstract
1. Introduction
The turnstile continual release model of differen- tial privacy captures scenarios where a privacy- preserving real-time analysis sought for a dataset evolving through additions and delctions. In typical applications of real-time data analy- sis, both the length of the stream 7 and the size of the universe [2[] 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 [t]]. In this paper, we give the first sublinear space differentially pri- vate algorithms for the fundamental problem of counting distinct elements in the turnstile stream- ing model. Our algorithm achieves, on arbitrary streams, O,, space and additive error, and a (1 + -relative approximation for all E (0, 1). Our result significantly improves upon the space requirements of the stateoff-theaat algorithms for this problem, which is linear, approaching the known /4T 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 (VWW) ad- ditive error, using O,(vW) space. This addi- tive еттог asymptotically matches that of prior work which required instead linear space. Our results address an open question posed by (Jain et al., 2023) about designing low-memory mech- anisms for this problem. We complement these results with space lower bound for this problem, which shows that any algorithm that uses similar techniques must use space 1/33 on arbitrary streams.
Data streaming applications in which one needs track specific statistics over a period of time oceur in many real- world scenarios including digital advertising, network mon- itoring, and database systems. Given the sheer volume of data collected and processed in these online settings, sig- nificant work has been dedicated to the design of efficient algorithms to track and release useful statistics about the data stream, at every timestep. key goal in this area is the design of space-efficient algorithms, i.e., algorithms that do not require storing the entire stream in memory.
In many applications, the data being collected is not only massive, but also contains sensitive and personal user infor- mation. In this case, formal privacy protections are often re- quired to ensure that the data released by the algorithm does not inadvertently leak protected information about individ- ual users. Differential privacy (DP) (Dwork et al., 2006) has emerged as the de facto gold-standard in privacy-preserving data analysis to address such concerns.
We focus on the turnstile model of continual release in differential privacy. In this model, we are given a stream x = (Ii,.... ,T)), where each iy can be an insertion (+u) deletion (-u) of some data item from a fixed universe u. 1 (no update). and the goal is to release statistic of interest at every timestep E [T]. in differentially private manner. An algorithm A is (s, 8)-differentially private if for any neighboring input streams x ~ x' and any output set O,
Pr[A(x) E O] Pr[A(z') 0
In the continual release model, the output A(x)) refers to the entire output history of the algorithm A over stream at every timestep. We consider event-level privacy, i.e., the input streams x ~ x' are neighboring if they differ in at most one timestep.
'Department of Industrial Engineering and Operations Re- search, Columbia University. New York, USA "Google Re- scarch, New York, USA. Correspondence to: Tamalika Mukherjee <tm3391 @cllumbia.cdu>.
In this paper, we study the fundamental problem of count- ing distinct elements in the turnstile model under continual release. Starting from the seminal works of (Flajolet & Mar- tin, 1985; Alon et al., 1999), there is a rich literature of low space algorithms for the problem of counting distinct ele- ments in the non-DP streaming world (c.g.. see references within (Muthukrishnan, 2005)).
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

DP Space-Efficient Algorithm for Counting Distinct Elements
While space-efficient DP algorithms for this problem have been recently studied in the (1) one-shot model (where the algorithm produces an output once at the end of the stream) (Pagh & Stausholm, 2021; Wang et al., 2022; Dick- ens et al., 2022; Hehir et al., 2023; Smith et al., 2020; Stano- jevic et al., 2017; Braverman et al., 2023; Blocki et al., 2023), and (2) insertion-only continual release model (where the algorithm outputs every timestep, but no deletions are allowed) (Epasto al., 2023; Dwork et al., 2010; Chan et al., 2011; Bolot et al., 2013; Ghazi et al., 2023), the existence of a private space-efficient algorithm in the more general turnstile model under continual release has been largely unexplored. Notably, even without any space constraints, recent work (Jain et al., 2023) has shown that designing DP algorithms for this problem in the general turnstile model more challenging and can incur significantly more addi- tive error, i.e. polynomial in T in the turnstile model vs. polylogarithmic in T in the insertion-only model. Under- standing whether this fundamental problem can be solved in the turnstile model under continual release with reasonable accuracy and efficiency is an open problem. We address this gap by presenting the first sublinear space algorithm (sublinear in T and (((() for counting distinct elements.
efficient DP algorithms for counting distinct elements with error and space that scales with the maximum occurrency.
Definition 1.1 (Occurrency). Given a stream æ and an ele- ment u E U, the occurrency of u in æ, denoted occur(u, x), is the number of times an element u appears (either as inser- tion or as deletion) in the stream æ. The occurrency of the stream x. denoted W.. is max occur(u,
We remark that for any stream I of size T, W. S. T; how- ever, in many instances, the occurrency is much smaller, and can be as low as T / [24] For example, consider the case of an online learning platform that wants to estimate the num- ber of activities being actively performed the moment by users. A user can begin one activity (e.g., initiating an home- work assignment for course) and then terminate it when they are done (e.g., completing the assignment). Each event in this example stream represents intiiaiions/termiattioon of a given activity (where +- is an initiation of an activity u, and -u is a termination). In this case, occurrency can be bounded by twice the maximum number of students in a class, which clearly < T (total number of events).
In this paper, we first design DP algorithm for counting dis- tinct elements that, when provided with stream promised to have occurrency bounded by W, has an error and space that scales as a function of the promised bound W. When a bound on occurrency is known, as in the example above, this first algorithm can be used as and will satisfy DP guarantees. However, in many cases an occurrency bound may not be known. For this reason, we also design more general algorithm that for an arbitrary stream of unknown occurrency, imposes a bound on occurrency for a subset of the stream. Combining these results, we prove our main result: a low-space algorithm with unconditional DP guar- antees for arbitrary streams - i.e., the algorithm is truly private in the sense of (Jain et al., 2023). Finally, we give a matching space lower bound showing that any algorithm us- ing technique based on bounding occurrency (or flippancy) cannot hope to achieve better space bounds.
For counting distinct elements in an input stream x under continual release, one strategy used by prior work (Epasto et al., 2023; Jain et al., 2023) is to approximately track the summation over the stream Sn E 1," with the binary tree mechanism (Chan et al., 2011; Dwork et al., 2010), where (t) is the difference in the number of dis- tinet elements at timestep L. --1 1 and f. Note that Eige &a (i) precisely gives the number of distinct elements at timestep t. In the insertion-only setting, it is easy to observe that the sensitivity of the summation stream 8z is bounded by a constant (Epasto et al., 2023; Bolot et al., 2013). In the turnstile model, (Jain et al., 2023) observed that a change in the stream can cause (?(T)) changes to the corresponding summation stream s.- In particular, the sensitivity of the summation stream s in the tursstiee model depends on the number of times an input stream item switches between be- ing present to absent or vice versa- - this property is called the flipancy of the item. (Jain et al., 2023) designed DP algorithms for counting distinct elements where the additive error scales with the flippancy of the stream, denoted Wa (i.e., maximum flippancy over all items in the universe for a fixed stream). More specifically, the algorithm imposes (provable) bound on the maximum flippancy of the stream.
1.1. Our Contributions
The main result of our paper is the design of the first sublinear space DP algorithms for the problem of count- ing distinct elements in the turnstile model under contin- ual release. Before presenting our results, we first define some useful notation and terminology. We say e is an (a, appppoooiinn of a function f on input stream x if (()) - 3 & v S af(x)) + B.
However, flippancy is ill-suited to design low-space algo- rithms due to its inherently stateful nature (i.e., whether an element flips at time t depends on all prior events of that element). For this reason, we introduce the related, but stateless, notion of occurrency (see Definition 1.1) which measures the maximum number of times item appears in the stream. Using this occurrency measure, we design space-
We first present a DP algorithm for the problem of counting distinct elements, where the input stream has promised
In this simple example, for clarity, we assume a user can only participate in the activity once. Our algorithms make such assumption.
2

---

DP Space-Efficient Algorithm for Counting Distinct Elements
upper bound on its occurrency. In such cases, our DP algo- rithm achieves space and error guarantees that only have sublinear dependency on occurrency stated below.? ?
distinct elements with no assumptions on the occurrency of the input stream. Our algorithm uses the blocklisting tech- nique described above with the optimal choice of occurrency W₂ = T combined with the KSET data strucure to achieve sublinear space and non-trivial additive error.
This algorithm utilizes low-space dictionary data structure denoted KSET, which was introduced by (Ganguly, 2007) to estimate the number of distinct elements in the non-DP turnstile streaming setting. KSET supports the insertion and deletion of data items and returns (with high probability) the set of items S present in the dictionary as long |S] I k. If the number of elements exceeds k or there is collision where two elements are assigned the same cell in the KSET, then it "fails" by outputting NIL.
Theorem 1.4 (Main (Informal), Corollary 3.2). For all E > 0 and ā E (0, and streams of length T E N. there exists an (s, 6D-D algorithm in the turnstile model under continual release that outputs a (1+n, O,,6.n (T) approximation to the number of distinct elements in the stream, using space 0n
Theorem 1.2 (Informal, Corollary 3.1). For all E > 0 and 8 E (0, 1) and streams of length T E N, given a promised occurrency bound of Wz. there exists an (s, DP algorithm in the turnstile model under continual re- lease that outputs a (1+ n, Oe (VV))) ( approximation to the number of distinct elements in the stream, using space Ō 0,,6.n(VV)
Comparison to prior work. We observe that our results are the first to address the open question posed by (Jain et al., 2023) regarding the existence of accurate, private, and low-memory mechanism for counting distinct elements in turnstile streams. When the stream has a promised flippancy bound W2 rather than promised occurrency bound, the informal Theorem 1.2 (and the formal counterpart Corol- lary 3.1) can be restated equally in terms of the flippancy of the stream. More precisely, our algorithm provides a ( + 7 multiplicative approximation with ,,,8 (v /w,)) ad- ditive error, using space Ōz,5.n ( This additive er- ror matches (neglecting lower order terms) the additive er- ror O₂ (min( vwz, T2/3)) in the algorithm of (Jain al., 2023)* which is achieved however with (2(T) space. (This is because for the regime of wa 2 T2/ one can use the unbounded occurrency algorithm in our paper to obtain ad- ditive error Oe...((T1//)) (T). When flippancy is unbounded, our additive error is always Oc.d.,, (T1/3). This is close to the lower bound of ft (T)/4) from (Jain al., 2023) for pri- vate algorithms for the problem in streams of arbitrary large flippancy. Closing this gap is an interesting open problem.
We remark that in this result, DP is guaranteed only when the input streams do not violate the promised occurrency upper bound. Our next result allows us to remove this assumption and provide a DP algorithm for streams with unbounded occurrency by creating blocklist of high occurrency items to effectively ignore them in future timesteps. Before pre- senting our main result, we first define the problem of block- listing high occurrency items and show a near optimal space algorithm for this problem.
Let blocklistoce () be the problem of outputting 0 at timestep i when the current input element has occurrency < W (up to the step before), and otherwise. An algorithm for solving blocklistace.. (W) reports a false negative if the element at timestep t has occurrency 2 W but the algorithm outputs 0; it reports a false positive if the element at timestep t has occurrency < W but the algorithm outputs 1.
1.2. Related Work
Our work on designing space-efficient turnstile streaming algorithms in the DP continual release setting is related to several topics in the areas of (non-private) space-efficient streaming algorithms, DP continual release, and DP stream- ing algorithms. Additional related work can be found in Appendix A.I.
Theorem 1.3 (Informal, Corollary E.3 and Theorem E.2). There exists an algorithu that, with high probability, has no false negatives and bounded false positives for blocklistoce (W) and uses space (T). Moreover, for any W > 0, any algorithm that solves blocklist (W) with the same false positive bound (and no false negatives) needs space ((T/W))
Space-efficient streaming algorithms. The streaming model of computation (Flajolet & Martin, 1985) is well- known abstraction for efficient computation on large-scale data. In this model, data are received one input at time, and the algorithm designer seeks to design algorithms that compute a solution on-the-fly fly while using limited space and time. In the area of non-private computation, a vast literature
This space lower bound applies to any algorithm (even ex- ponential time ones) and implies that the space bounds achieved by our final algorithms are optimal up to log factors (among algorithms using the blocklisting approach).
Finally, our main result gives a DP algorithm for counting
We omit the proof for simplicity as it follows the same steps as our proof in terms of occurrency. "Sublinear space requires a multiplicative approximation factor in our algorithm.
"We present our informal results in terms of (s, 6DP however formal theorems stated in terms of p>CCDP. We can use Theorem A.2 to convert p-zCDP to (c, DDP.
3

---

DP Space-Efficient Algorithm for Counting Distinct Elements
has been developed over the past decades (Morris, 1978; Flajolet & Martin, 1985; Flajolet et al., 2012; Alon al., 1996) for addressing variety of problems ranging from classical streaming computations (such as heavy hitters and frequency moments) (Flajolet & Martin, 1985; Flajolet et al., 2012; Durand & Flajolet, 2003; Cormode & Muthukrishnan, 2005; Misra & Gries, 1982), to solving combinatorial opti- mization problems (McGregor & Vorotnikova, 2018; Huang & Peng. 2019; Charikar al., 2003). Two key questions in the literature are whether it is possible to obtain space sublinear in the number of updates (Flajolet et al., 2012) and whether it is possible to handle increasingly more dy- namic updates (i.e., insertions-only sliding window (Datar et al.,, 2002), and fully-dynamic streams (McGregor & Vorot- nikova, 2018)). In the (non-private) streaming literature, there is well-developed theoretical understanding for in- terplay between the dynamicity of the stream, the accuracy achievable, and space bounds required, for a vast array of algorithmic problems (Woodruff, 2004).
from the universe requires ((log(((1)) log(T)) bits.
First, we recall the definition of differential privacy (DP) on streams. Neighboring streams x and x', denoted x ~ x', differ in the stream elements at most one timestep.
Definition 2.1 (Differential Privacy (Dwork et al., 2006)),
Given privacy parameters 5 > 0 and ò [0, 1), an algorithm A is (e, 8)-DP if for any neighboring streams ~ x and any output set O, Pr[A(x) E O S e Pr[A(x') O + 8.
When 6 = 0, this is known as pure DP, when ā > 0 and it is known as approximate DP. In the continual release setting, the output of A(x) is the entire T-length output over the stream x at every timestep.
Our privacy analysis will primarily use sero-concentrated differential privacy (zCDP), which is a slight variant of the standard DP definition. We present the definition of zCDP, its composition properties, and its relationship to (c, 6)D in the one-shot setting, where the entire stream is processed and only one output released at the end of the stream.
DP turnstile model. All previously mentioned work does not consider the fully dynamic streaming setting, where items can also be removed from the stream. The DP turnstile continual release model is the private equiva- lent of the fully-dynamic streaming model, and has re- ceived substantially less attention in the literature. Count- ing distinct elements in the turnstile continual release model was only recently studied for the first time by (Jain et al., 2023). For a stream with flippancy bound w, they give an (E, (PPP mechanism with additive error O poly (T)))o and space S(T)). They also show lower bound of Q(min (w, T) on the ad- ditive error for any DP mechanism for this problem. In concurrent work, (Henzinger et al., 2023) also studied this problem under a restricted variant of the turnstile model where items are guaranteed to be present with cardinality at most at any time (i.e., multiple insertions of the same element are ignored). For this setting, they give an (e, O)-DP algorithm with additive error Ö(VE-1 e K IT)) where K is the total number of insertions and deletions, and nearly matching lower bound. Contrary to the non- con-private litera- ture, theoretical understanding of space efficiency in private dynamic streaming algorithms is very limited. No prior work has designed differentially private sublinear-space al- gorithms for the foundational problem of counting distinct elements in the tursstle continual release model.
Definition 2.2 (zero-Concentrated Differential Privacy (zCDP) (Bun & Steinke, 2016)). Given privacy parameter P > 0, a randomized algorithm A satisfies p-zCDP if for all pairs of neighboring streams x ~ x' and all a > 1,
Da Da(A(z))(A(z') S par
where (PIl)) = - log (Fawr P(y
is the Renyi divergence of order a between probability distribu- tions P and Q.
Q0y-o1
There is also a relaxation of zCDP, known as approximate zCDP, which is analogous to the relaxation between pure DP and approximate DP.
Definition 2.3 (Approximate zCDP (Bun & Steinke, 2016)). Given privacy parameters p > 0 and ő E (0, 1). random- ized algorithm A satisfies 5-approximate p-zCDP if for all pairs of neighboring streams x ~ x', there exist events E (which depends on A(z)) and E' (which depends on A(x')) such that Pr[E] N 1 - 6, Pr[E"] 2 1 5, and for all a E (1,)
pa V (a(A(t ((A))le)) s pa. Da (A(()))
where A(z) E is the distribution of A(z) conditioned on E.
The privacy parameters of zCDP compose, similar to the composition guarantees of DP, and it is possible to translate between the guarantees of zCDP and DP. Both of these are shown in Appendix A.2, along with other additional details zCDP.
2. Preliminaries
We consider an input stream Ti,..., Fr of length T, com- ing from universe U. such that each x; E U {1}. We assume that U = (T)y as is standard in streaming literature (Chakrabarti, 2012). This assumption allows for simplified lower bound on space, since storing single item
3. Estimating the Number of Distinct Elements
In Section 3.1, we first present our DP algorithm (Algo- rithm 1), which outputs an approximation of the number of
4

---

DP Space-Efficient Algorithm for Counting Distinct Elements
distinct elements in the stream in a continual release manner. We then present our main results for this algorithm in Sec-
Algorithm 1 CountDistinct
Require: Stream 21,...,227 E U. relative error 1) E
tion 3.2, namely its privacy, accuracy, and space guarantees, will details of the analysis deferred to Section 4.
(0, 0.5), privacy parameter P failure probability B. boolean ob that signals if we have an occurrency bound on elements, occurrency bound W
3.1. Algorithm and Description
1: Let L f- [Tog(T)], À < 2 log
2: if ob is true then
Our algorithm CountDistinct (Algorithm 1) for counting the number of distinct elements in stream uses three main ingredients: (1) a KSET data structure which we use to store distinct elements from the stream z with low space, (2) a binary-tree mechanism BinaryMechanism- CD for estimat- ing the summation stream $2 (t) E {-1,0, 1)" which we obtain by comparing the cardinality of the distinct element set returned by the KSET data structure timesteps and t. and (3) a blocklist B which with high probability, stores all items whose occurrency is too large.
7 V 4/W 41W++)00g 7+ log( l0 7
4: else
(122/441(logT++ log (10[log (ouu(oogT400 T+1)/8)
5:
7
37 log(T) (T1/3 [3og 71/3)
6: end if
7: Let : u + [L] be A-wise independent hash func- tion; for every E u. i E [L]. Pr(g(a) = 2- Pr(g(a)=1]=2) 2-L
8: Initialize empty streams ,,,..., , S₁ (S, is the stream of noisy distinct counts and TOO-HIGHs) Initialize COUNTING-KSET, ...... COUNTING-KSET with occurrency bound W if ob true or occurrency bound T2/3 if ob false
At a high-level, CountDistinct executes the following pro- cess on different subsamples. At each timestep E [T). if the data element 22 is non-empty, then the COUNTING- KSET subroutine updates the KSET data structure with .r. and obtains the current set of distinct elements from the KSET (if the KSET does not fail; we discuss later how to deal with failures in the KSET as this case requires more care). If the item corresponding to x4 is present in the block- list B, then the COUNTING-KSET subroutine does not update the KSET data structure with Te. Next, the algo- rithm computes (t) to be the difference in counts between the current distinet elements set and the previously stored set, and feeds sz (f) into BinaryMechanism-CD. which produces a differentially privat count of the number of dis- tinct elements 2 (t). Finally 82 (t) is compared to a fixed
10: Initialize blocklist B = 0
11: for update 24 do
12: for i E [L] do
13: if x4 * and g(2,) = then BIEIING--SST,..ppaae B)) {see Algorithm 2}
14:
S
15:
if xt & B and ob is false then
16:
Add It to B with probability p
log(T1/3L/8)
72/3
17:
end if
18:
else
threshold r. If 8z (t) is greater than т, then COUNTING- KSET returns TOO-HIGH, otherwise it returns & (t) to the main algorithm. The algorithm then performs the block- listing step. which adds the current item to the blocklist B with probability high occurrency are not likely to be considered by our algo- rithm in future iterations. This process is executed in log( parallel instances of COUNTING-KSET with different sam- pling rates using hash function, in order to ensure that at least one sampling rate yields good approximation to the number of distinct elements.
19:
S:(1] COUNTING-KSET B)
{see Algorithm 2}
20:
end if
21:
end for
this ensures that the elements with
22:
Output: St(t] 2 for the largest i E [T.]
such that S.[t] is not TOO-HIGH and S. >
max(y/n, 32\/n²}. (If such i does not exist, output
0.)
23: end for
More concretely, Algorithm 1 takes in boolean flag ob as input, indicating whether there is a promised bound on the occurrency of the stream- - if ob is true, the algorithm will operate under the assumption that the input stream has an occurrency upper bounded by W. and thus does not employ the blocklisting technique. If ob is false, the algorithm imposes an internal bound of W T2/3 and executes the blocklisting procedure, in which it fixes a sampling probability p (in Line 16), and every time an element occurs, the element is sampled with probability p to be stored in a
blocklist B.
Algorithm 1 uses a hash function to generate multiple par- allel substreams i E [L] of the input stream (see Line 7) where L [log(2']] all subsampled with different sam- pling rates. The different sampling rates ensure that at least one sampling rate will yield good approximation of the number of distinct elements in the original stream.
For each instance, i E L, Algorithm initializes the DP subroutine COUNTING-KSET; (Algorithm 2), which uses two key subroutines:
5

---

DP Space-Efficient Algorithm for Counting Distinct Elements
Algorithm 2 COUNTING-KSET
tine is used to privately count the sum of the differ- ence in the count of distinct elements between consec- utive timesteps. The mechanism is an extension of the Binary Mechanism (Chan et al., 201 I; Dwork et al., 2010); however, the major differences are that it uses Gaussian noise (similar to (Jain et al., 2023)) and the input {-1, O, 1)² (as opposed to {0, 1)² in the orig- inal). Although the BinaryMcchanism- CD algorithm is similar to prior work, its privacy analysis needs be handled carefully in our use-case, as it is closely tied to the failure behavior of the KSET. Additional details are deferred to Appendix B.2.
Require: Stream update #1,..., #T E U, relative error ? E (0, 0.5), privacy parameter p. failure probability 3,
substream index i, occurrency bound W on elements,
blocklist B
1: Initialize
16 1amaax1///) 3///n)2
2/2 (log 1 T+112/ WW log(207
vp
2: Initialize
k
16 16 32A/n7²)
4 (2( 14) /w log(20X (1/8)
vp 3: Initialize BinaryMechanism-CD, with parameters: privacy parameter p/ I. and occurrency bound W
4: Initialize KSET, data structure with parameters: capac-
ity k and failure probability (2TLL)
COUNTING-KSET, (Algorithm 2) takes as input 2, and updates the KSET data structure with I; (as long as z is not in blocklist B or equal to ). If the KSET, does not fail, then COUNTING-KSET updates BinaryMechanism- CD; with the difference of the distinct sample size at time and the distinct sample size at the last timestep before baat < (Line 26) that the KSET did not fail. Then BinaryMechanism-CDD outputs the noisy count of distinct elements, denoted &; If the KSET does fail, i.e., S; NIL, then COUNTING-KSET, skips to Line 28 which returns TOO-HIGH if the KSET fails, or & exceeds the threshold k. Note that this step is crucial for proving that COUNTING- KSET, is DP, which is presented more detail in Sec- tion 4.1. We note that COUNTING-KSET, does not take as input the flag ob, because if ob true, then B = 0 in Algorithm 1, so taking B as input is sufficient.
5: Initialize Fttt = 0, flost" =
6: Update(2;; B)):
7: for update Hy do
8: if x, #1 and 2, & B then
9: UpdT::))
10: end if
11:
Let S: <
{Only keep the ele-
ments but not their counts }
12:
S, NIL then
13:
tail = - flast
14:
diff = |S.| Fastst
for j = 1 |diff] do
16:
if diff 0 then
17:
8; --Binayllechannss-DDD..ppaaalll
18:
else if diff < 0 then
19:
8;
20:
end end for for j
Finally, Algorithm maintains a stream of noisy distinct counts or instances of COUNTING-KSET, instance. These streams are used to output [ 2' such that S:]t] not TOO-HIGH in Line 22, which is the private count of distinct elements in the i-th stream at time I, normalized by (the inverse of) that stream's 's sampling rate. This final count is output for all times 1 E [T].
denoted S, for each of the log T
21:
22:
1 tdift - diff| do 8, --Biarr/Mechhniimm-CD..ppplall
23:
24:
end for
25:
Save Fatt + |S:1
26:
/ast =1
27:
end if
28:
if 6,
> 7 or S; =NIL then
Return TOO-HIGH
3.2. Main Results
30: else
In this subsection, we present our main results: Corollary 3.1 and Corollary 3.2, which summarize our main results on the privacy (Theorem 4.1), accuracy (Theorem 4.5), and space (Theorem 4.7) of Algorithm summarizes our main results when there is promised upper bound the occurrency of the input stream.
31:
Return 9;
32:
end if
33:
end for
Corollary 3.1 first
1. KSET (Algorithm 4): The k-set structure is dictio- nary data structure that supports insertion and deletion of data items and either returns, with high probability, the set of items S that present in the dictionary if |S| < kt or returns NIL (failure condition). Additional details are deferred to Appendix B.I.
and B E (0, and stream of length T, universe size [2a| poly(T), and promised occurrency S W, there exists a @-approximate p-zCDP algorithm in the turnstile model under continual release that, with probability at least 1 233 outputs a a + n, max{O( ((2/1?))) ())))))))ppprimmmatt apprrxximation to the number of distinct elements using space O(VW polylog(T///
Corollary 3.1. For all T
2. BinaryMechanism-CD (Algorithm 5): This subrou-
6

---

DP Space-Efficient Algorithm for Counting Distinct Elements
poly( pn) where ? = 0 = ((log(oog(T)/3))
W (logg) log(log T/8)
and
TOO-HIGH. Note that COUNTING-DICT is not space- efficient, and we only introduce it for analysis purposes. In COUNTING-DICT, the sensitivity of Sæ can be bounded in terms of the maximum occurrency W for all timesteps. We then use the coupling argument to bound the sensitivity of sy in COUNTING-KSED for all timesteps (barring spe- cific bad events whose failure probability is negligible and absorbed into the DP failure probability..
The next result (Corollary 3.2) summarizes our theoretical guarantees when the stream has unbounded occurrency.
Corollary 3.2. For all q and a stream of length T and universe size [u] (oly(T). there exists a 23-approximate p-zCDP algo- rithm in the turnstile model under continual release that, with probability at least 1 - 23 outputs a (1 = to the number of distinct elements using space O(T polylog([)) (T/ ()) [log Tya log[logT/3
O and B E (0,1),
Algorithm 3 COUNTING-DICT
Require: Stream ,1,...,,7 2T E U. relative error 1) E
(0, 0.5), privacy parameter Pa failure probability B, occurrency bound W on elements, substream index i, list of blocklisted elements B
n, max (O(x/)))
poly( mn) where ? 0 T
and
1: Let 8,
0 and 2/2 (log T +1) VW log(20r 71/B)
16 max 32X/11² +
P
A = O(log(log(T)//3))
2: Initialize BinaryMechhnism--C0
with parameters:
4. Analysis of CountDistinct
privacy parameter p/ I. and occurrency bound W
3: Initialize DICT, dictionary data structure of size (24) xT
This section presents details of the privacy (Theorem 4.1), accuracy (Theorem 4.5) and space (Theorem 4.7) guarantees of Algorithm 1. Omitted proofs are in Appendix D.
4: Initialize Fi.last =0
5: Update(11, B):
for update 24 do
if 24 + and H, $ B then 8: if 24, is an insertion then
4.1. Privacy
9: DICT, [ma][(] DICT, [2x) 1] +]++1
First we present the privacy analysis, showing that Count-
10:
else
Distinct (Algorithm 1) is differentially private. One key challenge in the privacy analysis is to ensure that the out- put of the KSET data structure does not leak privacy, even in the event of its failure (i.e., if more than k distinct ele- ments are stored). Note that if the KSET never failed, then one could simply sum up the difference in the output sizes of the KSET over consecutive timesteps, i.e., the stream
11:
DICT, [x.][]]] = DICT, [ 1]
12:
end if
13:
Let 8, <
Eueu IDICT -Binayllchhnnsn--ouuudddddd
14:
8;
Fiitst)
15:
Save Fijtst 5;
16:
else
8, E 13" using BinaryMecchanss--CD. Assum- ing no failures, the sensitivity of s can be bounded in terms
17:
end -BinaayMechanismmCD.uuuaaaoo
8; +
18:
of the maximum occurrency W, since in this case the KSET returns exact counts. However, the failure of KSET cannot
19:
if & > T then
20: Return TOO-HIGH
be avoided or absorbed into the parameter because the KSET will fail with probability I when its capacity exceeds (see Lemma B.
21:
else
22: Return 8;
23: end if
We address this challenge by modifying the original KSET algorithm to have well-behaved failures. More precisely, we introduce thresholding step where our algorithm returns TOO-HIGH if the KSET fails or approaches a regime where failing is a likely event. The latter can be estimated privately by verifying whether the binary tree output too large, 8, > T, and returning TOO-HIGH if so (see COUNTING- KSET, Algorithm 2).
24:
end for
We present the main theorem of the privacy guarantee below. The proof requires showing that the output stream published by COUNTING-KSET is DP (see Corollary 4.4), which is argued by showing that the outputs of COUNTING-KSET and COUNTING-DICT, are identical except with proba- bility at most 3 (see Lemma 4.2). Since all the operations after calling the subroutine COUNTING-KSET, in Lines 14 and 19 of Algorithm is post post-processing, we will have shown that CountDistinct is approximate zCDP (see Defi- nition 2.3) in Theorem 4.1.
By doing so, we can make coupling argument between our algorithm and a much simpler algorithm (COUNTING- DICT, Algorithm 3) that simply stores the exact counts of elements and computes & via BinaryMechanism-CC and has the same thresholding step: if å, > T, return
Theorem 4.1. CountDistinct (Algorithm 1) is
7

---

DP Space-Efficient Algorithm for Counting Distinct Elements
1. 3-approximate p-zCDP of true,
We emphasize that the privacy argument for the BM- Count-Distinct; instance in COUNTING-DICT, cannot be directly applied to the BM-Count-Distinct, instance in COUNTING-KSET: This is because in COUNTING- KSET, the output of the KSET is used to compute the input stream to (Count-Distincts and failures of the KSET can lead to a large difference in the outputs of BM- Count-Distinct, on neighboring streams. Thus the failure behavior of the KSET must be handled carefully in the privacy analysis. Corollary 4.4 gives the resulting privacy guarantee for COUNTING-KSET,
2. 13-aaproximate p-zCDP if ob- false.
To prove Theorem 4.1, we first establish that the outputs of COUNTING-KSET, and COUNTING-DICT are identical with high probability (Lemma 4.2, proven in Appendix variant of CountDistinct
D.I). Define CountDistinct' WANTING-KSETT (Algorithm 2) in Line 9, Line 14, Line 19 with calls to COUNTING-DICT; (Algorithm 3) for i E [L].
that replaces calls to
Lemma 4.2. Fix the randomness used across runs of Count- Distinct and CountDistinct'. Fix i E [L], and let K and E denote the oulput distributions of COUNTING- KSET; and COUNTING-DICT, respectively. If l Z T+ O polylog(T]
Corollary 4.4. COUNTING-KSET (Algorithm 2) is (!) (p/ L)DD) if ob true, and (2) -Jppproxiiit (p/ L)-CDD if ob faase.
JP then the total variation distance of the two distributions, drv (K, E) S B/L.
Proof. From Lemma 4.3 we know that COUNTING-DICT;
is L/L-approximate p/ L-ZCDP. In particular, for ob = true, COUNTING-DICT, is p/L-zCDP. From Lemma 4.2, we know that the output distribution of COUNTING-DICT, and COUNTING-KSET, is identical except with probabil- ity B/L. The claims for when ob true ob false follows.
To prove that COUNTING (Corollary 4.4), we first show that COUNTING-DICT, sat- isfies differential privacy (Lemma 4.3).
is differentially private
Lemma 4.3. COUNTING-DIOS (Algorithm 3) is pf L- zCDP, ob true, and is B/ T-approximmate pf L-ZCDP, if ob = false.
We are finally ready to prove Theorem 4.1.
The full proof of Lemma 4.3 in Appendix D.2; we pro- vide a proof sketch here to highlight the key ideas. Re- call that COUNTING-DICT; uses a dictionary data struc- ture DICT to store the counts of the elements seen in the stream, and the difference in the number of distinct ele- ments is exactly computed from DICT and fed as input to BM-Count-Distinct, which outputs a noisy distinct ele- ment count 8; Thus, in order prove the privacy guarantee of COUNTING-DICT;
Proof of Theorem 4.1. We first argue about the case when ob = false as this is the more general case.
The randomness of CountDistinct can be viewed as a joint probability distribution Rep = R2 x RR.. X RKc, x X RKC, where R, denotes the randomness from pick- ing hash function g (in Line 7 of Algorithm 1), RBL denotes the randomness associated with sampling an el- ement to add to blocklist B (in Line 16), and Rxc, de- notes the randomness from the subroutine COUNTING- KSET, for i E [L]. Similarly, the randomness of Count- Distinct can be viewed as a joint probability distribution RoD = R, x RBL x REC, x... X REC, where R2 denotes the randomness from picking a hash function g. REL denotes the randomness associated with sampling an element to add to blocklist B and REC, denotes the random- ness from the subroutine COUNTING-DICTY for i E [4].
need to show that BM-Count- Distinct; is DP. Then the output of COUNTING-DICT; will simply be post-processing on the DP output of BM- Count-Distinct; (either &; or TOO-HIGH), so it will also be DP. Hence, we prove that BM-Count -isttnt, when used in COUNTING-DICT, is B/ Lappooooeee p/ L-zCDP (in Lemma D.4), which implies Lemma 4.3.
We next sketch the proof of Lemma D.4, that COUNTING- DICT, is p/ L-ZCDP. On high-level, we need to argue that if x and z' are neighboring streams, then the resulting streams (after hashing and blocklisting, see Definition D.2) that are fed as input to BM- RM-Count--De -istinnt can differ in at most W positions with probability 1 B/L, for occurrency bound W T2/3 (see Lemma D.6). Opening up the analysis of the binary tree mechanism in BM-Count- Distinct; we show that the sensitivity of the nodes over all levels of the binary tree is at most 2 ( / + (Tog("T) + 1). Thus adding Gaussian noise proportional to this quantity to each node of the binary tree preserves p/ L-ZDDDP with probability 3/T.
We first define an identity coupling over the randomness Rg of picking the hash function and the randomness REL of blocklisting between CountDistinct and CountDistinct.. In other words, we fix the same hash function g and the same sampling rate to blocklist an item for CountDistinct and CountDistinct'. Applying Lemma 4.2, have that the outputs of COUNTING-KSET, and COUNTING-DICT; are identical except with probability B/L. In particular, from Corollary 4.4, we have that COUNTING-KSET, is 2,3 L-approximate p/ LLZDCD.. Since we have a total of I. substreams, using a union bound argument, the entire
8

---

DP Space-Efficient Algorithm for Counting Distinct Elements
CountDistinct algorithm is 2/3aaproximmaee p-zCDP by basic composition of zCDP (Theorem A.I).
(1 + 4n, 32 (1x, -apprximiiin of F(I) any 1) E (0,0.5).
In the case when ob- = true, note that we only have to con- sider the identity coupling of over hashing items using hash function in CountDistinct and CountDistinct'. The claim that the outputs are identical except with probability 3/ L follows from Lemma 4.2. But now, from Corollary 4.4, we have that COUNTING-KSET, is 3/ L-approximate p/ zCDP, and the rest of the argument follows from a union bound and composition.
With this, we can finally prove Theorem 4.5, by showing that substituting COUNTING-KSET in place of COUNTING- DICT still allows high accuracy of Algorithm 1.
Proof of Theorem 4.5, We apply a union bound argument that combines Lemma 4.2 and Theorem 4.6. By Lemma 4.2, we can link the accuracy of COUNTING-DICT, to that of COUNTING- and with probability at least 1 B, the output distributions of all the I. instances of COUNTING- DICT, and COUNTING-KSED the same. Furthermore, Theorem 4.6 gives desired accu- racy with probability at least 1 - 3 for Algorithm I with COUNTING-DICT: Thus, by a union bound over the two events that (1) the output of COUNTING-DICT. matches the output of COUNTING-KSET, for i E [L] and (2) COUNTING-DICT, is accurate.
4.2. Accuracy
used in Algorithm 1 are
We present our main accuracy theorem in Theorem 4.5. Our accuracy theorem is also parameterized by the value of the boolean flag ob and gives different error/space trade-offs according to whether ob is true or false. In particular ob is true, meaning our algorithm is promised that the occurrency of input streams bounded by W. then we get additive error only that has VW dependency. If ob is false, then our algorithm makes assumption the occurrency of the input stream and therefore incurs higher additive error. Omitted accuracy proofs are in Appendices D.3 and D.4.
4.3. Space Complexity
Finally, we present the space guarantees of our algorithm be- low. As with the privacy and accuracy result, Theorem 4.7 is parameterized by the value of the boolean flag ob. When ob is true and the input stream is promised to have occurrency bounded by W, the space is only polynomial in W. When ob is false, the algorithm allows general input streams, and internally enforces a bound 2 on the stream's ''s occurrency using blocklisting, which requires more space. We defer the proof of Theorem 4.7 to Appendix D.5.
Theorem 4.5 (Accuracy of Algorithm 1). Let F(t) be the correct number of distinct elements of the stream at time t and let x- = 2 log( 40 (oT)))))))BB) When ob=true, let ? = V [1 T 1-1) (og()
when ob=false, yet-= 4(72/841](log 11 (10 T 1+//8)
P
// log T1/B). For fixed timestep t E [T]. with probability at least 1 1-22 28, the output of Algorithum I at
time is a (1 + 4n, 32 max((1/) (tt////.//////// 32X/11) 1)) "apppoxximation of F(t) for any 17 E (0,0.5).
Theorem 4.7. With probability at least 1 1- 3,, assuming the universe size [24] poly(T): If ob is true, the space com- plexity of Algorithm is O(VW Be/WWpollyee poolyoogT//)) -pollppoop(p p If ob is false, the space complexity of Algorithm I I"is O polylog(T/ poll( (m))
To prove Theorem 4.5, we use three helper lemmas, all proved in Appendix D.4. Lemma D.7 bounds the number of elements in the substream after hashing. Lemma D.8 proves the accuracy of BinaryMechanism-O0 CD algorithm. Lemma D.9 bounds the size of the blocklist when ob is false. With the help of these lemmas, we can show the accuracy of COUNTING- as an intermediate step in the analysis. The proof of Theorem 4.6 is deferred to Appendix D.3.
5. Conclusions
In this paper we designed the first space-efficient differ- entially private algorithms for the count distinct element problem in the turnstile model. This result addresses an open question of (Jain et al., 2023), showing that it is possi- ble to design a low memory DP algorithm for this problem in the turnstile setting. While we show that any algorithm that uses blocklisting techniques cannot do any better in terms of space, an interesting open question to prove un- conditional space bounds for any DP continual release algo- rithm addressing the problem (regardless of the techniques used). The current theoretical understanding of space lower bounds in the DP streaming setting is very limited. Only recently (Dinur et al., 2023) gave the first space DP lower bound for any problem, under cryptographic assumptions; any future progress in this direction would be interesting.
Theorem 4.6. Let F(t) be the correct number of distinct elements of the stream at time I. and let A = (lg(4)))) When ob is true, let y /4(W+1)(log T+1 11 T+1)/8) and when ob is false, lety= = 4 1000g (log T 113 log((10((ggg T+ 11/8))
3/3 1o [log (13)) For a fixed timestep t E [T].
with probability at least 1 3, the output of Algorithm
at time with COUNTING-DICT, as the subroutine a
'Note that Theorem A.I gives even tighter guarantce, hut we use this slightly weaker composition for a cleaner presentation.

---

DP Space-Efficient Algorithm for Counting Distinct Elements
Acknowledgments
Bun, M. and Steinke, T. Concentrated differential privacy: simplifications, extensions, and lower bounds. In Pro- ceedings of the 14th International Conference on Theory of Cryptography, TCC '16, pp. 435-658, 2016.
R.C., T.M., and T.O. were supported in part by NSF grant CNS-1942772 and 2138834 (CAREER), a Google Cyber NYC Award, and the Center for Smart Streetscapes, an NSF Engineering Research Center, under grant agreement EEC-2133516.
Chakrabarti, A. Lecture notes on data stream algorithms, 2012. Available at hitps: /www cs. dar Martmouth. edu/ vdd/~ac//ne http://aTTeeccc/aaaaa http://ddttttstteeeeeeeeeeee pdf.
Impact Statement
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be
Chan, T.-H. H., Shi, E., and Song, D. Private and continual release of statistics. ACM Transactions on Information and System Security, 14(3), 2011.
specifically highlighted here.
Charikar, M., O'Callaghan, L.., and Panigrahy, R. Better streaming algorithms for clustering problems. In Pro- ceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC '03, pp. 30-39, 2003.
References
Alon, N., Matias, Y., and Szegedy, M. The space complexity of approximating the frequency moments. In Proceedings of the 28th ACM Symposium on Theory of Computing, STOC '96, pp. 20-29, 1996.
Cormode, G. and Muthukrishnan, S. An improved data stream summary: The count-min sketch and its applica- tions. Journal of Algorithms, 55(1):58-22 2005.
Alon, N., Matias, Y., and Szegedy, M. The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, 58(1):137-147, 1999.
Datar, M., Gionis, A., Indyk, P., and Motwani, R. Maintain- ing stream statistics over sliding windows. SIAM Journal on Computing, 31 31(6):1994-1813 2002.
Bellare, M. and Rompel, J. Randomness-efficte sampling. In Proceedings of the 35th Annual Symposium Foundations of Computer Science, FOCS '94, pp. 276 287, 1994.
oblivious
Desfontaines, D., Lochbihler, A., and Basin, D. A. Cardinal- ity estimators do not preserve privacy. In Proceedings on Privacy Enhancing Technologies, volume 2019 of PETS '19, 2019.
Blocki, J., Blum, A., Datta, A., and Sheffet, O. The Johnson- Lindenstrauss Transform Itself Preserves Differential Pri- vacy. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS '12, pp. 410-419, 2012.
Dickens, Thaler, J., and Ting, D. Order-invariant cardi- nality estimators are differentially private. In Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems, NeurIPS '22, 2022.
Blocki, J., Grigorescu, E., Mukherjee, T., and Zhou, S.
How to make your approximation algorithm private: A black-box differentially--rivaee transformation for tun- able approximation algorithmss of functions with low lensitivity. In Approximation, Randomization, and Com- binatorial Optimization. Algorithms and Techniques, AP- PROX/RNNDMM 2023, volume 275 of L.Ples, pp- 59:1- 59:24, 2023.
Dinur, I., Stemmer, U., Woodruff, D. P., and Zhou, S. On dif- ferential privacy and adaptive data analysis with bounded space. Proceedings of the 42nd Annual International Conference on the Theory and Applications of Crypto- graphic Techniques, EUROCRYPT '23, pp. 35- 65, 2023.
Durand, M. and Flajolet, P. Loglog counting of large cardi- nalities. In Proceedings of the European Symposium on Algorithmss ESA '03, pp. 605-617, 2003.
Bolot, J., Fawaz, N., Muthukrishnan, S., Nikolov, A., and Taft, N. Private decayed predicate sums on streams. In Proceedings of the 16th International Conference on Database Theory, ICDT '13 pp. 284 295, 2013.
Dvijotham, K., McMahan, B., Pillutla, K., Steinke, T. and Thakurta, A. Efficient and near-optimal noise gen- eration for streaming differential privacy. In 65th IEEE Symposium on Foundations of Computer Science, FOCS '24, 2024.
Braverman, V., Manning, J., Wu, Z. S., and Zhou, S. Private Data Stream Analysis for Universal Symmetric Norm Estimation. In Approximation, Randomization, and Com- binatorial Optimization. Algorithms and Techniques, AP- PROX/RANDOM 2023, volume 275 of LIPlcs, pp. 45:1- 45:24, 2023.
Dwork, C. and Roth, A. The algorithmic foundations of dif- ferential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211 00::21--007, 407, 2014.
10

---

DP Space-Efficient Algorithm for Counting Distinct Elements
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise to sensitivity in private data analysis. In Proceedings of 3rd Theory of Cryptography Conference, TCC '06, pp. 265-284, 2006.
Systems 36: Annual Conference on Neural Information Processing Systems, NeurlPS '23, 2023.
McGregor, A. and Vorotmikova, A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs. In Proceedings of 1st Symposium on Simplic- ity in Algorithms, SOSA '18, 2018.
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G.N. Dif- ferential privacy under continual observation. In Proceed- ings of the 42nd ACM Symposium on Theory of Comput- ing, STOC 10, pp. 715-724, 2010.
Mir, D. J., Muthukrishnan, S., Nikolov, A., and Wright, R. N. Pan-private algorithms via statistics on sketches. In Proceedings of the 30th ACM
Epasto, A., Mao. J., Medina, A. M., Mirrokni, V., Vassil- vitskii, S., and Zhong. P. Differentially private continual releases of streaming frequency moment estimations. In 14th Innovations in Theoretical Computer Science Con- ference, volume 251 of ITCS 23, pp. 48:1444: 1-4::24, 2023.
Symposium on Principles of Database Systems, PODS '11, pp. 37-48, 2011.
Misra, J. and Gries, D. Finding repeated elements. Science of Computer Programming, 2(2): 143-12,,, 1982.
Fichtenberger, H., Henzinger, M., and Ost, L. Differentially private algorithms for graphs under continual observation. In 29th Annual European Symposium on Algorithms, ESA, volume 204 of L/Plcs, pp. 42:1-42:16. Schloss Dagstuhl Leibnizz-entrru für Informatik, 2021.
Mitzenmacher, M. and Upfal, E. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
Morris, R. Counting large numbers of events in small reg- isters. Communications of the ACM, 21(10):840-842, 1978.
Flajolet, P. and Martin, G. N. Probabilistic counting algo- rithms for data base applications. Journal of computer and system sciences, 31(2):882-200) 1985.
Muthukrishnan, S. Data streams: Algorithms and applica- tions. Foundations and Trends in Theoretical Computer Science, 1 2005.
Flajolet, P., Fusy, É., Gandouet, O., and Meunier, Hy- perloglog: the analysis of a near-optimal cardinality esti- mation algorithm. Discrete Mathematics & Theoretical Computer Science, 2012.
Pagh, R. and Stausholm, N. M. Efficient differentially pri- vate FO linear sketching. In Proceedings of the 24th International Conference on Database Theory, ICDT '21, pp. 18:1-18: 19, 2021.
Ganguly, S. Counting distinct items over update streams. Theoretical Computer Science, 378(3):211-222, 2007.
Smith, A. D., Song, S., and Thakurta, A. The Flajolet- Martin sketch itself preserves differential privacy: Private counting with minimal space. In Advances in Neural Information Processing Systems 33, NeurIPS '20, pp. 19561-19572, 2020.
Ghazi, B., Kumar, R., Nelson, J., and Manurangsi, P. Pri- vate counting of distinct and k-occurring items in time windows. In 14th Innovations in Theoretical Computer Science Conference, ITCS '23, pp. 55:1-55:24, 2023.
Hehir, J., Ting, D., and Cormode, G. Sketch-Flip-Merge: Mergeable sketches for private distinct counting. In Pro- ceedings of the International Conference on Machine Learning, 2023.
Stanojevic, R., Nabeel, M., and Yu, T. Distributed cardinal- ity estimation of set operations with differential privacy, In Proceedings of the IEEE Symposium Privacy-Aware Computing, PAC '17, pp. 37-48, 2017.
Henzinger, M., Sricharan, A. R., and Steiner, T. A. Differen- tially private data structures under continual observation for histograms and related queries, 2023. arXiv pre-print 2302.11341
Thakurta, A. G. and Smith, A. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. In Advances in Neural Information Processing Systems 26, volume 26 of NeurIPS '13, 2013.
Huang, Z. and Peng, P. Dynamic graph stream algo- rithms in o(n) space. Algorithmniaa, 1165):195511987, 2019. doi: 10.1007/500433-018-65500 / //doi. . wrw.:orgg/l..oo wttpg///...100////..../ 100.0000000000000000011
Wang, L., Pinelis, L., and Song, D. Differentially private frac- tional frequency moments estimation with polylogarith- mic space. In Proceedings of the 10th International Con- ference on Learning Representations, ICLR 222, 2022.
URL https:
Jain, P., Kalemaj. I., Raskhodnikova, S., Sivakumar, S., and Smith, A. D. Counting distinct elements in the turnstile model with differential privacy under continual obser- vation. In Advances in Neural Information Processing
Woodruff, D. P. Optimal space lower bounds for all fre- quency moments. In Proceedings of the 15th annual ACM-SIAM Symposium on Discrete Algorithms, SODA '04, pp. 167-175, 2004.

---

DP Space-Efficient Algorithm for Counting Distinct Elements
A. Additional Tools and Background
A.I. Additional Related Work
DP continual release algorithms. Differential privacy (DP) (Dwork et al., 2006) has become the de facto standard of private computation in algorithm design. In the context of streaming algorithms, the standard DP model is the continual release model, first introduced by (Dwork et al., 2010; Chan et al., 201 I). In this model, algorithms should preserve privacy of the input, even if solution is observed at each timestep (as opposed the one-shot model where the adversary can obtain only one solution at the end of the stream). Celebrated results in the continual release model include the well-known binary mechanism for releasing sum statistics in a binary data stream with O( log²(T) additive error (Dwork et al., 2010; Chan et al., 20.1). Significant work has expanded on this foundational result in various directions, including handling non-binary streams (Thakurta & Smith, 2013; Fichtenberger et al., 2021), sliding windows (Bolot et al., 2013), and improving the space/utility tradeoffs (Dvijotham et al., 2024). The latter work also provided algorithms for counting distinct elements with additive error of (log' (aiggl((()) (T)) in insertion-one only streams. Later work (Ghazi et al., 2023) also focused on counting distinct elements in the sliding window model, achieving polylogarithmic additive error in the window size. For insertion-only streams, (Epasto et al., 2023) gave the first DP algorithms with space (polyy log(T)) and a (1 + m)-multiplicative and (poly log( additive error for counting distinct elements and frequency moment estimation in the insertion-only and sliding window model under continual release.
DP one-shot streaming algorithms. A more restricted setting is the one-shot streaming model, where the analyst only seeks to output a solution at the end of the stream. In the one-shot setting, (Desfontaines et al., 2019) showed membership inference attacks for a large class of non-DP sketching algorithms for counting distinct elements, implying that they do not preserve any reasonable notion of privacy. In the private sphere and for related problem, designing low-space DP algorithms for the general frequency moment estimation problem has been well-explored (Smith et al., 2020; Pagh & Stausholm, 2021; Blocki et al., 2012; Dickens et al., 2022; Hehir et al., 2023). Specifically (Wang et al., 2022) showed that a well-known streaming algorithm called the E, sketch preserves DP as is. (Blocki et al., 2023) gave a black-box transformation for turning non-DP streaming algorithms into DP streaming algorithms while still preserving sublinear space and accuracy guarantees. These problems have also been explored in the pan-privacy streaming model, where DP preserved even if the internal memory of the algorithm is compromised (Dwork et al., 2010; Mir al., 2011).
A.2. Additional Background on Differential Privacy
The privacy parameters of 7CDP compose, similar to the composition guarantees of DP. Additionally, it is possible to translate between the guarantees of zCDP and DP.
Theorem A.1 (Composition (Bun Steinke, 2016)), Let A be 5-approximate p-zCDP algorithm and A' be 8'- approximate pCDCDP algorithm. Then the composition (x) (A(z), satisfies (6 (6+8 8' 8 "approxximeeee (p+p') D'DDPDP
Theorem A.2 (Relationship DP (Bun & Steinke, 2016)). For all p. 6 (p+ 10+22/logge (1)8 6)-DP. Conversely, if A E- then A is (E² /2)-=CDPP If algorithm A is d-approximate p-zCDP then Ais (e,,+((16)))) - for all e 2 p, where 8' exp(-(e--p)) p)² /2/////4/// min [1, /T P, I+e-p1/20" 14
if algorithm A is P-ZCDP then A is
20
Conversely, if A is (c, 8)P then A is 6-approximate (E2 /2)-2CDP
Finally, we present a simple mechanism that satisfies both DP and zCDP. The Gaussian Mechanism privately answers vector-valued queries by adding Gaussian noise to the true query answer. The noise is proportional to the lg- sensiitiivtty of the function, which is the maximum change in the function's 's no-m from changing single element in the data.
Definition A.3 (Sensitivity (Dwork et al., 2006)). Let f X + R be function. Its éz-sensitivity is defined as
max [1((x) f(x')l22 x~W EX
Theorem A.4 (Gaussian mechanism (Dwork & Roth, 2014)). Let f : xm - R be a function with E Ez-sensitivity at most A2- Let A be an algorithm that on input y, releases a sample from N ((((y), 0²). Then A is (A2/ (2/(20)))=2CD
A.3. Concentration Bounds
We provide some basic concentration inequalities that will be used in our analyses.
12

---

1. H(X 2 H(XIY,), 2). DP Space-Efficient Algorithm for Counting Distinct Elements
Lemma A.S ((Bellare & Rompel, 1994)). Let X 2 4 be an even integer. Let X be the sum of n X-wise independent random variables which take values in [0, 1.. Let μ E [ and A > 0. Then,
dp du+ X2
2/2
Pr[|X /1| A 8
A2
Theorem A.6 (Multiplicative Chernoff Bound (Mitzenmacher & Upfal, 2017)). Let X -E X; where each X; is Bernoulli variable which takes value 1 with probability Ps and value O with probability 1 Ps. Let μ = E[X] = Ei=1 Ps. Then,
1. Upper Tail: Pr[X 2 (1 (L+1) 17) -M - exp
(-2tH)
d²M 2+n
for all 17 > 0;
2. Lower Tail: Pr[X S (1 7) μ exp
(->2)) for all 0 < 1.
Lemma A.7 (Chernoff Bound of Gaussian Random Variable). For X ~ NN Pr([X] > t) s 2exp(-e/220
A.4. Information Theory Basics
We provide some basic information theory definitions and facts that are used in Section E. In this paper, we use log to refer
to the base 2 logarithm.
Definition A.8. The entropy of a random variable X, denoted by H()), is defined as H(X) = Er(x =
x) log(1/ Pr[X- = z]).
Definition A.9. The conditional entropy of random variable X conditioned on random variable y is defined as H(XIV) =
(X|Y = y)] = Ey Pr[Y = y] - = =y)
Definition A.10. The mutual information between two random variables X and Y is defined as I(X:Y) = H(X)
H(X HYY) X
Definition A.11. The conditional mutual information between X and Y given Z is defined as I(X;YIZ) [
=)]
Fact A.12. Let X, Y, Z be three random variables.
2. H(X) log (X))p
3. I(X;YIZ) S Z()
4. Data processing inequality: for deterministic function f(X), ((X; 2 (f(()){)2)
5. I(X;YIZ) 0.
B. KSET and Binary Mechanism
B.1. KSET Data Structure
In this subsection, we present the KSET data structure, first introduced in (Ganguly, 2007). In the non-DP turnstile setting, one key strategy for solving variety of problems including estimating the number distinct elements sublinear space is to use space-efficient and dynamic distinct sample data structures. A distinct sample of stream with sampling probability p is a of items such that each of the distinct items in the stream has an equal and independent probability of p of being included in the set. (Ganguly, 2007) introduced the KSET data structure for this problem, which be used to (non-privately) give (1 + apprroxxiitti of the number of distinct elements in a stream using roughly O (log(T) + log((<()) log((2())) space. Our implementation of KSET is largely similar to the original version in (Ganguly, 2007), with one small change that is necessary for our privacy analysis.
Our primary reason for using the KSET data structure in the DP setting is that it allows us to maintain a distinct sample. This in turn helps us add smaller amount noise (proportional the bounded occurrency of data items) the final distinct
13

---

DP Space-Efficient Algorithm for Counting Distinct Elements
elements estimate released through a binary mechanism. However, the privacy analysis for the output of the KSET is quite involved and discussed in Section 4.1. To the best of our knowledge, distinct sample data structure has not previously been used in the DP setting,
The k-set structure (which we denote as KSET and is formally described in Algorithm 4) is a dictionary data structure that supports insertion and deletion of data items and, with high probability, either returns the set of items S present in the dictionary as long as |S| S k; or otherwise returns NIL. The structure is represented as a 2D array H R x B] which consists of R hash tables, each containing B buckets, where = [log $1 and B 2k. For each r E [R] b E [B], the bucket H ir, b] contains a TESTSINGLETON data structure, which tests whether or not the bucket [r; b] contains a single universe element. Details on the implementation of the TESTSINGLETON data structure are deferred to Appendix C. The r-th hash table in H R B] uses a pairwise independent hash function h, U + [B]. Upon the arrival of an update 2t the KSET structure contains two main operations:
1. The ( operation first increments (resp., decrements) the total number m of data items in the structure (which is initialized to zero) if the update is an insertion (resp., deletion) of an item. Next, for every hash table r E [R]]. we update the corresponding TESTSINGLETON structure in the bucket H(r, h, (x+)]-
2. The ReturnSet() operation, for every E [R], iterates over the buckets b E [B]. and checks whether the entry in the hash table [r, 6j is a SINGLETON, If so, then it retrieves the data item along with its frequency and keeps track of the set of elements (5) as well as the total sum of frequencies of items (mg) in S. If m, = m and |s| S k, then it returns S. Otherwise, the function returns NIL. We note that the latter check for |S| S k is not included in the original version of KSET from (Ganguly, 2007), but it is erucial for our privacy analysis. We include this check to ensure that the KSET returns NIL with probability 1 in the event that there are more than k elements.
Next, we state some simple properties regarding the accuracy of the KSET structure in Lemma B.1 that are used in the analysis of Algorithm 1.
Lemma B.1 (KSET properties). Consider a KSET data structure with capacity ls and failure probability B. Then, the following holds:
1. If strictly more than k distict elements present in the KSET, then with probability 1, KSET. = NIL.
2. If less than or equal to k distict elements are present in the KSET then with probability 2 1 1-3, where the entire set of items present in the KSET.
=
3. The space complexity of KSET is (k T + log [2() log $).
Proof. For Item 1, from (Ganguly, 2007), we have that if m, m then the set of retrieved items S is exactly the set of distinct elements with probability 1. Observe that if there are more than k elements, then either m, + m, the number of distinct elements returned is |S] >> k. In both cases, the condition in Algorithm 4 fails and the output is NII.
The proofs for Item 2 and Item 3 are identical to the one given in (Ganguly, 2007).
B.2. Binary Mechanism for the Count Distinct Problem
In this subsection, we present subroutine for COUNTING-KSET (Algorithm 2) that is a modified Binary Mechanism called BinaryMechanism-COl (see Algorithm 5). This subroutine is used to compute the summation stream 8, E {-1,0, 1}" representing the difference in the number of distinct elements at timesteps - 1 and t which is computed from the output of injects Gaussian noise (similar to (Jain et al.,
the KSET in Line 14 of Algorithm 2. The algorithm BinaryMechanism-C 2023)) - as opposed Laplace noise used in the original versions of the Binary Mechanism (Chan al., 2011; Dwork et al., 2010) proportional to the sensitivity of the summation stream.
We first note that if the input to BinaryMechanism-CD represented the exact difference in the number of distinct elements over consecutive timesteps, then the sensitivity of the summation stream in terms of occurrency can be calculated in a straightforward manner using arguments similar to (Jain et al., 2023). However, in for our use of BinaryMechanism in the algorithm BUUNNINGGKSETT BinaryMechanism-CU receives as input the difference in the number of distinct elements from the output of the KSET. Importantly, the failure behavior of the KSET needs to be accounted for when
14

---

DP Space-Efficient Algorithm for Counting Distinct Elements
Algorithm 4 KSET data structure (Ganguly, 2007)
Require: Capacity parameter k, failure probability
Initialize 2D array H[log g 2k]
2: R f- [log $1, B 4- 2k
Let ht, :u [B] be a pairwise independent function for L....: R
4: Initialize
5: Update(zz) {Process update 2t)
6: if sy is an insertion then
7: m 4 m +
8: else if 2,, is a deletion then
9: m < m
end if
for E [R] do
12: H(r, h...a.)).TSUPDATEE..) {see Algorithm 6}
13: end for
14: ReturnSet():
15: Initialize set 5= (, my = 0
16: for r E [R] do
for [B] do
if Hr, J.T
then
(2, c) [r, TTCCADD([1) H(r, TSCARD(]) (see Algorithm 6}
20:
Insert (x, fa) S
21: m, + m. + fx
22: end if
23: end for
24: end for
if m, = and |S| then
26: Return S
27: else
28:
Return NIL
29: end if
Algorithm 5 BinaryMechaansm--C
Require: Count distinct summation stream ./,...,,77 E [-1,0, 1)" privacy parameter
0, occurrency W >
1: Initialize each a; = 0 and á;
2: Let p' 2[+1
3: Update(y)):
4: for every update y do
5: Express in binary from: E, Bin, (t)2)
6: Let min Bin, (1) 1} be the least significant binary digit, and set o; = E5= 03 + yt
7: for j 0, , i do
8: Set a; = 0 and à 0
9:
end for
10: Set d; a; + (0, 1/p')
11: Return B(I) = (1)=1 aj
end for
arguing about the sensitivity of the resulting summation stream computed from the KSET output (when it does not fail). In order to do this, we use a coupling argument to show that the output stream of the algorithm COUNTING-KSE is close to the output stream of an algorithm that exactly computes the number of distinct elements and feeds the difference as input. The privacy analysis for BinaryMechanism- CD in the latter algorithm is similar to (Jain et al., 2023) and is given in Lemma D.4. The privacy guarantee of our application of
over consecutive timesteps to BinaryMechanism-CO
15

---

DP Space-Efficient Algorithm for Counting Distinct Elements
BinaryMechanism-C inside COUNTING-KSS is implicitly derived in the privacy analysis of COUNTING-KSET via the coupling argument of Lemma 4.2 and the claim that COUNTING-KSET is DP in Corollary 4.4.
The accuracy guarantee of BinaryMechanism-CD follows from Lemma D.8 in which we consider the overall accuracy of L instances of BinaryMechanism-CD as instantiated in Line 3 of COUNTING-KSET, Finally, the space complexity of BinaryMechanism-CD is (T)) and this follows from (Chan et al., 201 I).
C. Additional Details on KSET
We describe the TESTSINGLETON data structure (Algorithm 6) which is building block of the KSET data structure in more detail.
Algorithm TEST-SINGLETON data structure
Require: Input stream æ1, ,,
1: Initialize m - 0, U - 0, V -
2: (x
if Ie an insertion of item then
4:
1, - U + i, V V + 5: else if 24 is a deletion then
6:
m 1, - U V V -
7: end if
8: TSCARDO:
9: if m = then
Return EMPTY
else if (22 m V then
12: Return (SINGLETON, U/m, m)
13: else
14: Return COLLISION
15: end if
The TESTSINGLETON data structure supports the following operations:
1. An update operation, TSUPDATE(2;). which updates three counters - MTS,, U, and (all initialized to zero) preserving the following invariants throughout the stream:
Ea. Sar U= Ea Sara V= -a
mrs
aEu
aEll
aEl/
More precisely, for an non-empty update xa corresponding to data item a, TSUPDATE(<;) performs the following update:
mrs mTs +1, U= U + ta, V= V
(for an addition)
mrs mrs - 1, U = U a, V = V - a²
(for deletion).
2. A check operation, TSCARD(), which determines whether the TESTSINGLETON data structure: (1) 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 mrs O): (2) the triplet SINGLETON, the element, and its frequency (this happens 2 Mrs V); or (3) COLLISION (if the last checks fail). It is easy that the unique item returned (in the SINGLETON case) has identity U and has frequency mrs.
myg
D. Omitted Proofs from Section 4
For case of analysis, we define the streams produced after applying the hash function and the blocklisting procedure (in the case when ob = false) as follows. These streams will be used intermediate steps in the analysis CountDistinct to
16

---

DP Space-Efficient Algorithm for Counting Distinct Elements
separately reason about the hashing and blocklisting procedures, and their impact sensitivity of the resulting streams. Definition D.1. Define Stgg the substream of after applying hash function g. That is, let be the item contained in the update Z4z- Then [ =
if g(a) = i and Si [1] 1 otherwise.
Definition D.2. Define St as the stream of updates produced from Si.g after checking whether the item corresponding to the update 2y is in the blocklist B before time or not. That is, if the item corresponding to 2e is in before time t, then S, [t] 1, otherwise St, [t] = (t.
D.1. Proof of Lemma 4.2 and Helper Lemma
Lemma 4.2. Fix the randommess used across runs of CountDistinct and CountDistinct' Fix E [L], and let K and E de- note the output distributions of COUNTING-KSET and COUNTING-DICT, respectively. Ifk 2 T +0 polylog(T/ / B then the total variation distance of the two distributions, drv(K, E) S B/L.
vP
Proof. We start with the case when ob = false, which is the more involved case. Consider the randomness of COUNTING- KSET, and COUNTING-DICT.. Observe that because of the fixed randomness of both hashing and blocklisting, the resulting streams Sr (see Definition D.2) that are respectively used to update the KSET (in the case of COUNTING- KSET,) and the DICT data structure (in the case of COUNTING-DICT are identical.
Next, define the randomness of COUNTING-KSET, as Rxc, = Rks, x R.M.M where Rks, denotes the randomness from the KSET (Algorithm 4) and R.B.M. denotes the randomness from BinaryMechanism-00 (Algorithm 5). On the other hand, the only randomness in COUNTING-DICE We emphasize that because the randomness from adding items to the blocklist has been fixed across CountDistinct and CountDistinct', the blocklist B passed to both COUNTING-KSS
is due to the randomness of BinaryMechanism-CD. i.e., REG, BBM,
and COUNTING-DICT, are identical.
We now want to argue that the outputs of COUNTING-KSET; and COUNTING-DICT, are the same except with probability 3. Let the BinaryMechanism-CD instance in COUNTING-KSSS be denoted as BinaryMechanism-CDD kc, and the BinaryMechanism--C CD instance in COUNTING-DICT as BinaryMechanism-CU EC, and fix the randomness used in BinaryMechanism- kC, and BinaryMechanism-O0 EC,-
We claim that there are two bad events for which the outputs of COUNTING-KSET, and COUNTING-DICT, may differ.
Ej: There exists timestep where the true count S le and the KSET outputs NIL.
Eg: There exists timestep where the true count is k and the noisy count of COUNTING-DICT; S k.
By setting k 2 T + O (T we argue that both events happen with probability at most 3.
vp
For the event E1, the probability of the KSET outputting NIL happens with probability at most 3/2TL for one timestep. This because, Line 4 of COUNTING-KSET, we set as the capacity of the KSET and 3/2TT, as the failure probability. So by Item 2 in Lemma B.1 and union bound over all timesteps, this event happens with probability at most 3/2L.
For the event Eg, Lemma D.3 (below) bounds the probability of Eg B/2L over all timesteps for choice of k.
Now, conditioned on bad events E, and Eg not occurring over all timesteps, we argue that the outputs of COUNTING- KSET, and COUNTING- -DCT; are identical. Let t be the first timestep that the true count is > k. Let 12 > t be the next timestep that the true count is < k. We next consider the outputs of the two algorithms by cases across timesteps.
Case 1: 1 <t t1. Conditioned on event E, not occurring, the KSET does not output NIL during this time epoch, which means that the inputs to BinaryMechanism-CDD BinaryMechanism-CO kc; and BinaryMechhaiis-OOD timestep. In this case, the resulting noisy outputs will be the same under the fixed randomness, and the output of COUNTING-KSET, and COUNTING-DICT, after the thresholding step (comparison to T) is identical.
and BinaryMechanism CD gc, are identical, since both will be updated with only the update from the previous
Case 2: & S t < tz. For timesteps in this epoch, both COUNTING-KSET, and COUNTING-DICT, will output TOO-HIGH. Since the true count is > 1 for all t S < i22 and conditioned on E, not occurring, the output of COUNTING-DICT, must be TOO-HIGH. Also by Item 1 in Lemma I. the KSET outputs NIL for this time period with probability which means that the output of COUNTING-KSET, is also TOO-HIGH.
17

---

DP Space-Efficient Algorithm for Counting Distinct Elements
12- Next we argue about the output of COUNTING-DICY and COUNTING-KSET, timestep l2 when the true count S k. Conditioning on event E₁ not occurring. the KSET does not output NIL. at timestep l2 because the true count S k. Moreover, observe that BinaryMechhansm-CCD kc, is not updated over t < t < 82 and is only updated at timestep by because the KSET does not output NIL. Also, by construction of COUNTING-KSET, claim that BinaryMechanism-CD kc; is fed a sequence of inputs (+1, 1, 0) at timestep l2 that result in the same sum and the same length as in BinaryMechanism-C Diniisss-Dgc: eC, over 12 - 1 timesteps. This is because by definition, diff is the difference in the number of distinct elements between times 4 and /2, and |diff| S ldit, as there can only be < falf many distinct elements added (or removed) over t2 f1. Since the length and sum of the sequence of inputs to both BinaryMechanism-C00 kC. and BinaryMechanism-CD EC; timestep is the same, the outputs of both COUNTING-KSET, and COUNTING-DICT, are the same timestep l2 under the fixed randomness.
Case 3:
we
This argument can be extended over all timesteps by iteratively considering the nexl timestep when the true count is > k and the following timestep when the true count is < k. Thus when ob = true, except with probability 3/LL corresponding to the events E₁ and Eg occurring, COUNTING-KSET and COUNTING-DICT; will produce identical outputs at each timestep. That is, the distributions of COUNTING-KSET, and COUNTING-DICT, denoted K and respectively, will agree on all outcomes except subset of probability mass B/L. L. which implies that that drv (rv(K,,5 E) S B/L.
For the case when ob true, the blocklisting step is not needed. Then the fixed randomness between CountDistinct and CountDistinct' means that the randomness of the hash functions of both algorithms will be the same, so the resulting stream Stg (see Definition D.1) that is used to update the KSET (in the case of COUNTING-KSET. and the DICT data structure (in the case of COUNTING-DICT.) is identical. The rest of the argument follows symmetrically to the case when ob- = false.
D.1.1. HELPER LEMMA
Lemma D.3. Let EBM be the event that there exists a timestep where the noisy count of BinaryMechanism-
is greater than le when the true count is less than the noisy count of BinaryMechanism-CDDee is less than when the true count is greater thun k. The probubility of ERM is at most B/2L over all limesteps when ks 2 + 2/2 (log (ogg++))/ 3/2 /W log(12 ( (og(T)1/3)
Vp
Proof. For notational convenience, let A = k- T. From Algorithm 5, we know that the noise that we apply to the true count a summation at most m S log T + Gaussian random variables, each sampled from (0, 4W (log T p)pp) (Recall that the input privacy parameter to the binary mechanism is p/ L). Thus the overall noise added is (O, 4mW (log t/p) Now want to bound the probability that (0 4mW T + 1)L/p)| A, which is an upper bound the prohability of EBM occurring at single timestep.
Applying a Chernoff bound (Lemma A.7) yields:
A 8mW (log + I)L
Pr(W[(0, 4mW +)LL/)) A) s 2exp(-
We wish to bound the above term on the right by B/2TL, so that then by union bound, the probability of EBM over all timesteps is bounded by 3/2L. This requires:
2 p
+1) S 1og(3/4TL)
SmoL
+
A > 2 2 /mWg(log + 1) 1) (4T
vp
Recall that our goal is to set the value of A - such that the above inequality always holds, and we want to set A to be the upper bound of the right hand side. Since m < log T + and [log < log T' 1, then, choosing
k 2 t+ 2/2 ( / log(4T (1g()) will ensure that A is valid upper bound, and hence that the probability of
sP EBM over all timesteps is bounded by 3/2T.
18

---

DP Space-Efficient Algorithm for Counting Distinct Elements
D.2. Proof of Lemma 4.3 and Helper Lemmas
Lemma 4.3. COUNTING-DICT? (Algorithm 3) is D/ if ob true, and is B/L-approximate D/L-CDDR if ob false.
Proof. We will prove the privacy claim for the more general case when ob = =false. Note that when ob true, do not need to deal with the failure event associated with blocklisting (Lemma D.5) and thus 3 0 and COUNTING-DICT, (Algorithm 3) is p/ L-zCDP.
The key point we must show is that when neighboring streams are input to COUNTING-DICT, then the internal streams passed to BinaryMechanism- CD; inside of COUNTING-DICT, will remain neighboring. Once this is shown, then we can directly apply Lemma D.4, which shows that this instance of BinaryMechanism- CD, inside COUNTING-DICT, is differentially private. Thus we must show that even after applying the hashing and blocklisting operations the original neighboring input streams, the resulting processed streams remain neighboring.
The randomness of CountDistinct' can be viewed as joint probability distribution RED = RR x R.B.. x REC, x... x REC, where Rg denotes the randomness from picking a hash function (in Line 7 of Algorithm 1), RBL denotes the randomness from blocklisting, and RgC, denotes the randomness from the subroutine COUNTING-DICT, for i E [L]. Let a and x' be neighboring streams that differ only at timestep (", which the update (either deletion or addition) in x is for item u, and in x' is 1. and fix the randomness used in CountDistinct" across runs on and x'.
Let Sig and St.,, be the substreams of and x' produced from the hash function g (see Definition D.I). Then with the fixed randomness, Stgg and Si are neighboring. To see this, observe that for all updates except those inserting or deleting u, Si, and Sg are exactly the same. For updates regarding item if is hashed into substream i, then Sigg and S will differ only in time t". Otherwise Si and Sh will be identical. Thus, St,, and Si will be neighboring streams for all i E [4].
Let Sr and B be the substreams of r and x' produced after blocklisting (see Definition D.2). Under the fixed randomness, the timesteps at which items are first blocklisted are the same for the neighboring streams, except (possibly) for item u. Since the updates from substreams Si n and 8 are stored exactly as-is in DICT, and then fed to BM-Count-Disinnt as input, the input streams to BinaryMechanism- CD, are indeed neighboring.
By Lemma D.4, the output &; of BinaryMechanism-CD: is 3/ L-approximate p/ L-ZCDP. The remainders of the operations in COUNTING-DICT - including the thresholding step to output either the numerical value of & or TOO-HIGH - are simply postprocessing on the private outputs & of BinaryMechanism-CDD, which will retain the same privacy guarantee. Thus, COUNTING-DICT. is // //--approximate p/ L-ZCDP as well.
D.2.1. HELPER LEMMAS
Lemma D.4. The BinaryMechanism-CC instance in COUNTING-DICT; is L/approoxee L-DCDDP
Proof. Consider the binary tree produced by BM-Count-Distinct with log(T) levels. We define a vector G2 of length T/2h for each level [log(T))] of the binary tree as
Gabi = - - 1) 2"1
defined in Algorithm 3 of COUNTING-DICT, Let G (Go, ... ). To prove the claim, we will bound the sensitivity of the counts stored in the binary tree represented by G, and then show that sufficient noise is added to each count to satisfy differential privacy. Similar to the original binary tree mechanism of (Chan et al., 2011; Dwork et al., 2010), the output of BM-Count- Doount-Distinct; at timestep L can be obtained from G by considering the dyadic dccomposition of the interval (0, t] as a sum of the individual nodes composing the interval, and this output will be private by postprocessing. 6
for all; j [T/2"] and s,[t] = E.Ee [u])
First, we claim that the binary tree described by G plus DP noise (which we will determine) produces the output &c. To this, first observe that [t] s - s - +] Z[t] where Z[t] is the noise term. Also Go 3 Z1j.. The claim follows by induction over h E [[og(T))-
*JJain et al., 2023) used similar techniques to argue about the sensitivity of their binary tree mechanism. However, their argument more straightforward as does not have to consider the randomness from hashing or blocklisting.
19

---

DP Space-Efficient Algorithm for Counting Distinct Elements
Let G and G" be the binary tree representation of neighboring streams x and x' respectively. We will show that ||G-G"
2 <WW + () + 1) with probability 1 1 B.
Fix h E [log(T)) and j E [T/2*]. For ease of notation, let ji - 1). 2 and j2 = jj2 Then
|G Gi = [s, - s,(ii] - ادا + s [لاا - 2,
(I)
where the inequality is due to the fact that and s/ can differ by at most at both timesteps j1 and je-
Next, observe that for a fixed h, the intervals (i,, J2] are disjoint, by definition. Also, for E [T/2"], G.Di + G are different at most W + 1 intervals with probability 3 (by Lemma D.6) where = TT/33
Thus, with probability / T., the (squared) lg- fz-sensitivity of G is bounded:
A < G - 12 = Σ Σ
(Grbl - G,DD) s (log T + 1)(W + 1)
(2)
[E[log(T)] J2[T/2M
By Theorem A.4, adding Gaussian noise sampled N (0, ) for o² = A3L to each count stored in a node of the binary tree 2p
represented by G will satisify p/ L-ZCDP with probability B/ L. Plugging in the bound A it is sufficient add
Gaussian noise with variance o² flog ++1(W+122 In Algorithm 3, the BinaryMechanism-C subroutine is instantiated
with privacy parameter p/ L, which adjusts for the extra factor of L.
Finally, since the output of BinaryMechanism-C CDD can be obtained by postprocessing the noisy nodes of G, the output is p/ L-ZCDP with probability 1 3/LL.
Lemma D.5. Suppose ob = false. With probability at least 3/ L, the maximum occurrency of the stream produced from the blocklisting procedure (Definition D.2) is bounded by T2/3
Proof. Recall that the probability of blocklisting any element after an appearance in the stream p log(T>/3
T
For any element U4 can bound the failure probability of the blocklist to catch an element after the maximum number of occurrences:
= log 1/3(T1/3L//)
Pr(x & B after 2/3 appearances]
mars
T2/3
T2/3,
(ng(r1/31,1))
< e
7273
e log(T"/31//3)
B T L
The inequality in the second step comes from the fact that (1 - a) S e for all a E R.
At most T/T2/3 = 1/ elements can appear 2 T2/3 times in a stream of length T. Taking a union bound, the probability that any of these elements is not blocklisted after T2/3 appearances is at most Ti7sE TT13 = B/T.
3
Lemma D.6. Suppose ob = false. Let x and x' be neighboring input streams and fix the randomness of CountDistinct" across runs on x and x'. For any E [T.), Si,B and St,BB differ in most T2/3 positions with probability ///T.
Proof. Let neighboring streams x and x' differ only at timestep 1", in which the update (either deletion or addition) ar for item u. and in x' is L. and fix the randomness used in CountDistinct" across runs on x and x'. As shown the proof of Lemma 4.3, the substreams St,g and Si neighboring and thus will also differ at timestep tº with respect to item Thus under the fixed randomness, for all timesteps 1 + t", the same items are blocklisted in S; and Sy
Let Eo be the bad event that there exists an item v that appears in the hashed substream at some timestep t * t* and is not blocklisted after T2/3 occurrences. By Lemma D.5, the probability of Eg is bounded by 3/L. We will condition on the event E, not occurring for the remainder of the proof. Note that if the items in Stgg and Si do not appear more than 2 times for all E [Z.]. then naturally Eg does not occur.
20

---

DP Space-Efficient Algorithm for Counting Distinct Elements
Recall that the item u appears in exactly the same timesteps in Sigy and Si.g for + 1". Suppose that the number of appearances of u in those steps is 2 72/3, The resulting blocklisted streams St, and Si can differ in at most 72/3 + 1 timesteps because the item may he blocklisted before it appears 72/3 times, but conditioned on Eg not occurring, it must be blocklisted after the 7 -th appearance. Since St.g has an extra occurrence of (at timestep t²) relative to Si.g this means that Si can differ from S/,B in at most T2/3 + 1 timesteps, after which both S and Si, will have O's for all future occurrences of item u.
D.3. Proof of Theorem 4.6 (Accuracy)
We restate Theorem 4.6 below for convenience.
Theorem 4.6. Let F(I) be the correct number of distinct elements of the stream at time I and let X +1)0g T T-1) oo0000000 and when ob is false, let "y P ((13/3-1)(lg 1 +1) log( T+13/8) +3T1/3 log (T2/3 log BB)) For a fixed limestep E [T], with probability least
2 log [00 (0000loog))11)))100
When ob is true, let
0
1 1- 3, the output of Algorithm I at time with COUNTING-DICT; the subroutine is a (1 + 4n, 32 max 32,,3/22//))) approximation of F(t) for any 17 E (0,0.5).
Proof of Theorem 4.6. When ob is true: The proof relies on the following lemmas, which ensure that for a specific timestep t, the good events occur with high probability:
1. In all substreams E [L. the correct number of distinct elements in the substream by hashing, denoted (t).). is also a good estimator for the number of distinct elements in the entire stream timestep i, denoted F(I) (Lemma D.7). That is, for all i [L]. the following two conditions hold at the same time for any specific timestep t with probability at least - 3/5 for any 17 E (0, 0.5):
(a) Vi E [Z] with Ftt) 2 2'
4A
1pt we have (1 - 11)
S
(t) S (1 + 7) F(O)
2
2
(b) Vi e [z] with F(t) < 2' we have
F())
4A 2
S
Et(t)
F(O)
+
7
2
2. BinaryMechanism-Ol CD (Algorithm 5) is accurate (Lemma D.8). That is, for all E [L], we have [F((1) 8s(()) s
4(W (o000log411 (10(lo0 +1//8) with probability - 3/5.
3. For any stream i, if the correct number of distinct elements in the subtream is below certain threshold then COUNTING-DICT; will not output TOO-HIGH (Lemma D.3). Plugging in 3/5L into Lemma D.3 yields that if Ft(t) < 16 max 32./n"]. then COUNTING-DICT, will not output TOO-HIGH, i.e. the noisy count s, S T
16 max 322, / + 2/2 (log T+1) / / 120( 20T log T8)8)
with probability at least - B/5.
vp
To prove the desired accuracy claim, we will condition on all three high-probability events listed above occurring at timestep t. Note that each of the three events occur with probability 1 - 3/5.. Thus all three events will happen with probability at least 1 - 3 3 21 1 - 3 by a union bound.
We consider two cases for the number of distinct elements of the stream at time & denoted by F(I): (1) F() > 8 max(7//1, 32Xrr²), for which we show that the resulting approximation satisfies a multiplicative error of (1 + 4n). and (2) F(t)= < 8 max((7/n, 32X/n"), for which we show that the resulting approximation has additive error of 32 32)/n"). We now separately consider the two cases.
Case (1). F(t)= 2 8 maxxy//n 32A/1²). Let 1" E [L] be the largest i s.t.
F()) 2 4 maxx(7/n,322/1)) Note that
2
20 < (t)(t) < (1 + n) F() Therefore by the definition of i", F:-(t) 2 nrd S 2 Since in this case the noisy count 8;- at timestep / would not exceed by Lemma D.3, so COUNTING-DICT, will not output TOO-HIGH in the stream i*, Then S,- [t] = 8.. (t)), and by Lemma D.8.
by Lemma D.7, (1- 7) F())
8
= 16 (onaax//,,32//////1
BinaryMechanism-CC will be accurate and S.- [4] Z F-- (1) yy Since Fi-(1) Z (1 - -)) 2 Lemma D.7 and using the fact that 17 < 0.5:
F(e)
2 max(7/n1 32X/n²) by
Sy. [t] 2 2 maxx(1//
7 2 max(>/1) 322/
(3)
21

---

DP Space-Efficient Algorithm for Counting Distinct Elements
Above we showed that Fg. (1) s 16 max(1/n, 32A/1P). m22/ Then by Lemma D.3, the noisy count from i" will exceed
T= == 16 max(7/n, 32//n/ 2 [1)) /W log(207 log so COUNTING-DICT, will not output TOO-HIGH. vP
The only concern now is that the output from i" may not be output if the noisy count is smaller than max(7/n, 32X/1²²) (see Line 22 of Algorithm 1), but by Inequality (3), this is impossible because S (c) 2 max(n/n, 322/1²). Therefore, Algorithm with COUNTING-DICT for some Y' 2 i" instead 0.
the subroutine will produce non-zero output, i.e. it will output some Sy [4] -2
We now proceed in two steps: first, we derive lower bound on the true count (t) in substream i'; then, we bound the ratio between Algorithm I's output Sy [4] 2 and the true count F()), using (1) as an intermediate quantity.
We start with the lower bound on (t):
(t) 2 [t] Y
by Lemma D.8 because I nS
2 (1 St([]
16A/17²
because 32A S St and 0 < < 0.5
F(t) Next we bound the ratio between Sy 2 and F(t). According to Lemma D.7, (1 (1- 11) 2 Then,
S (t(() S (1 7) F())
2n
Sv14 S (2(1) +7
by Lemma D.8
Sy1 - (t(()
because S </SSy [t]
1-
- + r Ftt)
by Lemma D.7
1j 2²
<1 + 4n) F(t)
because 0 < 1) < 0.5
2
To see the second inequality, we use the fact that y S S [t]. and plug this into [t < (t) + to get St([t] <
Fy)t (t) + [t]. Rearranging gives that (t]t < (e
1-" The third inequality is from Lemma D.7, which gives that Fx S
(1+ F(D whenever F(L)= 2 2 7
4. We now show that because we are in Case I where F() Z 8 max((7/1,
then it must always be the case that F(1)/2' # Assume towards a contradiction that F())/2' 42/12. Then by
Lemma D.7 (t) F(t)/2' + 42/n. By the lower bound above Fşr (t)( Z 162/1/² Combining these gives that,
16\/n2 < (1) S F()/22 + +4//1 < 4X/12 + 4X/1 < 82/12,
where the second to last step is from the assumption that F(I)/2 < 4X/1/² and the last step is because 7) E (0,0.5). Clearly this is a contraction, so it must be that F(t)/2"
By symmetric arguments,
(b(()
1 1- n F() 2
F(I)
1 2 (t) - - 2
2 (1 4n)
1+1
1 1 2
2
Thus in the case when F(I) > max(1/n, 32X/11²)) Algorithm produces a numerical output [x 2 for some i' > O. which will achieve multiplicative error of 1 417 with respect to the true count Ftt).
Case (2). F(t) < 8 max(1/n. /et/////.//////" 32 ) in which case again F((t) S 16 max(y/n,32M would not exceed 7 by Lemma D.3, so COUNTING-DICT. will not output TOO-HIGH. Then, Algorithm 1 either outputs O, which will result in additive error at most 8 max(7/n, 32X/n")), )), or it outputs Sy(t] 2" for some i', such that Sp [f] 2 (oxx(7/n,222/11 In this latter case, by the same argument as in Case (1),
for all i, so the noisy count
(t( 2 Sy (1) 7 2 (1 S 2 162/1/.
Having established a lower bound for Fv (f), we now turn to derive upper bound for the algorithm's output Sp((] 2², By Lemma D.7, we know that if
F(t) 4A then (t) s 2 F(U)) and otherwise, F(t)
2 7 then 162/n S 162/1² S
2d n
22

---

DP Space-Efficient Algorithm for Counting Distinct Elements
F()) which implies that F(D (t) $
2 2
122/n. Thus in this case (t(t) S
F(D) 2
+ 42/n S 2 P(0
2d as well, since
F(1)/2' 2 12 Hence under both conditions,
S 2" 1 (t) +1)- 2
by Lemma D.8
B.(()) 2
$ 1- 17
because 7 75 11Str [4]
F(1)
because F.(1)) < F()) 2
2.. 2
2
and 0 < < 1/2
= 4F(t)
< 32 max m2X/7/
by Case 2 condition
Therefore, in this case Algorithm 1 achieves an additive error of at most 32 32.////,,,,///7
When of false: This proof is very similar to the case where ob is true. The main difference is that we need one extra lemma about the size of the blocklist. There is also an additional error caused by the blocklist, which can be treated as part of the error from the binary mechanism. The majority of the analysis stays the same; the only difference is that will have a larger error in this case because of the blocklist.
We will use the three same key lemmas as in the case where ob=true, and an additional lemma bounding the size of the blocklist. These four lemmas will ensure that at a fixed timestep I, the desired good events will happen with high probability:
1. In all substreams E [L] the correct number of distinct elements in the substream by hashing, denoted F;()), is also a good estimator for the number of distinct elements in the entire stream timestep t. denoted F(t) (Lemma D.7). That is, for all [T.], the following two conditions hold at the same time for any specific timestep & with probability at least 3/5 for any 1) E (0, 0.5):
(a) Vi E [4] with Ftt) 2 2'
7 we have (1 (1- 11)
1
F(t)
< (.(() S (1 + 1))
F(O) 2
2
(b) Vi E [4] with F(t) < 2
4A T we have F(t) 4A
< R(I)
S F(O)
2 + 4A
2
2. BinaryMechanism-OO (Algorithm 5) is accurate (Lemma D.8). That is, for all E [L], we have [Ft(t) - -s((t] <
4(W +1) (+ log( 10(1og T+1)8) with probability at least 3/5.
3. For any stream i. if the correct number of distinct elements in the subtream is below certain threshold then COUNTING-DICT, will not output TOO-HIGH (Lemma D.3). We plug 3/5L into Lemma D.3 to obtain that, if Ft(t) & 16 max 32A/7²}. then COUNTING-DICT, will not output TOO-HIGH, i.c. the noisy count & S T = 16 max(7/n,322 3 + 2/2 (log 1+133/2 /w 1o0(207 (1gg T1/8)
v
4. The blocklist has bounded size (Lemma D.9). With probability at least 1 - 33/5, the size of the blocklist is bounded by /3 I/ log /))
Conditioned on these good events and plugging in W T2/3 by Lemmas D.8 and D.9, for each instance of BinaryMechanism-CCD the overall additive error stemming from the binary mechanism and blocklisting is y ((T=//-1)(log T +1) log(100log + 3/ 1/3 [log T1/3).
To prove the desired accuracy claim, we will condition on all four high-probability events described above occurring at timestep l. Note that each of the four events occur with probability - 3/5 Thus all four events will happen with probability least 1 3 2 1 3 by a union bound.
From here, can again treat separately two cases based on F(t), the number of distinct elements of the stream at time t: (1) F(()= > 8 max(7/n, 32\/1²) and (2) F(I)= < 8 max(1//,, 32\/1²). As in the case where ob=true, we show in Case (1), the resulting approximation satisfies multiplicative emror of (1 + 4n), and in Case (2), the resulting approximation has an additive eтror of 32 max(7/n, 32)/1²). The analysis in both cases is identical to when ob=true as presented above, with the correspondingly larger value of 7/ and so is not repeated here.
23

---

DP Space-Efficient Algorithm for Counting Distinct Elements
D.4. Proofs of Helper Lemmas for Theorem 4.6
Lemma D.7 bounds the number of elements in the substream after hashing. Lemma D.8 proves the accuracy of BinaryMechanism-CD algorithm. Lemma D.9 bounds the size of the blocklist when ob is false. With the help of these lemmas, can show the accuracy of COUNTING-DICT, as intermediate step in the analysis.
Lemma D.7 (Substream concentration bound). Let F(t) be the number of distinct elements of the stream at time t, and ler Ft( be the number of distinct elements of substream Si.g (Definition D.I) any i E [L]. F(t) 2 2' 12. then F(1)
ap.
(r(] P(D) > 11 1 S 5.. Otherwise, if (() < 2 + then (r(
4A S 9 This implies that
2
5I.
the following two conditions hold at the same time with probability at least B/5:
1. Vi E [L] with F(t) 2 2
4A oft
we have (1 11-
F(1) 2
I (t(t)
S (1 + 7) F())
2
2. Vi E [L] with F(t) 2
1A a
we have
F(D) 2
12 S (t)
F(U) -
+ 1
2
Proof. We start with the case of F(t) 2 2
77
14.
Applying Lemma A.5 to the F((t) as sum of F(t) A-wise independent =
Bernoulli(2 random variables, and with μ
F(O)
A=
F(t) 2
yields the following:
F(I)
F(L)
A
F(A) 2
+
X2
A/2
Pr [((t)
17
8
2
2
112
F(L)
)2
X/2
X
X
8
112 2
F(O)
172(
F(t)
)2
2
A
X
A/2
1P(4//1P) 1P(44/12)3
2 +
7
A/2
8
4
16
where the third step is because of the case F(I)= 2 2 n,,
and the fourth step simplifies terms.
We now wish to bound the right hand side by sz. solving this inequality for À yields the following bound:
A/2
8
8
+
4
16)
5L
A/2
n/
$ 3/40L
4
16)
log(1/ (1/4 + 1/ //16) S log(3/40L)
2 2log(3/40)
log(1 1/4 + + 126/16)
log( 40L/B)
A log( 1/447///6
The last step comes from multiplying both the numerator and denominator by -1, and - log(z) = log(1/z).
Since 7) < 0.5, then the denominator can be bounded by: log( (18474777)11) 1og(64/17) 1. Since Algorithm sets (400444)/)) the above inequality will be satisfied.
Next we consider the second case, where F(t) < 24. 4A. Applying Lemma A.5 again to the (t()), now with 4A
'7 yields
24

---

DP Space-Efficient Algorithm for Counting Distinct Elements
the following:
F(t)
41
A
P())
+ X2
X/2
Pr
[F((t)
8
2
12
4X/12
X2
2/2
<
16X
/n2
2/2
17
16
where the second step because of the case F(t) 2 12 and the third step simplifies terms.
172
We again wish to bound the right hand side by 6z. and by the same steps as in the first case, the desired inequality holds if 2 1lg((401//) and using the requirement that < 0.5, Algorithm I's choice of À = 2 log(40L/B3) will log( 178==2/10
and only if X 2
satisfy the desired inequality.
Lemma D.8 (Binary mechanism accuracy). Fix a timestep & E [7], and recall that (,(1) is the noisy count of F((t) produced by BinaryMechanism-CDi Then [F((t) 8,(1) < 4(W+1)0log T+133 log(10(log T=g]olog(0 T+1)/a) simultaneously for all i E [L] with probability 1 3/5.
Proof. We will show that for a specific substream E [Z.] the error (F((t) - 8c(() is bounded by the desired term with probability - 3/5L, and the lemma will follow by a union bound over all i E [L].
Now consider the error of substream at timestep t. Algorithm 5 (BinaryMechanism-Ol independent Gaussian noise terms, where Bin, (4) is the number of ones in the binary representation of t. Hence, the error (t) (t)] is sum of at most log T + independent Gaussian random variables each distributed as (0, 2L + (log I + 1)) and so the error itself is also Gaussian with mean 0 and variance at most 21 ()(lg T+1)²
adds a total of Bin (t)
Applying a Chernoff bound (Lemma A.7) to this random variable, gives that for any 7 > 0,
-py² Pr[ - s, 3.(0) > 7] s 2xxp 4L(W + 1)(log T + 1)3
We wish to bound this probability by 8/5L. Solving this inequality for y yields 7
AL(W+1)(log T+ 1)+1)1m 1+1))1og(10//33 (00(10//3))
Since
P
L log 77 < log T + 1, then choosing 7 4(W 41 (og 11/) will satisfy the inequality.
Lemma D.9 (Bounded blocklist size). Suppose ob = false, Fix a timestep t E [T]. With probability at least 1 - -B55, the size of the blocklist B is bounded by 3T (T' L where L [log T7.
Proof. The size of the blocklist is non-decreasing since elements are never removed, so it is sufficient to upper bound the final size of the blocklist after T timesteps.
Define the random variable Y, to be 1 if the j-th arrival in the stream is blocklisted and 0 if otherwise. Then Y = Σ. Y, an upper bound on the size of the blocklist (because the arrivals may be updates of the same element). The sampling T log (11/3 T1/3 1/g(T L/3).
rate for blocklisting is p- log(T1/31_/9) T4/3
Y, Bern( L/8B)) and [E[Y] 72/3
7273
Applying a multiplicatiie Chernoff bound (Theorem A.6) with 17 = 2 yields:
Pr Y 3/ /33 S exp (T33/3 log (33)
We would like to bound this probability by B/5, which occurs when 11/3 (lgg T1/31 2 log( 9). This inequality will clearly
hold if T1/3 T1/3 Tog T] 2 5. which is true for 2 8.
25

---

DP Space-Efficient Algorithm for Counting Distinct Elements
D.5. Space Complexity
We restate Theorem 4.7 below for convenience.
Theorem 4.7. With probability least 1 B, assuming the universe size [M] poly(T); If ob is true, the space complexity of Algorithm 1 is O(vW pOlyyoogT/33) poly( If ob is false, the space complexity of Algorithm is O (e0p/s.polyooo polylog(T/3)) poly( pn
Proof of T'hoorem 4.7. We condition on all the high-probability events used in the proof of Theorem 4.5; these events occur with probability - |3 as shown in the proof of Theorem 4.5. The space usage comes from (1) the KSET data structure in COUNTING-KSET, (2) BinaryMechanism-CD, and (3) the blocklist (when ob false).
From Lemma B. the L instantiations of COUNTING-KSER together have space complexity L Okk T + log log(k/8))
O (log T k- (log T + log (1) log(k/$)) where À 2 2log(40flog(2)1/)) and k 16 max(?/1, 32X//m/ + 4V2 (logT++1 7'1)%/ /W 1og(207 [log T1/B) (here W = 72/3 when ob is false). We make the
vP
standard assumption that the universe size 44 is poly (T), so can represent an item in poly(T) bits. This means that the space complexity simplifies to O(k poly log((") log(k/3)).
As shown in (Chan et al., 2011), one instance of BinaryMechanism-C0 uses O(log(T)) space, and therefore the L use space O log(T)) = O(log" (T)).
copies of the BinaryMechanism-O0
The blocklist when ob is false has size O /3 (T)B)) when conditioned the high high-probability events.
The dominating term is the one from the KSET data structures, which is O(k polylog(T) log(k/B)) for k
16 maxf7/n, 322/n2) + 4/2 (1og/+ W (og(207[log T1/3)
vp
ob is true, 7
4(W 40W+)) 1)s log( 7+ 1)/8) which case the space complexity simplifies to
O(WW- (T)))og(T/3)) poly(d))) otherwise, when ob is false, Y = // log / [log 2))3). in which case the space complexity simplifies to O polylog(T/3)) poly( (
log T+1/0) +
E. Blocklisting Problem: Space Upper and Lower Bounds
In this section, we formally define the problems of blocklisting items with high flippancy (and high occurrency) and prove space lower bound for both problems. Our lower bound is information theoretic and applies to any algorithm for blocklisting (flippancy or occurrency), including exponential time algorithms and non-private algorithms. Then, show that the problem of blocklisting occurrency has an almost-matching space upper bound that is tight up to log factors, given by Algorithm 1.
Recall that the flippancy of an item is defined in (Jain et al., 2023) as the number of timesteps where the item switches between being present absent or vice versa, while occurrency defined by the number of timesteps where an item appears in the stream (with any sign).
Informally, we define the blocklistaip (W) (resp.. blocklistocc (W)) problem to be the problem of identifying. for each timestep of a tursstile stream, whether the current element of the stream has flipped < W times (resp., occurred < W times) before this timestep. More formally, let 2/ be a universe of items and let x = (#1...., Fr),, be a turnstile stream where for each time t E [T]. the stream element 2; is either an insertion (++) or deletion (-u) for some u E U, or I4 =1 indicating an empty update.
Definition E.1 (The blocklistaip (W) (resp., blocklistoee (W)) problem). For the turnstile stream x (I1, TT). define the ground truth for the binary stream of outputs o² o"(x) (oi, .., o where for each ( [T], of = 0 if mr has flippancy < W (resp., occurrency < W) in the prefix stream (ZI,..., xz-1) or if x; =L, and of = 1 otherwise. Let o(r) (01- or) ) be the output provided by an algorithm on the stream æ. The algorithm has false negative at time t if or 0 and or 1, and has a false positive when o, = 1 and of =0. 0.
Notice that algorithms using flippancy blocklisting such as (Jain et al., 2023), or occurrency blocklisting like our algorithm are required to have no false negatives with high probability. This is because the max flippancy (and occurrency) bound
26

---

DP Space-Efficient Algorithm for Counting Distinct Elements
used upper bound the sensitivity of the binary tree mechanism and thus needs to hold with probability at least (1 8) achieve (e, 6)-D.
While false negatives affect the privacy of the algorithm, false positives must also be bounded to ensure accuracy. For this reason, we ask if it is possible to design low-space blocklisting algorithms (for flippancy or occurrency) that guarantee (with high probability) no false negatives, while bounding the number of false positives. In Section E.I, we prove a lower bound on the space of any algorithm that bounds flippancy or occurrency. Then in Section E.2, we give a near-matching upper bound by showing that Algorithm solves the low-space occurrency blocklisting problem using space that matches the lower bound up log-factors.
E.1. Lower bound
We first show that any algorithm (including non-prion son-private and exponential algorithms) for blocklistaip (V)) and blocklistoee (W), with no false negatives and with bounded false positives must have a space that depends the number of false positives allowed. This space lower bound also extends any algorithm for count distinct estimation that uses blocklisting methods to control flippancy occurrency, such (Jain et al., 2023) or our work.
Theorem E.2. For any even integer W > O, and any integer r > O, let Astip (resp., Aoce) be an algorithm for blocklistnip (W) (resp.. blocklistoce (W)) such that, given an arbitrary stream x of length T, with probability at least 1 - 8, has no false negatives and has at most r false positives. Then algorithm A Allip and Aoee use space at least:
(1 (1- B) (1og(1 - 3)+ 2W
(1og(1-3))
T
WT
log T + 2Wr
We provide a proof sketch here, and full proof is deferred to Appendix F.1. Our lower bound proceeds by describing random process defining stream distribution that is hard for the problems of blocklistaip (W)) and blocklist (W). For the element universe U = [T/2], the main idea is to define a distribution of problem instances as follows. First, generate X C U as a uniformly random set of size T/2W. Then define a stream xxX) where for the first T/2 timesteps, each element u E X appears in W updates, alternating W/2 times between one insertion and one deletion of u. This results in W flippancy and W occurrency for all elements of X at the end of the first half of the stream. the second T/2 timesteps of the stream, all elements U are inserted once. Thus the correct output for this stream for both the blocklist (W) and blocklistocc (W) problems is to always output O in the first half, and to output in the second half only for elements in X.
We then use an information theory argument to show a space lower bound for any algorithm Aftip that satisfies the conditions of no false negatives and at most false positives, with probability at least 1 - 3 over this distribution of problem instances.
E.2. Upper bound for occurrency blocklisting
We now present an upper bound (Corollary F.3) based on Algorithm for the space required to solve the occurrency blocklisting problem with r false positives.
Corollary E.3, With probability 1 1- 22 and when [u] = poly(T), Algorithum with ob=false reports no false negatives and r = 1/ log(T [Togg (T))3))) false positives for the problem blocklistoee (W) W T2/3, while using space O(T1/3, polylog(T)) (T)3)) poly( pq)
Note that plugging = 1/3 1/r
and W = 72/3 into the lower bound of Theorem E.2 gives an near-matching space lower bound that is tight up to log factors.
The proofs for no false negatives and the space complexity follow from Lemma D.5 in Appendix D.2, which gives a high probability bound on the maximum occurrency of the stream after blocklisting, and from Theorem 4.7, which bounds the space used by Algorithm 1. The proof for the bounded number of false positives follows from concentration bound the probability of blocklisting element too early. The full proof is deferred to Appendix F.2.
F. Omitted Proofs from Appendix E
F.I. Proof of Theorem E.2
Theorem E.2. For any even integer W > O, and any integer r > O, let Asup (resp.. Aoce) be an algorithm for blocklistaip (W) (resp., blocklist (W)) such that, given an arbitrary stream x of length T, with probability at
27

---

DP Space-Efficient Algorithm for Counting Distinct Elements
least 1 B, has no false negatives and has most r false positives. Then algorithm A Aflip and Aoce use space at least:
(1- B)- (1og(1-3)+
-3) 2W
T
log T+ 2Wr
WT
Proof. We now define a random process defining stream distribution that is simultaneously hard for the the problem of blocklistaip( (W) and for blocklistaee W.. For notational convenience, set = T/2, and m //W - (2W... For simplicity, we assume T, W such that n, m are integers.
Let the element universe be U = [n], over which we assume there is a total order. We define a distribution of problem instances with the following process:
A uniformly random set X [ U of size m is sampled.
Generate the first n. = 2/2 timesteps ensuring that all elements in X have W flippancy and W occurrency.
Then generate the second n = 2/2 timesteps ensuring that all elements in Ui are inserted once.
Define stream z (X) to be deterministic function of X follows. For the first half, all updates related to each element in X appear consecutively and in the total order. Each element X has exactly W updates, alternating W/2 times between one insertion and one deletion of u, this results in both W flippancy and W occurrency for all E X at the end of the first half of the stream. Then, the second half of the stream has one insertion of each element in U, appearing according to the total order.
is easy to see that the correct output for this stream in both the blocklistaip (W) and blocklistoce (W) problems is to always output 0 in the first half, and output in the second half only for elements in X: o" (x(()), 0 for / s n and or (x(X)), iff x, E X and 2 + 1.
We want to show space lower bound for an algorithm Astsp (resp., Aocc) that will satisfy the conditions of no false negatives, and at most false positives, with probability at least 1 - 3 over this distribution, for the blocklist (W) (resp., blocklisttcce (W)) problem. The proof proceeds identically for both problems, so we prove it only for Aflip
Without loss of generality, we assume Aftip deterministic, since for any randomized algorithm, there will exist a random seed to achieve no worse guarantee on the considered input distribution.
We prove this space lower bound via an information theory argument (see Section A.4 for information theory basics) by considering three random variables in addition to X:
S: A random variable representing the memory state of algorithm Astip after observing the first n T/2 timesteps.
Y: The set of elements with an output in the second half of the stream by algorithm Aflip-
P: An indicator variable that is 1 if Aytsp has no false negatives and at most r faase positives, and 0 otherwise. By definition we know Pr[P- 1] > - 8.
Since the algorithm Astip is deterministic, then S, P are all deterministic functions of X, since the stream itself is a deterministic function of X. Since algorithm Aytsp does not learn new information in the second half of the stream since the second half of the stream is the same for all streams then Y is deterministic function of S.
To start, the maximum size of S can be lower bounded by its entropy (S). Then HSS) can be further lower bounded by the mutual information between the input secret X and the random variable Y, which is part of algorithm Aytip 's output, conditioned on P. This can be seen using inequalities from Fact A.12:
|S| N H(S) 2 H(S)P) Z S(P; 2 I(X;YIP).
Next, we apply the definitions of condition mutual information and mutual information:
I(X:Y|P) = Pr(P = 1] I(X + Pr(P = ((X:)
2 Pr(P = I(X;Y|P==1
Pr[P = (U(X)]=))-H((P)))
28

---

DP Space-Efficient Algorithm for Counting Distinct Elements
For HX 1), since Antp is deterministic and Pr(P- 1] B, we know that X|P 1 is distributed uniformly
across least (8) (m) sets of universe elements and therefore,
H(XP= = 1) 2 log (1 (1-
(m
71
Next we analyze H(X Y,. Conditioned on P 1, by the no false negatives requirement, we know X S Y, and by at most r false positives, we know |Y| S m + r. Therefore, for any y such that Pr[Y = u| = 1] > O, it must be that |y| I m + r and that conditioned on P = 1 and Y = y, X is subset of y of size m. Therefore X can take at most (m different values. By Fact A.12,
H(X = 1,Y y) S log
m +
m )
and
H(X = Σ
Pr|Y = p= 1] H 1,Y = =y) I log
m + m
[
Putting everything together:
|S| 2 H(S) 2 I(X;VIP) 2 Pr(P- = =1] (H(X =1) -
2 (1-8)
log (1 -1-33 3)
n
- log m++)t)
m
m
n x (n 1) x
(n m + 1)
= (1 B)
log(1 - 3) + log
(m +r) x ( - 1) x .. x (r +
2 (1 - B) log(1 - 3) + m log
n
m +r
T
WT
= (1 - B) loog1 - 3) + 2W T + 2Wr
log
E.2 Proof of Corollary E.3
Corollary E.3. With probability 1 - 2B and when [M] = poly(T)), Algorithm with ob=false reports no false negatives false positives for the problem blocklistoce(W) W T while using space
and r = // log(TT (log(T]) false O polylog( (T/3)) polly( pm) )).
Proof. For the space complexity of Algorithm 1, Theorem 4.7 says that when [4| = poly(T) and ob=false, then with probability least 1 - 3, Algorithm uses space OTT1/3, polylog(T/3)) poly( pn
For the claim that Algorithm I has no false negatives with high probability, Lemma D.5 in Appendix D.2 shows that when ob false, with probability at least 1 B/L, the maximum occurrency of the stream produced from the blocklisting is at most 2//3, Since Algorithm uses W = 72/33 then with probability at least 1 - B/ T. Algorithm 1 will have no false negatives, since it will never allow elements with occurrency larger than W = 2/3 to persist without being blocklisted. Plugging in the value of L = [Tog(T)], note that (/[log(T) s 8/2, therefore with probability 3/2, Algorithm 1 will have no false negatives.
To see the false positive bound, let X; be an indicator random variable where X; if the element timestep i is a false positive in Algorithm 1, and let X Σ/ X,. Recall that Algorithm samples elements for the blocklist with probability
p
at each occurrence. Note that Pr[X; = 1] Pr((a, B) (#: < W)] Pr[(æ; B)] p. then 7-73
TT see this, first observe that P(X) partitions the input space according to the event that Ayup has no false negatives and false positives. Let R denote the size of the support for X P 1. Then, since X is uniformly chosen, Pr(P(X) 1 3
means that R
2 - B, and therefore 2 (1 - 8) (()
29

---

DP Space-Efficient Algorithm for Counting Distinct Elements
E[X] Σ Pr[X; ST T2/3 p= (,/ Applying multiplicative Chernoff bound (Theorem A.6) with " 1 yields:
12
B
Pr(X 2 1ogg exp(-(T1/3/3) Log(
S
$
T1/33
T1/9/3
To the last inequality, first plug in L [To wish to show numerically that this holds for T 2 8.
8 (T//
8/2. We observe
[lgg(T)
Taking union bound over the failure probability from the space complexity, false positive, and false negative bounds, then with probability 23, Algorithm solves the blocklistoce (W) for the desired r and space conditions.
30


Reviews:
[{"review_id": "k5SSVblmAW", "reviewer": "Reviewer_wC4M", "summary": "This work gives a new space-efficient algorithm for differentially private counting of distinct elements under the turnstile model of continual release. In this setting, the algorithm sees a length $T$ stream of insertions, deletions, or null updates of elements from a fixed domain. At each timestep of the stream, the algorithm releases the count of distinct elements remaining after the stream of operations. Their algorithms use $\\log T$ dictionaries each of which hold at most $T^{1/3}$ items to approximate the counts, giving a $\\tilde{O}(T^{1/3})$-space algorithm. This improves on the space complexity of prior work ($O(T)$ space), while still maintaining a competitive additive error bound of $O(T^{1/3})$.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and valuable feedback. \n\nRegarding the comparison against Henzinger, Sricharan, and Steiner (2024), we do, in fact, compare our result to this work in Line 192 of the submitted version; however, we cited an earlier version of the paper, titled \"Differentially Private Data Structures under Continual Observation\" (2023). We will update the reference to the 2024 version in the final paper for better clarity in the references. We appreciate the reviewer bringing this to our attention. \n\nAs for the statement on page 5 of “the space parameter k should be polylog(T)”, we apologize for the typo. More correctly we meant that the space should be sublinear in T, and in our paper it is indeed O(T^{1/3}), and we will make this correction in the final version of the paper.", "claims_and_evidence": "All claims in the work are supported with proof.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I read all proofs contained in the body of the paper and found no issues. I did not, however, read the proofs in the appendices.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "With the exception of the paper mentioned below, and to the best of my knowledge, this paper adequately contextualizes its results with comparison to prior work.", "essential_references_not_discussed": "The related work section missed a recent and very relevant paper, Private Counting of Distinct Elements in the Turnstile Model and Extensions by Henzinger, Sricharan, and Steiner 2024. This work studies the same problem and improves over the work of Jain, Kalemaj, Raskhodnikova, Sivakumar, and Smith 2023 in a few dimensions. It does not give a significant improvement in space complexity, however, so does not subsume this work.", "other_strengths_and_weaknesses": "Strengths: This paper shows how to use a series of dictionaries, each of which store elements subsampled from the stream at varying rates, to avoid maintaining the exact counts of all elements in the stream. This represents, to the best of my knowledge, a significant improvement in space over prior work, at least in the regime where the domain of stream elements is much larger than $T^{1/3}$. \n\nWeaknesses: A comparison to the work mentioned above should be included in the work.", "other_comments_or_suggestions": "On page 5 it’s stated that the parameter $k$ should be polylogarithmic in $T$, which was a bit confusing given that the space complexity ends up being $T^{1/3}$. I understand this to mean that for fixed occurrency not depending on $T$, $k$ should have only polylogarithmic dependence on $T$, so I don’t think it’s an unfair claim, but I think it somewhat misleads the reader as to what the role of the KSET dictionaries will be in the algorithm.", "questions_for_authors": "Please see comments in strengths and weaknesses section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HlDvMEqTd1", "reviewer": "Reviewer_uSeR", "summary": "This paper introduces the first differentially private algorithm for counting distinct elements in the turnstile model to obtain *sublinear* space-complexity.\nTheir new approach is to introduce the notion of occurency (maximum number of times any element appears in a stream) and are able to achieve sqrt(W) additive error, where W is the occurency of the stream. For arbitrary streams they achieve additive error of T^{1/3}, where T is the length of the stream.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comment about the subroutines and other technical details of the main algorithm that currently appear in the appendix. Based on this feedback, we plan to reduce the space dedicated to the technical overview (Section 2) in the final version, and instead use the space to incorporate additional core content from the appendix into the main body. We agree with the reviewer’s comment that this would improve readability of the main body. We will also move the definition of \\rho-zCDP back to the main text for better clarity of this concept.\n\nAs for the significance of the counting problem, we observe that counting serves as a fundamental primitive in the analysis of many private algorithms. Advancements in private counting – especially in the continual release setting – are crucial for the development of private machine learning. For instance, the state-of-the-art differentially private stochastic gradient descent (DP-SGD) underpinning privacy-preserving AI have consistently relied on advances in private sum queries over data streams (including the work on binary tree mechanisms and advanced correlated-noise counting schemes). We believe that foundational research on efficient DP continual release algorithms is necessary for advancing private ML.  We observe that the prior work “Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation” Jain et al. published at NeurIPS 2023, also highlights the relevance and importance of this problem within the machine learning literature.", "claims_and_evidence": "They provide proofs of their results.", "methods_and_evaluation_criteria": "Not applicable.", "theoretical_claims": "Only a small part of the proofs are provided in main article and these refer to algorithms and lemmas in the appendix, so I cannot confidently claim to have checked correctness of these. I did not read proofs in appendix.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "Counting distinct elements in a data stream is an extremely well studied topic. This paper adds the requirement of differential privacy to the problem. This seems well motivated, especially since they are not the first to look at this.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The result of the paper is good, achieving simultaneously low memory, high accuracy and differential privacy in the streaming distinct elements problem. The authors do a good job explaining the previous work that motivated this result.\nHowever, this paper has a lot going on and a lot of different subroutines only provided in the appendix, which can make it hard to understand how the overall algorithm works.\nAlso, one could argue, that counting distinct elements is not a core machine learning task, so there might be a question of scope. This is only a minor issue as ICML has traditionally published papers in this direction.", "other_comments_or_suggestions": "I think it would be fitting to define \\rho-zCDP in the main part of the paper instead of in the appendix, since this is the important property that is (at least directly) shown for the algorithm.", "questions_for_authors": "No questions", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Qs1f9SlMjt", "reviewer": "Reviewer_F6kk", "summary": "The paper considers the problem of continually releasing private estimates of the number of distinct elements in a turnstile stream (with insertion and deletion of elements). It presents the first such algorithm that uses sublinear space while maintaining error similar to that of previous private algorithms (that use linear space).\n\n## Update after rebuttal\nThe rebuttal confirms my assessment", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments and valuable feedback. \n\nOn using Misra Gries to track elements with high occurrency instead of blocklisting, we note that our algorithm’s goal is not to output elements with high occurrency but simply to filter them out at every timestep. While it is possible to implement a version of the Misra Gries algorithm that continually outputs items with high occurrency, our blocklisting method is simpler as it only involves sampling with a fixed probability.\n\nThanks for your comment on the use of KSET vs other techniques like IBLT. We have considered using other more complex (and advanced set structures) — it is an interesting direction to pursue, in part because other methods like IBLT can reduce the space used by polylog factors. However, we chose to use KSET because for the DP guarantees, we need to open the black box of the algorithm and analyze its consistency properties (something that is not needed for non-private work). The largely consistent output for KSET in the presence of increased collisions makes it more amenable to analysis in DP settings. We stress that even our use of the simpler to analyze KSET method in the DP setting requires significant care especially when dealing with the failure cases. \n\nQ1: For the comment on the “output being a multiple of a power of 2”, first we observe that actually the output is the product of $2^i$ times a real value (a DP estimate from a count + gaussian noise) so it is not actually an integer power of two (even after rounding). This aspect is however not crucial for the accuracy proof (see below). The scaling up by a factor of $2^i$ is to account for the sampling rate of $2^{-i}$ in the $i$-th stream. In terms of how this relates to our accuracy guarantees (and in particular, our $(1+\\eta)$-approximation guarantee), we note that our accuracy guarantee follows from the proof of Lemma A8 in appendix, which shows how our sampling rate is sufficient to give accuracy of the output of the substreams in terms of $(1+\\eta)$ multiplicative error plus some additive error. This is because we only need the number of distinct elements in the downsampled stream to be within a multiplicative constant (specifically, 2) range for the concentration bounds to hold with the desired multiplicative approximation and with the allowed additive error. Notice as we discuss in the introduction of our paper, any low-space private algorithm for this problem must incur both multiplicative and additive error.\n\nQ2 & Q3: Regarding the hash functions (and whether they need to be fully random), our construction only requires $\\lambda$-wise independent hash functions. Specifically, we use pairwise independent hash functions for the KSET subroutine and $\\lambda$-wise independent hash functions for the CountDistinct subroutine. The space complexity for the latter is $O(\\lambda \\log T)$, which simplifies to $O(polylog(T))$, and thus remains efficient in our setting. We note that using universal hash functions might introduce dependencies as it only ensures low collision probability for any pair of elements, and this may affect utility. In particular, our utility analysis relies on a concentration bound (Lemma D.5) for $\\lambda$-wise independent hash functions and thus would need to change if we use universal hash functions instead.", "claims_and_evidence": "The paper is theoretical. All claims are backed by proofs.", "methods_and_evaluation_criteria": "There is no empirical evaluation.", "theoretical_claims": "The approach and the proof statements make sense. I have a few technical questions (below) that I could not easily answer myself. Though I did not check all details there seems to be no reason to suspect fundamental problems with correctness.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper is a timely follow-up to the recent work on tracking distinct elements under continual observation (NeurIPS '23), making progress on one of the main open problems from that work. This seems like a fundamental problem with multiple potential applications, but most past work has focused on the single-release setting.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "It appears that the paper could be simplified somewhat by substituting some of the building blocks. For example, the Misra-Gries algorithm (cited in the paper) could be used to keep track (separately) of the insertions and deletions in the stream, guaranteeing that all elements with occupancy (or flippancy) at least W are detected. This seems simpler than the current Theorem 1.3 and avoids the error probability.\n\nIn a similar vein, the KSET structure is not a modern solution. Invertible Bloom Lookup Tables, IBLTs (in various forms) give the functionality you need with good space usage, speed, and low error probability. \n\nI have a few technical questions/concerns (questions below) but given the expected answers I do not think they are serious.", "other_comments_or_suggestions": "-", "questions_for_authors": "- In Algorithm 1, line 22 you always output a multiple of a power of 2. I wonder how this is compatible with relative error arbitrarily close to 1?\n- Do you assume that the hash functions used are fully random? If the space for the hash functions is not counted this requires some discussion.\n- Would implementing the method with, say, universal hashing potentially impact privacy, utility, or both?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VPQXpUt0WD", "reviewer": "Reviewer_M6qz", "summary": "This paper studies the classical problem of counting distinct elements in a streaming (bounded space) setting, under differential privacy constraints in the continual release model (where the requirement is to provide an output at all times along the stream, while retaining differential privacy as usual). The main result is a $(1+\\eta)$-approximation algorithm with $O(T^{1/3})$ space and additive error. It is known that a polynomial additive error is needed in this setting, from work of Jain, Kalemaj, Raskhodnikova, Sivakumar, and Smith in NeurIPS'23 (henceforth JKRSS) who showed an $\\Omega(T^{1/4})$ additive error lower bound among other results. Notably, the JKRSS paper did not consider sublinear-space algorithms, and presented the question of obtaining such algorithms as an open problem, which the current paper resolves.\n\nThe main conceptual contribution of the current paper is a notion called the occurrency. The occurrency of a single element from the universe w.r.t. the stream is the number of times this element appears in the stream (both insertions and deletions count), and the maximum occurency in the stream is simply the maximum among all elements. Note that high occurrency items are simply heavy hitters (in an insertion only sense, where the number of occurrences always goes up, regardless of the sign). \n\nTo achieve the above bound, the authors combine an algorithm suitable for low-occurrency elements with a separate algorithm dealing with the heavy hitter elements that appear a lot of times (high occurrency items). One algorithm deals with all elements up to occurrency $W$, where $W$ can be an artificial upper bound (or simply the maximum occurrency), and achieves roughly $\\sqrt{W}$ space and $\\sqrt{W}$ additive error. The other algorithm deals with heavy hitters and has space bound $O(T/W)$. Setting $W = T^{2/3}$ achieves the aforementioned $O(T^{1/3})$ result. (Here I omitted lower order terms.)\n\nThe analogue notion used in JKRSS is that of flippancy. The flippancy of an item is the maximum number of items it flipped from 1 or -1 to 0 or vice versa. In their work they obtained an algorithm whose additive error is of order $\\sqrt{F}$, where $F$ is the flippancy. Because the flippancy is bounded by the occurency and can be much smaller, the additive error of the JKRSS approach can be much better than the current paper. However, the space complexity of their approach is not sublinear, so the main saving here is in terms of space.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and valuable feedback.\n\n**Connections to heavy hitters:** \nWe agree that there is a conceptual connection to the heavy hitters problem, as high-frequency elements can be viewed as heavy hitters, especially in the insertion-only setting. However, in the turnstile setting, an element may have high occurrency without being a heavy hitter in the frequency estimation sense: for example, if the element is very frequently added to and removed from the stream. As a result, the goal of our work is different from the heavy hitters problem: we are not trying to identify these high-occurrency elements, but simply to filter them out as items arrive. For this purpose, a simple probabilistic blocklisting approach suffices, and there is no need to apply a heavy hitters algorithm. Moreover, as shown by our lower bound, our blocklisting technique is space-optimal (up to log factors), so the potential improvements from using heavy-hitter algorithms as a form of blocklisting (e.g., use HH algorithms to identify high-occurency algorithms, and treating these as the blocklisted elements)  is limited. We will add a discussion to the final version of the paper on the connection of occurrency to the heavy hitters problem, as well as the differences that arise in the turnstile model specifically.\n\n**Differences from robust streaming:**\nThe problem studied in this work and our approach to solving it are in fact different from the robust streaming literature. Here we highlight these differences in the context of lp-moment estimation. The goal of the robust streaming literature is to design algorithms that can give meaningful utility and (low) space guarantees for lp-moment estimation in the presence of an adaptive adversary, which can generate inputs to the stream based on previous timesteps and feed this to the algorithm in the next timestep. In this model, the algorithm can output an approximation at every timestep, but the **output does not need to preserve privacy** as in our DP algorithms. In contrast, in the continual release model, the algorithm is required to output a solution at every timestep and these outputs must also preserve DP. As a result, the two problem settings are not comparable and the solution for one problem cannot in general be used to solve the other problem (especially if efficient and accurate solutions are desired).\n\nThe DP techniques introduced in [1] and subsequently used in works like [3,4] in the robust streaming literature are different from ours and are intended for a different purpose. Thus it is not possible to directly use prior work in the area to solve our problem (or vice versa). Importantly, the main DP technique introduced by [1] is used to preserve the privacy of the internal **randomness of the algorithm**,  but not to preserve the privacy of the algorithm’s **input**. As such, these algorithms do not protect the privacy of the user data in input: the adversary can infer information about the user’s data in the input, but is not able to learn about the random bits used (thus making adaptive attacks to the utility of the algorithm harder). \n\nWe emphasize that the solutions of [3,4] do not preserve DP at every timestep. For example, [3] devises a solution for lp-moment frequency estimation by separating the cases of when the underlying frequency vector is sparse vs dense. For the sparse case, their algorithm stores the input explicitly using sparse recovery whereas for the dense case they use the DP technique from [1]. Thus for the sparse case, their output is non-private as it is directly computed from the sparse recovery structure. \n\nIn contrast, because our goal is to preserve the privacy of the input stream at every timestep, our DP techniques need to differ from the ones used in the robust streaming literature. While we also use sparse recovery tools such as KSET, we must ensure that the output of the KSET does not leak privacy by analyzing its consistency properties (towards sensitivity analysis), and use DP building blocks adapted to our problem such as BM-CountDistinct (Algorithm 5). \n\nRegarding flippancy vs flip number, we emphasize that the concept of flippancy was introduced by [Jain et al] and we show in our work that it may not be a suitable measure to design low space algorithms in the DP turnstile model due to its stateful nature (L91-108), which is the main motivation for introducing occurrency instead. In general, the flip number is a property intrinsic to the problem being computed, while the flippancy (and occurrency) is a property intrinsic to the input stream (regardless of the problem). Thus these two measures are somewhat incomparable.", "claims_and_evidence": "Yes, this is a theoretical paper and the claims are proved.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "I did not read the proofs, but I have a rough understanding of how to prove these results and am pretty sure they should be correct.", "experimental_designs_or_analyses": "None, this is a theoretical paper.", "relation_to_broader_scientific_literature": "The paper improves upon the Jain et al. paper in terms of space complexity. The results are quite similar to the dense-sparse tradeoffs literature in adversarially robust streaming, see detailed discussion in the next bullet.", "essential_references_not_discussed": "Occurency is very closely related to the notion of a a heavy hitter. An element has high occurency if and only if it is a heavy hitter, when we consider the turnstile stream an insertion only one. You should connect this notion to the heavy hitters literature and provide ample context.\n\nYour result is very reminiscent of several dense-sparse tradeoffs works in robust streaming (that is, streaming against an adaptive adversary while providing continual output). It is well known by now that differential privacy is a central tool in robust streaming [1]. The DP-based approach of [1] achieves, for a global notion called flip number [2] (denote it by $\\lambda$) (which differs somewhat from flippancy, though there are some similarities) roughly $\\sqrt{\\lambda)$ space and $\\sqrt{\\lambda}$ additive error (which is hidden in [1] in the computation of a DP median). \n\nThe dense-sparse robust streaming work of [3] achieves $T^{1/3}$ space complexity by combining the DP-approach with sparse recovery (whereas your work combines a similar variant of the former with a heavy hitters approach). \nThe work of [4] gets a dense-sparse tradeoff by using heavy hitters. I strongly recommend you to read [3] and [4] and see how your work compares to them. Your use of KSET seems to be novel.\n\n[1] A. Hassidim, H. Kaplan, Y. Mansour, Y. Matias, U. Stemmer, \"Adversarially robust streaming algorithms via differential privacy\", JACM 2022. Preliminary version in NeurIPS 2020.\n[2] O. Ben-Eliezer, R. Jayaram, D. Woodruff, E. Yogev, \"A frame for adversarially robust streaming algorithms\", JACM 2022, preliminary version in PODS 2020.\n[3] O. Ben-Eliezer, T. Eden, K. Onak, \"Adversarially robust streaming via dense--sparse trade-offs\", SOSA 2022.\n[4] D. Woodruff, S. Zhou, \"Adversarially robust dense-sparse tradeoffs via heavy-hitters\", NeurIPS 2024.", "other_strengths_and_weaknesses": "This paper is very well written -- I enjoyed reading it.", "other_comments_or_suggestions": "See \"essential references not discussed\".", "questions_for_authors": "I do not have questions for the authors; however I do think it is important that they address my comments in the \"essential references not discussed\" section.\n\nI am not opposed to increasing your score, provided that you will be able to convince me that your approach is meaningfully different from what is done in the robust streaming literature (see references above).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}]

Author rebuttal:

Meta-review: The paper presents a new space-efficient algorithm for differentially private counting of distinct elements under the turnstile model of continual release. In this setting, at each step of the execution, the algorithm observes the next update in the stream (an insertion or deletion) and releases an updated estimate of the current number of (remaining) distinct elements. The proposed algorithm improves the space complexity over prior work while maintaining a competitive additive error. The reviewers all agree that the results are strong and the techniques are interesting. This paper would be a valuable addition to ICML.
Decision: Accept (poster)