Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation
Authors: Palak Jain
Iden Kalemaj
Sofya Raskhodnikova
Satchit Sivakumar
Adam Smith
Venue: NeurIPS 2023 poster (2023)
Keywords: distinct elements
differential privacy
continual release
turnstile streams
TL;DR: We show new algorithms and lower bounds for the private continual release of the number of distinct elements in turnstile streams

Abstract: Privacy is a central challenge for systems that learn from sensitive data sets, especially when a system's outputs must be continuously updated to reflect changing data. We consider the achievable error for differentially private continual release of a basic  statistic---the number of distinct items---in a stream where items may be both inserted and deleted (the turnstile model). With only insertions, existing algorithms have additive error just polylogarithmic in the length of the stream $T$. We uncover a much richer landscape in the turnstile model, even without considering memory restrictions. We show that every differentially private mechanism that handles insertions and deletions has worst-case additive error  at least $T^{1/4}$ even under  a relatively weak, event-level privacy definition. 
Then, we identify a parameter of the input stream, its maximum flippancy, that is low for natural data streams and for which we give tight parameterized error guarantees. Specifically, the maximum flippancy is the largest number of times that the contribution of a single 
item to the distinct elements count changes over the course of the stream. We present an item-level differentially private mechanism that, for all turnstile streams with  maximum flippancy  $w$, continually outputs the number of distinct elements with an $O(\sqrt{w} \cdot \mathsf{poly}\log T)$ additive error,  without requiring prior knowledge of $w$. We prove that this is the best achievable error bound  that depends only on $w$, for a large range of values of $w$. When $w$ is small, the error of our mechanism is similar to the polylogarithmic in $T$ error in the insertion-only setting, bypassing the hardness in the turnstile model.

Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation
Palak Jain Boston University palakj @bu. edu
Iden Kalemaj Boston University emu edu
Sofya Raskhodnikova
Satchit Sivakumar Boston University satchit@bu. edu
Adam Smith
Boston University sofya@bu. edu
Boston University ads a2db2. edu
Abstract
Privacy a central challenge for systems that learn from sensitive data sets, espe- cially when system'' 's outputs must be continuously updated to reflect changing data, We consider the achievable error for differentially private continual release of basic statistic- the number of distinct items-in in stream where items may be both inserted and deleted (the turnstile model). With only insertions, existing algorithms have additive error just polylogarithmic in the length of the stream T. We uncover a much richer landscape in the turnstile model, even without consid- ering memory restrictions. We show that every differentially private mechanism that handles insertions and deletions has worst-case additive eπrо least / even under a relatively weak, event-level privacy definition. Then, we identify a parameter of the input stream, its maximum flippancy, that low for natural data streams and for which we give tight parameterized error guarantees. Specifically, the maximum flippancy is the largest number of times that the contribution of a single item to the distinct elements count changes over the course of the stream. We present item-level differentially private mechanism that, for all turnstile streams with maximum flippancy w. continually outputs the number of distinct elements with an O(yw- / poly log T') additive error, without requiring prior knowledge of w. We prove that this is the best achievable error bound that depends only for large range of values of w. When small, the error of our mechanism similar to the polylogarithii in T error in the insertion-only setting, bypassing the hardness in the turnstile model.
Introduction
Machine learning algorithms are frequently run sensitive data. In this context, central challenge to protect the privacy of individuals whose information is contained in the training set. Differential privacy [27] provides a rigorous framework for the design and analysis of algorithms that publish aggregate statistics, such as parameters of machine learning models, while preserving privacy. this work, focus on the model of differential privacy interchangeably called continual observation and continual release that was introduced by Dwork et al. [25] and Chan et al. [13] to study privacy in settings when both the data and the published statics constantly updated. One of the most fundamental statistics about a data stream is the number distinct elements it contains (see, e.g., the book by Leskovec al. [47]). The problem of counting distinct elements has been widely studied, starting with the work of Flajolet and Martin [32], and has numerous applications [2, 30, 49, 42, 4], including monitoring the number of logins from distinct accounts streaming service, tracking
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the number of different countries represented by people in a chat room, and tracking the number of students signed up for at least one club university. Algorithms for this problem are also used as basic building blocks in more complicated data analyses.
We investigate the problem of privately counting the number of distinct elements under continual observation in the turnstile model, which allows both element insertions and deletions. In the continual release model, a data collector receives a sensitive dataset as stream of inputs and produces, after receiving each input, an output that is accurate for all inputs received so far. The input stream is denoted x and its length (also called the time horizon) is denoted T. The elements come from a universe U. Each entry in the stream is an insertion (denoted by +-)) or deletion (denoted by -u) of some element u E u/ or, alternatively, a no-op (denoted by L). representing that no update occurred
in the current time step. More formally, for a universe Lt, let _ denote the set {+.- -} } x U U { of possible stream entries. The shorthand +u and -u is used for the pairs (+, u) and (-, u). Given a
vector x of length T and an integer E [7], the vector ar1 t] denotes the prefix of x consisting of the first entries of x.
Next, we define the function CountDistinct in the (turnstile) continual release model.
Definition 1.1 (Existence vector, CountDistinct), Fix a universe U and a time horizon T E N. For element E U and stream E Uf, the existence vector fa( {0, 13 is an indi- cator vector that tracks the existence of element u in x: specifically, for each t E [T, the value f=())(t] = 1 if and only if there are strictly more insertions than deletions of element in 2[1 : t). The function CountDistinct -TI - N" returns a vector of the same length as its input, where CountDistinct(x))( Eneu [u(x)(() for all E [T]-
The focus of our investigation is the best achievable error in the continual release model for a given time horizon T and privacy parameters. We study the worst-case (over all input streams and time steps f) additive error of privately approximating the distinct elements counts under continual release. Definition 1.2 (Error of an answer vector and error of a mechanism for CountDistinct). Given an answer vector a E TR.,, the error of this vector with respect the desired function value f(x) E T computed on dataset x is defined as ERR, (z, a) = [I((x)) - alloo- A mechanism for CountDistinct in the continual release model is o-accurate it outputs a vector of answers a with error Co, a) S. a with probability at least 0.99.
Next, we discuss privacy. Originally, differential privacy [27] was defined in a setting where data collector outputs the desired information about an entire dataset all at once. We call this the batch model contrast with continual release. In the batch model, two datasets are called neighbors they differ in the data of one individual. There are two natural ways to adapt this definition to the continual release model [25, 13], depending on the desired privacy guarantees.
Definition 1.3 (Neighboring streams). Let x., x' UL be two streams of length T. Streams x and x' are event-neighhors if one can be obtained from the other by replacing a stream entry with L. Streams and x' are item-neighbors one can be obtained from the other by replacing subset of stream entries pertaining to one specific element of U with symbol 1.
Differential privacy can be defined with respect to any notion of neighboring datasets. There are two privacy parameters: >> O and 5 E [0, 1). An algorithm A is (e. -)iffeerrnt private (DP) if for all pairs of neighboring datasets v. a' and all events S in the output space of A,
Pr[A(#) E S] S ef Pr[A(x') E 6
The case when 5 = 0 is referred to as pure differential privacy, and the general case as approximate differential privacy. For went-neighboring (respectively, neighbbbbbbrr)g) streams x, x' E uf, say that A is (e, 8) -veent-leeel- DD (respectively, item-levei-DPP. Item-level differential privacy imposes a more stringent requirement than event-level, since it guards against larger changes in the input stream. To contrast with the batch setting, we refer to continual release algorithms as mechanisms.
In the batch setting, where only (ountDisiintt())(7] is released, there is an e-DP algorithm for counting distinct elements with expected error ((1/e) since the function CountDistinct(2)) has sensitivity 1- regarddlss of whether we consider event-level or item-level privacy. Privacy is more challenging in the continual release setting, where we aim to release a sequence of estimates, one for each time t, and we require that the privacy guarantee hold for the entire sequence of outputs.

---

Bounds
Item- Item-Level Privacy
Event-Level Privacy
δ (min (V'w log T + log T)
Vlog 1/6
log 1/8) ,T)) )
(Thm. 1.5)
Upper
22/3
Lower
2s
min
yeu
T:/3 22/3 ) (Thm. 1.7)
,T,)))
min
w
T 274
T
(Thm. 1.6)
Table I: Summary of our results: bounds the worst-case additive error for CountDistinct under event-level and item-level (s, d)ddiferret privacy, with e I 1 and = of of Upper bounds depend on the maximum flippancy wa of the input x, for every Lower bounds apply to the worst-case error of an algorithm taken over all inputs with a given maximum flippancy.
Prior work on privately estimating distinct elements in this setting considered the insertion-ons only model, exclusively: Bolot et [9] show that one can get sequence of estimates, all of which are within additive error poly(log /s. Their result holds for both item-level and event-level privacy (which are essentially equivalent for counting distinct elements with only insertions). Follow-up work generalized their mechanism but, again, considered only insertions [35, 29].
We uncover much richer landscape in the turnstile model, restrictions. We show that any differentially private mechanism that handles insertions and deletions has worst-case additive error at least T /4 even under event-level privacy, the weaker of the two privacy notions. To overcome this lower bound, flippancy, that is low for natural data streams and for which one can give tight parameterized error guarantees. To define flippancy, recall the notion of the existence vector from Definition 1.1.
without considering memory
identify a property of the input stream, its maximum
Definition 1.4 (Flippancy). Given stream of length T and an element u E U, the flippancy of in x. denoted by flip(u, z), is the number of pairs of adjacent entries in the existence vector fa(x) with different values. That is, flip(u, = H E T - 1]: fo (z)(i) # f=(x)]i j + 1]H The maximum flippancy of a stream x, denoted w, is max flip(u. 2))
In other words, the maximum flippancy is the largest number of times the contribution of a single item the distinct elements count changes over the course of the stream. We design item-level private mechanisms whose error scales with the maximum flippancy of the stream, even though the maximum flippancy not input to the mechanism. We show matching lower bounds for item-level privacy that hold in all parameter regimes. For a large range of the flippancy parameter, we also show a matching lower bound for event-level privacy, via a different argument. This leaves range with an intriguing gap between item-level and event-level bounds.
1.1 Our results
Our results summarized in Table 1. Our first result is mechanism for privately approximating CountDistinct for turnstile streams. For a stream x of length T with maximum flippancy Wz- this mechanism item-level-DP and has error O (min(y -uilly/--pooylog T, T1/3). Crucially, the mechanism is not given the maximum flippancy upfront.
Theorem 1,5 (Upper bound). For all e, E (0,1] and sufficiently large T E N, there exists an (E, 8) -item-leevel-DP mechanism for CountDistinct that is a-accurate for all turnstile streams z of length T, where
a= à a=0(min (in ((/mz log" T) Vlog 1/5 (T log 1/8) 1/3
T )
2/3
and w, is the maximum flipancy of the stream x.
Since this mechanism is item-level-DP, it is also event-level-DP with the same privacy parameters. The error it achieves is the best possible in terms of dependence only w, for item-level privacy, and this error is nearly tight for event-level privacy. When wy is small, as is the case for many natural streams, our mechanism has error Opolylog 7"), similar to mechanisms for the insertion-only setting.
Theorem 1.5 can be easily extended & bounded by any constant larger than 1. We fixed the bound to be 1 to simplify the presentation. Our mechanism has polynomial time and space complexity in the
3

---

input parameters, although it does not achieve the typically sublinear space guarantees of streaming algorithms. (See "Bounded Memory" in Section 1.4 for discussion.)
Our lower bounds on the accuracy for CountDistinct for turnstile streams are parametrized by a flippancy bound w, and apply for streams with maximum flippancy wx S For event-level DP, our lower bound shows that for all mechanisms with error guarantees expressed solely in terms of the maximum flippancy Wy, time horizon T, and privacy parameter E, our Count asymptotically optimal for large range of values of w'z, namely, for all W2 S / and wa T2/3 for event-level DP remains open problem.
mechanism is
The best achievable error for wa E /T'
Theorem 1.6 (Event-level lower bound). Let e, 8 E (0, 1), and sufficiently large w, T E N such that w T. For all (e, 8) -eeentt--eeel--D mechanisms that are o--accurate for CountDistinct on turnstile streams of length T with maximum flippancy at most w, if = o(
V T/4
Ω min
3/4 T
In particular, any accuracy bound for event-level algorithms depending only Wz, as in Theorem 1.5, must grow as 52 min y T3/4 .)) in all ranges of Wg. This is reflected in Table 1.
For item-level DP, lower bound the error matches our upper bound for all regimes of w2 up to polylogarithmic factors.
Theorem 1.7 (Item-level lower bound). Let E E (0, 11, 5 E (0, 1], and sufficiently large w. T E N such that w S T. For all (e, 8) ----tee---ee mechanisms that are o-accarate for CountDistinct on turnstile streams of length T with maximum flippancy at most w,
1 If 8 o(E/T), then 52 min
y
T2/3
e273 .T.TT) (278.T))
2 If 5 = 0, then = 2 min e T.T)
In particular, any accuracy bounds depending only on we must grow at least as quickly as the expressions in Table 1.
Variants of the model. All our lower bounds also hold in the strict turnstile model, where element counts never go below 0. They also apply to offline mechanisms that receive the entire input stream before producing output; they do not rely on the mechanism's 's uncertainty about what comes later in the stream. Furthermore, our item-level lower bounds hold even in the model where each element can be inserted only when it is absent and deleted only when it is present (as is the case, for example, with the "like" counts on social media websites).
1.2 Our techniques
Upper bound techniques: tracking the maximum flippancy. Before describing our algorithmic ideas, we explain the main obstacle to using the techniques previously developed for insertion- only streams [9, 29] in the turnstile setting. Bolot et al. [9] and Epasto et al. [29] used reduc- tion from CountDistinct to the summation problem. A mechanism for the summation problem outputs, every time step E [T]. the sum of the first elements of the stream. Dwork et al. [27] and Chan et al. [13] designed the binary-tree mechanism to obtain a Oppolylog aaaaccuraee mechanism for summation. Given input stream x of length T (to the CountDistinct problem), define a corresponding summation stream 8, E (-1,0, 1) At time step 1 E [T). the entry sy (t] equals the difference in the count of distinct elements between time steps - 1]. Then CountDistinct(x)) [t] is precisely the sum of the first elements of s.. In the insertion-only model, changing one entry of æ changes most 2 entries of $z, and thus, by group privacy, the binary-tree mechanism has Oppolylog T') additive error for CountDistinct. For turnstile streams, even under the weaker notion of event-level privacy, a change in the stream can cause I2(T) changes to sg. To see this, consider the stream consisting of alternating insertions (++) and deletions (-u) of a single element u E U, and its event-neighboring stream where the first occurrence of +u is replaced with 1. This example illustrates that one of the difficulties of the CountDistinct problem for turnstile streams lies with items that switch from being present absent multiple times over the course of the stream, that is. have high flippancy. We present
and t, i.c..
s. i] = CountDistinct( [t][ - CountDistinct(

---

a private mechanism that outputs estimates of the count of distinct elements in a turnstile stream with optimal accuracy in terms of maximum flippancy.
Our first key idea allows us to obtain a mechanism, Algorithm 1, that is given as input a flippancy upper bound w. For stream whose maximum flippancy is bounded by w. changing to item- neighbor of æ causes at most 2w changes to the corresponding summation stream sg. This observation, combined with a group privacy argument, gives mechanism with error O(w polylog T) directly from the accuracy guarantee of the binary-tree mechanism for summation. Previous works in the insertion-only model [9, 29] used precisely this approach for the special case w 1. To obtain the better v dependence on w in our upper bound, we "open up" the analysis of the binary-tree mechanism. By examining the information stored in each node of the binary tree for the summation stream, we show that changing the occurrences of one item in a stream x with maximum flippancy at most w can change the values of at most w nodes in each level of the binary tree. The / dependence in the error then follows from the privacy guarantees of the Gaussian mechanism (used inside the binary-tree mechanism) for approximate differential privacy. This type of noise reduction makes crucial use of the binary tree approach: there are optimized noise addition schemes for prefix sums that improve quantitatively over the binary-tree mechanism (see, e.g. [18, 4IJ. but it is unclear they allow the same noise reduction. While our mechanism is only accurate for streams with maximum flippancy at most w. it is private even for streams that violate this condition. To achieve this, our mechanism ignores stream elements after their flippancy exceeds
The second key idea allows our algorithms to adapt automatically to the maximum flippancy w, of the input, without the need for an a-priori bound w. We design a private mechanism, Algorithm 3, that approximately keeps track of the maximum flippancy of the prefix of the stream seen so far and invokes our first mechanism (Algorithm 1) with the current estimated maximum flippancy úo as an input. Our main innovation lies in the careful application of the sparse vector algorithm [24] to track the maximum flippancy of the stream, We cannot do this directly, since the sparse vector algorithm achieves good utility only for queries of low sensitivity, and maximum flippancy has global sensitivity ((T) under item- changes.
Instead, we track a low sensitivity proxy that indirectly monitors the maximum flippancy wz: given the current estimate á of the flippancy, we use the sparse vector algorithm to continuously query the number of items in the stream with flippacyy above u. This query has sensitivity one for item-level neighbors, as desired, but it is not priori clear how to use it to upper bound the maximum flippancy of the stream. This is remedied by observing that Algorithm invoked with a flippancy bound w, has the same error (and privacy) guarantee even if at most V items in the stream have flippancy higher than ú. That is, an exact upper bound on the maximum flippancy is not needed to design an accurate mechanism. Items that violate the flippancy bound are safely ignored by Algorithm and do not contribute to the distinct elements count.
When the number of high-flippacy items gets large, we adjust the estimate v and invoke new instantiation of Algorithm 1. By doubling ú each time this happens, we ensure that it remains at most twice the actual maximum flippancy Wy. and that we need only invoke log T different copies of Algorithm 1 and the sparse vector algorithm'. With these ideas, we obtain an item-level private mechanism that, for all streams 2;, has error that scales with WWy..
Lower bound techniques. Our lower bounds use the embedding technique introduced by Jain et al. [44] to obtain strong separations between the batch and continual release models of differential privacy. The approach of Jain et al. embeds multiple separate instances of an appropriately chosen base problem on the same sensitive dataset in the batch model into a single instance of a continual release problem. Then, the continual release mechanism can be used to solve multiple instances of the base problem in the batch model. The hardness results in the continual release model follow from lower bounds for the batch model.
key idea in our event-level lower bound is a connection between the inner product of two binary vectors and the count of distinct elements in the union of those indices where the vector bits equal Estimates of distinct elements counts can thus be used to estimate inner products on sensitive dataset of binary bits. Lower bounds on the accuracy of private algorithms for estimating inner product queries have been previously established in the batch model through the reconstruction attack of Dinur and Nissim [21]. This connection was used by Mir et al. [50] to provide lower bounds for
All log expressions in this article base 2.
5

---

pan pan-private algorithms for counting distinct elements. However, continual release and pan- -riivaey are orthogonal notions, and their results don't 't imply any lower bounds in our setting, We crucially use deletions to embed multiple instances of inner product queries into a stream: once query is embedded and the desired estimate received, the elements inserted to answer that query can be entirely deleted from the stream to obtain a "clean slate" for the next query. We obtain a lower bound of / on the error of event-level private mechanisms for CountDistinct in turnstile streams.
We obtain stronger item-level lower bounds (for pure and approximate differential privacy) by embedding multiple instances of a 1-way marginal query. We then apply lower bounds of Hardt and Talwar [38] and Bun et al. [12] for releasing all 1-way marginals in the batch model in conjunction with our reduction. The 1 1-way marginals of a dataset y E {0. 1 consisting of nt records and d attributes, are the averages of all d attributes of y. Deletions in the stream are once again crucially used to embed a marginal query for one attribute and then clean the slate for the next attribute. Changing one record/row in the dataset y translates d changes of item in the constructed stream, and thus this reduction is particularly tailored to item-level lower bounds.
1.3 Related work
The study of differential privacy under continual release was initiated by two concurrent works [25, 13]. They proposed the binary-tree mechanism for computing sums of binary bits. The binary- tree mechanism has found numerous applications in the continual release setting and elsewhere, demonstrating the versatility of this mechanism. Under continual release, it has been extended to work for sums of real values [52]. weighted sums [9], graph statistics [55, 31], and most relevantly, counting distinct elements [9, 29, 35]. It has also been employed for private online learning [45, 57, 1] and for answering range queries [25, 26, 28].
Prior to our work, the CountDistinct problem with continual release was studied exclusively in the insertions-only model. Bolot et al. [9] were the first to study this problem and showed a O(log" 1.5 T)- accurate item-leeel-DP mechanism. Ghazi et al. [35] considered the more challenging blddingwwindor model and showed nearly-matching upper and lower bounds for this setting, parameterized by the window size, for item-level and event-level differential privacy. Epasto et al. [29] studied the more general e, fp-frequency estimation problem with a focus on space efficiency. For distinct elements, i.e. p 0, their mechanism provides an estimate with 1 ++) 17 multiplicative error and O(log" T) additive error, using space poly (log T/n). They also extended their results to the Bldding-windov model. Two of the works [9, 29] reduced the CountDistinct problem to the bit summation primitive, which allowed them to use the binary-tree mechanism. Since the streams are restricted be insertion-only. the bit summation primitives they considered have low constant sensitivity. The same primitives have sensitivity Q(T)) for turnstile streams, and thus this approach cannot be directly extended to our setting. Ghazi et al. [35] observed that for fixed and sliding windows, the distinct elements problem can be reduced to range queries. For the special case when the window is the entire stream, their reduction is to the summation problem.
In concurrent work, Henzinger et al. [40] studied CountDistinct with insertions and deletions in a different version of the continual release model (which we call the "likes" model), where an item can be deleted a time step only if it is already present in the stream at that time step, and inserted only if it is absent from the stream at that time step. Our model is more general, since multiple insertions and deletions of the same item can happen consecutively. Our upper bound and our item-level privacy lower bound can be extended to the 'likes" model. On the other hand, our event-level private lower bound provably does not apply to that model: in the 'likes' model, for event-level privacy, there is simple reduction to the bit summation problem in the continual release model such that the resulting algorithm incurs only a polylogarithmic in T error, whereas we show that in our model, any event-level private algorithm incurs polynomial in T error.
Henzinger et al. [40] showed error bounds for item-level privacy in the likes model that are parame- terized by the total number of updates K in the stream. The parameter K is related to our concept of flippancy: in the likes model, K equals the sum of all items' flippancies and, in general, is at least that sum. Henzinger et al. [40] give an (c, DP algorithm with error Ō(VK log T) and show a nearly matching lower bound on the error for (e, O)-DP algorithms using a packing argument. This lower bound applies to our model as well. is incomparable to our lower bounds, since it scales differently and depends on different parameter. In our model, their algorithm can be analyzed to give

---

error bounds in terms of the sum K' of the flippancies of the items and incurs error Ö(v K' log T); however,it is unclear if their algorithm can be analyzed in our model to give bounds in terms of the (potentially smaller) maximum flippancy.
Another line of work investigated private sketches for distinct elements, motivated by the popularity of sketching algorithms for the streaming setting. Mergeable sketches for counting distinct elements have received partieular attention [56, 15, 51, 391, since they allow multiple parties to estimate the joint count of distinct elements by merging their private sketches. While these sketches can be combined with the binary-tree mechanism obtain private mechanisms for CountDistinct, the utility deteriorates when many (log T') sketches are merged. In fact, Desfontaines et al. [19] showed that achieving both privacy and high accuracy is impossible when many sketches for counting distinct elements are merged. Other private sketches have been studied [54, 20, 58] for the streaming batch setting (without continual release). The distinct elements problem has also been studied in a
distributed setting [14, 34] and under pan-privacy [50]. In particular, our lower bound for event-level privacy uses ideas from the lower bound of Mir al. [50], as described in Section 1.2
The CountDistinct problem has been extensively studied in the non-private streaming setting, where the goal is achieve low space complexity [32, 16, 36, 37, 6, 5, 22, 43, 59, 30, 33, 10, 46]. Blocki et al. [8] showed a black-box transformation for every streaming algorithm with tunable accuracy guarantees into a DP algorithm with similar accuracy, for low sensitivity functions. Their transformation does not obviously extend to the continual release setting. Moreover CountDistinct has high sensitivity for turnstile streams.
The first lower bound in the continual release model of differential privacy was an alog 7)) bound on the accuracy of mechanisms for bit summation, shown by Dwork et al. [25]. Jain et al. [44] gave the first polynomial separation in terms of error between the continual release model and the batch model under differential privacy. Our lower bounds also show such separation. The lower bounds of Jain et al. [44] were for the problems of outputting the value and index of the attribute with the highest sum, amongst d attributes of dataset. Our lower bounds are inspired by their sequential embedding technique to reduce multiple instances of batch problem to problem in the continual release model. Similar to them, we also reduce from the 1 I-way marginals problem to obtain our item-level lower bound. However. our event-level lower bound involves reducing from different problem, and our reductions use the specific structure of CountDistinct for turnstile streams.
1.4 Broader impact, limitations, and open questions
We study the achievable error of DP mechanisms for CountDistinct under continual observation in streams with insertions and deletions. We show that it is characterized by the maximum flippancy of the stream. Our work is motivated by societal concerns, but focused on fundamental theoretical limits. It contributes to the broader agenda of obtaining privacy-preserving algorithms for data analysis. We discuss natural directions for future research and some limitations of our work.
We found the best achievable error in some settings, but our upper and lower bounds do not match in some parameter regimes. What the right error bound for event-level privacy for streams æ with maximum flippancy w. between /T and T2/3? Our results yield a lower bound of T1/4 and upper bound of roughly v/r..
Tight bounds:
Bounded memory: We did not consider any memory restrictions. Prior to our work, no other work addressed CountDistinct with deletions under continual release-wiit with without space constraints. We consider only the privacy constraint since it is more fundamental-aa cannot be avoided by buying more memory-an and the best algorithms with unbounded memory provide benchmark by which to evaluate space-constrained approaches.
Space complexity is certainly natural topic for future work. While it is not clear how to apply the sketching techniques of Epasto et al. [29] to the turnstile setting, it would interesting to come up with accurate, private, and low-memory mechanisms for counting distinct elements in turnstile streams. Such algorithms would necessarily mix multiplicative and additive error guarantees (due to space and privacy constraints, respectively).
7

---

1.5 Organization
In Section 2, we present a mechanism for privately approximating CountDistinct on turnstile streams. Preliminaries on differential privacy, proof' omitted from Section 2 as well as proofs of Theorems 1.6 and 1.7 all appear in the supplementary material.
2 Item-level private mechanisms for CountDistinct
In this section, we present our item-level-DP mechanism for CountDistinct for turnstile streams. Its guarantees are stated in Theorem 2.1 with zero Concentrated Differential Privacy (zCDP). Using this notion of privacy, one can show tight bounds for the Gaussian mechanism and cleaner and tighter bounds for composition. Theorem 2.1 is the key ingredient in our proof of Theorem 1.5. This section dedicated CountDistinct mechanism and the main ideas behind it. All proof's are deferred to the supplementary material.
Theorem 2.1 (Upper bound). For all p e (0, 1] and sufficiently large N, there exists a p-item- level->CDP mechanism for CountDistinct that is a-accurate for all turnstile streams x of length T, where
a = 0 Wir log T + llog"
vp
and we is the maximum.lippanccy flippancy of the stream x.
In Section 2.1, we describe a modification the binary-tree mechanism which, when analyzed carefully, provides the desired error guarantees- but only if the maximum flippancy of the stream is known upfront. Section 2.2, we use this mechanism, in conjunction with a method for adaptively estimating the flippancy bound, to obtain our item-level-DP mechanism for CountDistinct.
2.1 Enforcing a given flippancy bound w
When a flippancy upper bound is given upfront, we leverage the structure of the binary-tree mechanism to privately output the number of distinct elements at each time E [T]. where 7 is the stream length. The mechanism and its error guarantees are presented Algorithm and Theorem 2.2, respectively. To provide intuition, we first describe the mechanism when it is run on streams with maximum flippancy most w. We then discuss a modification that ensures privacy of the mechanism for all streams regardless of maximum flippancy.
Algorithm 1 stores vectors fa E (0, 13T for all elements u E Z that appear in the stream. For streams with maximum flippancy at most w, the vector fu is equal to the existence vector fa, In this case, by Definition 1.1, the number of distinct elements at timestep & E [2'] equals Σnsu ful4]. The mechanism outputs values Eveu fult] with Gaussian noise added according the binary-tree mechanism, with privacy parameter z p/w w (see Definition 2.4) that is, with noise scaled up by factor of /w/p. The accuracy of this mechanism follows from that of the binary-tree mechanism.
However, if the mechanism computed fu instead of fu. would be private for streams with maximum flippancy greater than w, since it adds noise that scales according to w. That is because for every stream x E 2T with maximum flippancy Wx > there exists a neighboring stream x' such that the vectors Count and CountDistinctt(")) differ in as many as θ (wwz) indices. To provide privacy for such streams, the mechanism simply "truncates" the vector fu E {0, 1)" to obtain fal!] = for 2 t" if the flippancy of u in æ[1 ("] exceeds w. This corresponds to running the naive version of the mechanism (that uses fa instead of f..) on the "truncated" version of the stream x, where elements in x are ignored after their flippancy exceeds w. (Note that the computation of fu can be done online since [u[t]] depends only on x/1 t).) With a careful analysis of the value stored in each node of the binary tree, are able show that this mechanism is D-item-level-zCDP for all streams, however, loses accuracy for streams with many high flippancy elements. In Section 2.2, leverage this mechanism to provide estimates of CountDistinct that are both accurate and private for all streams.
Theorem 2.2 (Mechanism for a given flippancy bound w). Fix p E (0, 1), sufficiently large E N, and < T. Algorithm I is mechanism for CountDistinct for turnstile streams that is p-item-
8

---

level-2CDP for all input streams of length T, and a-accurate for streams of length T with maximum flippancy at most w, where a = O Vie log T+ T
/P
Algorithm Mechanism M for CountDistinct with given flippancy bound
Input: Time horizon T E N, privacy parameter p >>>>> 0, flippancy bound w 0, stream x E U4
Output: Vector s E Rx of distinct count estimates
1: Sample a binary-tree random variable I² with parameter p' = Awoflo 7+1)
Definition 2.4
2: Initialize Ug 0
3: for all E [7' do
4: Obtain entry xr[t] and skip to Step 10 if x|t] =
5: Suppose x[t] is an insertion or deletion of a universe element u
6: if u $ Ur then insert into Uz: initialize count,, = 0 and fú = 0" clse count,
D. vector with T zeros
7:
if 1o [4] + then count,,
8:
for all u E Us do
9: if flip(U, x11 f)) S w and count, then set feld) =
10: Return s stt] = (E fult)) + Z(t]
Definition 2.3 (Dyadic decomposition). For L E N, the dyadic decomposition of the interval (0, () is a set of at most log + disjoint intervals whose union (0, obtained as follows. Consider the binary representation oft t (which has at most logt t bits), and express t sum of distinct powers 2. Then, the first interval is (0, r), where r is the largest power of 2 in the sum. The second interval starts at + 1 and its size is the second largest power of in the sum. The remaining intervals are defined similarly for all remaining summands. For example, for decomposition of (0, 11] is the intervals (0, 8). (8, 10] and (10, 11].
11 + 2 + 1, the dyadic
Definition 2.4 (Binary tree and binary-tree random variable). Let > be a privacy parameter and T N be power 2. Consider complete binary tree with T leaves whose nodes are labeled as follows. The T leaves are labeled by the intervals (t - 1, f, for all t & [T] and the internal nodes are labeled by intervals obtained from the union of their children's 's intervals. Specifically, the binary tree consists of log T + levels. A level E E [0, log T'I partitions the interval (0, T into a set of L z
2 i 2%). The nodes in level E are labelled disjoint intervals, each length 2", of the form ((i 1)-
by the intervals in this partition.
The binary-tree random variable Z E R.T with parameter is defined as follows. For each node (t1, tz] in the binary tree with leaves, let Zittaaal (0, 1/p). For each t E [T], consider the dyadic decomposition of the interval (0, 1] (Definition 2.3) and let Z[I be the sum of the random variables corresponding to the intervals in this dyudic decomposition.
The proof of Theorem 2.2 can be found in Section B.
2.2 Adaptively estimating good flippancy bound w
In this section, we leverage the privacy and accuracy guarantees of Algorithm 1 to construct a new mechanism ( (Algorithm 3) for estimating CountDistinct. It achieves the privacy and accuracy guarantees of Theorem 2.1, when the maximum flippancy is not known upfront. Algorithm instan- tiates log T + 1 different copies Bo .h.... BlogT of Algorithm I with flippancy bounds 2 ..... 2 respectively (the maximum flippancy of a stream at most T). To obtain an accurate estimate the distinct elements count, at each time / E (T). we privately select i E [0, log 7' such that the output of B, satisfies the desired accuracy guarantee for the stream entries æ[1 t] received so far. Selecting such i amounts to selecting good bound the maximum flippancy of the stream 2[1 t). Next, describe how to obtain this bound using the sparse vector technique (Algorithm 2).
The maximum flippancy has high sensitivity; changing one stream entry can change the maximum flippancy drastically. However, the number of items with flippancy greater than any particular threshold is a function of sensitivity one. Furthermore, since Algorithm when run with flippancy bound w already has error about /w/pp. p. its accuracy guarantee remains asymptotically the same even if it simply ignores that many elements with flippancy greater than w. Thus, Algorithm uses the sparse vector technique to maintain an upper bound on the flippancy of x11 t) such that not too

---

many elements in x=1 t] violate that bound. This bound, in combination with the error guarantee of Algorithm 1, suffices to provide the desired low error guarantee. Since the sparse vector algorithm remains differentially private even when its queries are chosen adaptively, the privacy guarantees of Algorithm follow from the privacy of Algorithms and 2.
Algorithm 2 SVT: Answering Threshold Queries with Sparse Vector Technique
Input: Stream æ; queries qı, 92,... of sensitivity 1, cutoff e > O, privacy parameter p Output: Stream of Above or Below answers
1: Let e = 22p and set count = 0
2: Let Z Lap(2/e)
3: for each query Qr do
4: Let Ze Lap(4c/e)
5: if @r (x) + Ze 2 Z and count < c then
6:
Return Above
7:
count = count +
8: else
9:
Return Below
Algorithm Mechanism for CountDistinct
Input: Time horizon T E N, privacy parameter > 0, stream E UI
Output: Vector s of distinct count estimates
1: Initialize vector W'max = o 0
2: for E [0, log T] do
3:
Initialize B, as Algorithm with horizon T, privacy parameter 2(log T+1 flippancy 2 See Algorithm
4: Initialize SVT with privacy parameter p/2 and cutoff log T
5: for all f. E (7] do
6: Obtain entry xtt]
7: If 2 2, set Wmax [t] = Wmax [t -]]
8:
for all E [log do
9:
Send x/{] to mechanism B; and get output 8i,e
10:
while True do
11:
Consider query 9: = luu E U flip(u, x11 : t)) 2 wmax [t]}
Wmax d
12:
Send query q: SVT and if the output is "Below". break Update Wmax = 2 Wmaxx [t]
13:
14:
Return 8J,t for j = log( Wmax (t]
D Note that j [0, log T]
The proof of Theorem 2.1 can found in Section C.
Acknowledgments and Disclosure of Funding
We thank Teresa Steiner and an anonymous reviewer for useful suggestions on the initial ver- sion of this paper. S.S. was supported by NSF award CNS-2046425 and Cooperative Agreement 1820ADR0160001 with the Census Bureau. A.S. and P.J. were supported in part by NSF awards CCF-1763786 and CNS-2120667 as well Faculty Awards from Google and Apple.
References
[1] Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In Proceedings, International Conference Machine Learning (ICML), pages 32-40, 2017.
[2] Aditya Akella, Ashwin R. Bharambe, Michael K. Reiter, and Srinivasan Seshan. Detecting DDoS attacks on ISP networks. In Workshop on Management and Processing of Data Streams, 2003.
[3] Noga Alon, Y. Matias, and Mario Szegedy. The space complexity approximating the frequency moments. In Proceedings, ACM Symposium Theory of Computing (STOC), 1996.
10

---

[4] Daniel N. Baker and Ben Langmead. Dashing: fast and accurate genomic distances with hyperloglog. Genome Biology, 20, 2018.
[5] Ziv Yossef, T. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. Counting distinct elements in data stream. In Proceedings, International Workshop on Randomization and Computation (RANDOM), volume 2483, pages 1-10, 2002.
2002.
[6] Ziv Bar- Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application counting triangles in graphs. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002.
[7] Kevin S. Beyer, Peter J. Haas, Berthold Reinwald, Yannis Sismanis, and Rainer Gemulla. On synopses for distinct-value estimation under multiset operations. In ACM SIGMOD Conference, 2007.
[8] Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee, and Samson Zhou. How to make your approximation algorithm private: A black-box affferentially-priaate transformation for tunable approximation algorithms of functions with low sensitivity. In APPROX/RANDOM, volume 275, pages 1-:9224, 2023.
[9] Jean Bolot, Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, and Nina Taft. Private decayed predicate sums streams. In International Conference on Database Theory (ICDT), page 284-295, 2013.
[10] Joshua Brody and Amit Chakrabarti. A multi-round communication lower bound for gap ham- ming and some consequences. Proceedings, IEEE Conference on Computational Complexity (CCC), pages 358-368, 2009.
[11] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Proceedings, Theory of Cryptography Conference (TCC), volume 9985, pages 635663555666 658, 2016.
[12] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approxi- mate differential privacy. SIAM Journal on Computing, 47(5): 1 1888-1938, 2018.
[13] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1226:244 2011.
[14] Lijie Chen, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. On distributed differential privacy and counting distinct elements. In Proceedings, Innovations in Theoretical Computer Science (ITCS), volume 185, pages 56:1-56:18, 2021.
[15] Seung Geol Choi, Dana Dachman-Sole Mukul Kulkarni, and Arkady Yerukhimovich. Differentialll--priva multi- sketching for large-scale statistics. Proceedings Privacy Enhancing Technologies, 2020: 153 174, 2020.
[16] Edith Cohen. Size-estimation framework with applications to transitive closure and reachability.
J. Comput. Syst. Sci,, 55:441-453, 1997.
[17] Anindya De. Lower bounds in differential privacy. Proceedings, Theory of Cryptography Conference (TCC), volume 7194, pages 321-338, 2012.
[18] Sergey Denisov, H. Brendan McMahan, John Rush, Adam D. Smith, and Abhradeep Guha Thakurta. Improved differential privacy for SGD via optimal private linear operators on adaptive streams. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[19] Damien Desfontaines, Andreas Lochbihler, and David A. Basin. Cardinality estimators do not preserve privacy. Proceedings on Privacy Enhancing Technologies, 2019:26 446, 2018.
[20] Charles Dickens, Justin Thaler, and Daniel Ting. Order-invariant cardinality estimators are differentially private. In Advances Neural Information Processing Systems (NeurIPS), 2022.
[21] Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings, ACM Symposium on Principles of Database Systems (PODS), pages 202-210, 2003.
11

---

[22] Marianne Durand and Philippe Flajolet. Loglog counting of large cardinalities (extended abstract). In Embedded Systems and Applications, 2003.
[23] Cynthia Dwork, Frank McSherry, and Kunal Talwar. The price of privacy and the limits of LP decoding. In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 85-94, 2007.
[24] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 381-390, 2009.
[25] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 715-724, 2010.
[26] Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N. Rothblum. Pure differential privacy for rectangle queries via private partitions. In Advances in Cryptology ASIACRYPT, volume 9453, pages 735-751, 2015.
[27] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. Priv. Confidentiality, 7(3):1751,, 2016.
[28] Alexander Edmonds, Aleksandar Nikolov, and Jonathan R. Ullman. The power of factorization mechanisms in local and central differential privacy. Proceedings, ACM Symposium on Theory of Computing (STOC), pages 425-438, 2020.
[29] Alessandro Epasto, Jieming Mao, Andres Muñoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially private continual releases of streaming frequency moment estimations. In Proceedings, Innovations Theoretical Computer Science (ITCS), volume 251, pages 48:1-4,: 2023.
[30] Cristian Estan, George Varghese, and Michael E. Fisk. Bitmap algorithms for counting active flows on high-speed links. IEEE/ACM Trans. Netw, 14(5):925-9377 2006.
[31] Hendrik Fichtenberger, Monika Henzinger, and Wolfgang Ost. Differentially private algorithms for graphs under continual observation. In European Symposium Algorithms (ESA), volume 204, pages 42:1-42:16 16, 2021.
[32] Philippe Flajolet and G. Nigel Martin. Probabilistic counting algorithms for data base applica- tions. Comput. Syst. Sci., 31(2):122-209 1985.
[33] Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Hyperloglog: the analysis of near-optimal cardinality estimation algorithm. Discrete Mathematics & Theoretical Computer Science, pages 137-156, 2007.
[34] Badih Ghazi, Ben Kreuter, Ravi Kumar, Pasin Manurangsi, Jiayu Peng, Evgeny Skvortsov, Yao Wang, and Craig Wright. Multiparty reach and frequency histogram: Private, secure, and practical. Proc. Priv. Enhancing Technol., 2022(1):373-395, 2022.
[35] Badih Ghazi, Ravi Kumar, Jelani Nelson, and Pasin Manurangsi. Private counting of distinet and k-occurring items in time windows. In Proceedings, Innovations in Theoretical Computer Science (ITCS), volume 251, pages 55:1-55:24, 2023.
[36] Phillip B. Gibbons. Distinct sampling for higuly-accurate answers to distinct values queries and event reports. In Proceedings, Very Large Databases (VIDB) Endowment, 2001.
[37] Phillip B. Gibbons and Srikanta Tirthapura. Estimating simple functions on the union of data streams. In Proceedings, ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 281-291, 2001.
[38] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings, ACM Symposium Theory of Computing (STOC), pages 705-714, 2010.
12

---

[39] Jonathan Hehir, Daniel Ting, and Graham Cormode. Sketch-flip flip-mmrgee: Mergeable sketches for private distinct counting. In Proceedings. International Conference on Machine Learning (ICML), volume 202, pages 12846-12865. 2023.
[40] Monika Henzinger, A. R. Sricharan, and Teresa Anna Steiner. Differentially private data struc- tures under continual observation for histograms and related queries. CoRR, abs/2302. 13341, 2023.
[41] Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay, Almost tight error bounds on differentially private continual counting. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5003-5039. SIAM, 2023.
[42] Stefan Heule, Mare Nunkesser, and Alexander Hall. Hyperloglog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm. In International Conference on Extending Database Technology (EDBT), pages 683 633,692,222 2013.
[43] Piotr Indyk and David P. Woodruff. Tight lower bounds for the distinct elements problem. In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pages 283-288, 2003.
[44] Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. The price of differential privacy under continual observation. In Proceedings, International Conference on Machine Learning (ICML), volume 202, pages 14654-14678, 2023.
[45] Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Conference on Learning Theory (COLT), volume 23, pages 24. 2012.
[46] Daniel M. Kane, Jelani Nelson, and David Woodruff. An optimal algorithm for the distinct elements problem. In Proceedings, ACM Symposium on Principles of Databuse Systems (PODS), pages 41-52, 2010.
[47] Jure Leskovec, Anand Rajaraman, and Jeffrey D. Ullman. Mining of Massive Datasets, 2nd Ed. Cambridge University Press, 2014.
[48] Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. Proceedings, Very Large Databases (VLDB) Endowment, 10(6):637-648, 2017.
[49] Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic. In International Conference on Extending Database Technology (EDBT), volume 261, pages 618-629. ACM, 2008
[50] Darakhshan Mir, S. Muthukrishnan, Alcksandar Nikolov, and Rebecca N. Wright. Pan-private algorithms via statistics on sketches In Proceedings, ACM Symposium on Principles of Database Systems (PODS), page 37-48, 2011.
[51] Rasmus Pagh and Nina Mesing Stausholm. Efficient differentially private Fo linear sketching. In International Conference on Database Theory (ICDT), volume 186, pages 18:1-18:19, 2021.
[52] Victor Perrier, Hassan Jameel Asghar, and Dali Kaafar. Private continual release of real-valued data streams. In Network and Distributed System Security Symposium (NDSS), 2019.
[53] Alfred Rényi. On measures of entropy and information. Berkeley Symp. on Math. Statist. and Prob., pages 547-561, 1961.
[54] Adam D. Smith, Shuang Song, and Abhradeep Thakurta. The Flajolet-Martin sketch itself preserves differential privacy: Private counting with minimal space. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[55] Shuang Song. Susan Little, Sanjay Mchta, Staal A. Vinterbo, and Kamalika Chaudhuri. Differ- entially private continual release of graph statistics. CoRR, abs//809.00555 809.02575, 2018.
[56] Rade Stanojevic, Mohamed Nabeel, and Ting Yu. Distributed cardinality estimation of set operations with differential privacy. IEEE Symposium on Privacy-Aware Computing (PAC), pages 37-48, 2017.
13

---

[57] Abhradeep Guha Thakurta and Adam Smith. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. Advances in Neural Information Processing Systems (NeurIPS), volume 26, 2013.
[58] Lun Wang, Iosif Pinelis, and Dawn Song. Differentially private fractional frequency moments estimation with polylogarithmic space. In International Conference on Learning Representations (ICLR), 2022.
[59] David P. Woodruff. Optimal space lower bounds for all frequency moments. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 167-175. SIAM, 2004.
14


Reviews:
[{"review_id": "TfqIsRscSj", "reviewer": "Reviewer_iH8C", "summary": "This paper studies distinct elements under the turnstile continual observation model. The paper provides both upper bounds and lower bounds for event-level and item-level privacy. The error depends on the maximum flippancy, i.e., the maximum number of times that the occurrence of an element changes from positive to 0. In particular the error has sqrt dependency of the maximum flippancy, and they also show the tightness of the result.", "questions": "What's authors' conjectured lower bound for the case when maximum flippancy is between T^{0.5} and T^{2/3}?", "limitations": "Authors adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Distinct element is a fundamental problem in the literature of differential privacy. This paper gives an (almost) tight result for distinct element problem for the continual release model with both insertions and deletions. Previous work only studies insertion-only model, and previous techniques can only imply an error which has linear dependence on maximum flippancy. This paper open the black box of the binary tree mechanism and shows a sqrt(maximum flippancy) dependence.\n\n- I feel the lower bounds are very interesting. To the best of my knowledge, this is the first work formally studying the necessity of the dependence on maximum flippancy for the distinct element problem under turnstile continual observation model.\n\n- The proposed algorithm also works for item-level DP, i.e., even when considering the neighboring stream which is obtained by removing all occurrence of one item, the algorithm is still DP.", "weaknesses": "- The algorithm does not work in the low memory regime, i.e., the space required is linear in the stream size.\n\n- The lower bound of event level DP is not tight. \n\n- For the upper bound, the algorithmic idea is not very impressive. It is basically a clever combination of several standard techniques and ideas appeared in the previous DP continual observation literature. But maybe it is not really a weakness because the lower bound shows that such clean and simple algorithm is the best one can get.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading of our paper! We respond to specific questions below:\n\n> The algorithm does not work in the low memory regime, i.e., the space required is linear in the stream size.\n\nThat is correct, but even the unconstrained problem was not studied previously; Prior to our work, (basically) nothing was known about cardinality estimation with deletions under continual release—with or without space constraints.  We consider only the privacy constraint, since understanding the information-theoretic limitations is a precondition to understanding the additional effect of space constraints. \n\nFurthermore, our lower bounds apply to all algorithms, including space-constrained algorithms. \n\nSpace complexity is certainly a natural topic for future work. \n\n> The lower bound of event level DP is not tight. [...] \n>\n>What's authors' conjectured lower bound for the case when maximum flippancy is between T^{0.5} and T^{2/3}?\n\nThis gap between the upper and lower bounds for event-level privacy is an interesting open question. We don't have a good guess for where the true answer lies (despite having spent time on it).\n\nThat said, in practice, the range of parameters for which there is a gap is quite small; in interesting settings, it seems unlikely for an element to be inserted and deleted more than $T^{1/2}$ times. \n\n> For the upper bound, the algorithmic idea is not very impressive. [...] But maybe it is not really a weakness because the lower bound shows that such clean and simple algorithm is the best one can get.\n\nWe believe that our algorithm has several genuinely new ideas in addition to using existing techniques. We would like to highlight one of them here--specifically, the idea that allows us to get from error $w$ to $\\sqrt{w}$ for streams of flippancy $w$. As in previous work on insertion-only streams, our algorithm transforms the distinct elements stream into a stream of bits for which we release prefix sums using the Tree Mechanism of \\[DNPR'10\\] and \\[CSS'11\\]. A naive analysis—say, based on group privacy—would suggest that one needs to scale the tree mechanism noise up by $w$ to cover a change of flippancy $w$. However, we show that the internal structure of the tree mechanism allows one to scale the noise only by $\\sqrt{w}$. \n\nHere is one indication that this analysis is nontrivial: There are optimized noise addition schemes for prefix sums (see, e.g., Denisov et al (NeurIPS 2022) and Henzinger, Upadhyay and Upadhyay (SODA 2023)) that improve quantitatively over the tree mechanism, but it is unclear if they are compatible with the same noise reduction (from $w$ to $\\sqrt w$) as the tree-based scheme.\n\nAnother new idea, which was picked up on by reviewer 7TW6, lies in the careful application of sparse vector. Because the maximum flippancy can have high sensitivity, we instead count the number of items with flippancy above a given threshold. \n\nFinally, the simplicity of our algorithm is a good thing! It makes it more amenable to modifications for other constraints, such as space complexity.\n"}, {"review_id": "Z8niDdJBtB", "reviewer": "Reviewer_7TW6", "summary": "This paper studies the problem of counting the number of distinct elements in a turnstile stream with differential privacy under continual release. For an insertion-only stream of length $T$ and $\\epsilon$-DP, it was previously shown that is possible to achieve roughly $\\text{polylog}(T)/\\epsilon$ additive error. The results in this paper show that this is not possible in general in turnstile streams. Instead, a particular quantity of interest seems to be the flippancy number of the stream, which is the largest number of times the contribution of a single item to the distinct element count changes over the course of the stream. \n\nFor maximum flippancy $w$, this paper shows that it is possible to achieve additive error proportional to $O(\\sqrt{w})$ for approximate DP, and moreover, $\\Omega(\\sqrt{w})$ additive error is necessary for approximate DP and $\\Omega(w)$ additive error is necessary for pure DP, and the paper notes it is relatively straightforward to achieve $O(w)$ additive error for pure DP. \n\nThe approximate DP upper bound is achieved through a standard binary tree mechanism along with a sparse vector technique, where the latter is used to guess the maximum flippancy $w$ when it is not input to the stream. The lower bound is achieved through a reduction from multiple instances of private inner product queries for the event-level lower bound and through a reduction from multiple instances of a 1-way marginal query for the item-level lower bound. ", "questions": "P5, L171 and P8, L349: Why does the maximum flippancy have sensitivity 1 for event-neighboring streams? I thought the example in the first paragraph of Section 1.2 shows that the flippancy can change by $\\Omega(T)$.\n\nIn terms of correctness, this still seems fine since the sparse vector technique only cares about the *number* of items with flippancy more than $w$, which seems to have sensitivity 1 for both event-neighboring streams and item-neighboring streams. On the other hand, I'm confused about the differences between the event-level and item-level privacy settings and in particular, what algorithmic components can be simplified for event-level privacy. ", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The separation between insertion-only and turnstile streams is a nice conceptual result. \n+ The usage of the sparse vector technique to privately adapt to the growth of the maximum flippancy $w$ seems creative to me.\n\nIn summary, I think the strengths significantly outweigh the following weaknesses, though I'm a bit confused about the claimed sensitivity for maximum flippancy for event-neighboring streams (see below). Hopefully this can be resolved during the discussion phase. \n\nEDIT: As the author response in the discussion phase has resolved this point, I've increased my score from 6 to 7.", "weaknesses": "- The proposed algorithms fully store the entire dataset, which can often be undesirable in the streaming model.\n- There is a gap between the upper and lower bounds for certain regimes of $w$ and $T$, i.e., $w\\in[\\sqrt{T},T^{2/3}]$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading of our paper! We will do our best to incorporate the suggested clarifications.\n\n> P5, L171 and P8, L349: Why does the maximum flippancy have sensitivity 1 for event-neighboring streams? I thought the example in the first paragraph of Section 1.2 shows that the flippancy can change by $\\Omega(T)$.\n\nThank you for pointing out this mistake in the explanatory text. Indeed, in the example we provide, the maximum flippancy does change by $\\Omega(T)$ for the two event-neighboring streams. The corresponding text is a remnant of a previous notion of flippancy; we will update the relevant portions accordingly. As noted by the reviewer, this does not affect our result since we are keeping track of the number of elements with flippancy above $w$, a function that has sensitivity 1 for both event and item level privacy. \n\n\n> On the other hand, I'm confused about the differences between the event-level and item-level privacy settings and in particular, what algorithmic components can be simplified for event-level privacy.\n\n\nIt is not clear what major simplifications of the algorithm are possible in the event-level setting. However, the lower bounds use different reductions in the two settings. The event-level argument reduces from the problem of releasing many inner products with a fixed binary vector (for which high-accuracy solutions are ruled out by Dinur and Nissim's seminal reconstruction attacks). The item-level argument reduces from one-way marginals. The additional flexibility one has in designing item-level attacks allows increasing the range in which they apply. \n\n\n\n\n>The proposed algorithms fully store the entire dataset, which can often be undesirable in the streaming model.\n\nThat is correct, but even the unconstrained problem was not studied previously; Prior to our work, (basically) nothing was known about cardinality estimation with deletions under continual release—with or without space constraints.  We consider only the privacy constraint, since understanding the information-theoretic limitations is a precondition to understanding the additional effect of space constraints. \n\nFurthermore, our lower bounds apply to all algorithms, including space-constrained algorithms. \n\nSpace complexity is certainly a natural topic for future work.  \n\n> There is a gap between the upper and lower bounds for certain regimes of w and T, i.e., w \\in [T^{1/2},T^{2/3}].\n\nThis gap between the upper and lower bounds for event-level privacy is an interesting open question. We don't have a good guess for where the true answer lies (despite having spent time on it).\n\nThat said, in practice, the range of parameters for which there is a gap is quite small; in interesting settings, it seems unlikely for an element to be inserted and deleted more than $T^{1/2}$ times. "}, {"review_id": "Ykhj3ckH8v", "reviewer": "Reviewer_G17t", "summary": "The paper studies private counting problem in continual release under the strict turnstile model. The authors focus on two neighboring definition: item-level and event-level. To gain an upper bound of error for both settings, the authors combine max flippancy, binary tree mechanism for private prefix summation and group privacy. To enforce max flippancy, the authors use SVT to privately track the flippancy. The authors also use embedding technique to obtain a lower bound which matches the upper bound for item-level privacy and most regimes of event-level privacy.", "questions": "N/A", "limitations": "Yes, the authors adequately discuss the limitations", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Reading the paper is a pleasure. The authors did a good job disentangling the math under the hood into plain language and clear intuition.\n\nThe main contribution of the paper is to provide the first error analysis of private counting under continual observation in the turnstile model. The derivation of the upper bound and lower bound is clear but not trivial.\n\nThe papers also list a few interesting open problems which can be good start point for future research in this area.", "weaknesses": "I do not find any conspicuous weakness of the manuscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our paper!"}, {"review_id": "zm8L73vrSc", "reviewer": "Reviewer_MGRg", "summary": "This paper investigates the problem of the continual release of distinct elements subject to differential privacy in the turnstile model.\n\nIn particular, the algorithm must maintain a multi-set S containing elements from a universe U. The algorithm should support the insertion and deletion of elements. After each update, the algorithm needs to report a number which is approximately the number of distinct items in the current set S. Finally, differential privacy constraints require the list of reported numbers over the whole interaction to be private for either (1) the contribution from one item (item-level privacy) or (2) the contribution from one update (event-level privacy). The basic question is to understand the trade-off between (a) interaction length T; (b) privacy budget (eps, delta); and (c) the additive error of reports.\n\nIt is shown, via upper and lower bounds, that the additive error is characterized by the \"flip number\" of the stream. Namely, it is roughly the minimum w such that the contribution from one item changes by at most w times throughout the interaction.\n\nThe upper bound combines many standard tools from differential privacy, including noise-addition mechanisms, the binary-tree mechanism, and the sparse vector technique. I find the application of these tools to be standard. The lower bound is an adaptation of a previous technique.\n\nThe lower bound and upper bound nearly match for the case of item-level privacy; However this is a gap for event-level DP.", "questions": "NA", "limitations": "The limitations and possible future directions are discussed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Counting distinct elements is a basic task in streaming algorithms. Understanding the possibility of this task under privacy constraints is a natural question. This paper presents nice progress on this question.\n* This paper satisfactorily shows that the hardness of the problem is tightly connected to the \"flip number\" quantity, which, depending on the scenario, could be much smaller than the pessimistic bound of poly(T). In this sense, this paper goes beyond the worst-case analysis usually considered in many DP theory papers.", "weaknesses": "* This paper does a good job of skillfully combining techniques in DP. However, the new technical meat looks limited (or maybe I was missing something)\n* This paper did not consider the space complexity of algorithms, which is usually a major resource to optimize in the streaming context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our paper! We respond to specific questions below:\n\n> 1. This paper does a good job of skillfully combining techniques in DP. However, the new technical meat looks limited (or maybe I was missing something)\n\nWe believe that our algorithm has several genuinely new ideas in addition to using existing techniques. We would like to highlight one of them here--specifically, the idea that allows us to get from error $w$ to $\\sqrt{w}$ for streams of flippancy $w$. As in previous work on insertion-only streams, our algorithm transforms the distinct elements stream into a stream of bits for which we release prefix sums using the Tree Mechanism of \\[DNPR'10\\] and \\[CSS'11\\]. A naive analysis—say, based on group privacy—would suggest that one needs to scale the tree mechanism noise up by $w$ to cover a change of flippancy $w$. However, we show that the internal structure of the tree mechanism allows one to scale the noise only by $\\sqrt{w}$. \n\nHere is one indication that this analysis is nontrivial: There are optimized noise addition schemes for prefix sums (see, e.g., Denisov et al (NeurIPS 2022) and Henzinger, Upadhyay and Upadhyay (SODA 2023)) that improve quantitatively over the tree mechanism, but it is unclear if they are compatible with the same noise reduction (from $w$ to $\\sqrt w$) as the tree-based scheme.\n\nAnother new idea, which was picked up on by reviewer 7TW6, lies in the careful application of sparse vector. Because the maximum flippancy can have high sensitivity, we instead count the number of items with flippancy above a given threshold. \n\nFinally, the simplicity of our algorithm is a good thing! It makes it more amenable to modifications for other constraints, such as space complexity.\n\n> 2. This paper did not consider the space complexity of algorithms, which is usually a major resource to optimize in the streaming context.\n\nThat is correct, but even the unconstrained problem was not studied previously; Prior to our work, (basically) nothing was known about cardinality estimation with deletions under continual release—with or without space constraints.  We consider only the privacy constraint, since understanding the information-theoretic limitations is a precondition to understanding the additional effect of space constraints. \n\nFurthermore, our lower bounds apply to all algorithms, including space-constrained algorithms. \n\nSpace complexity is certainly a natural topic for future work. "}, {"review_id": "EWoy74l6W8", "reviewer": "Reviewer_wtJp", "summary": "The paper considers the problem of differentially private cardinality estimation under continual observation in the turnstile model. With only insertions, existing algorithms showcase the additive error is polylogT. With both insertions and deletions, this paper demonstrates that the worst case additive error is at least T^{.25}. While mapping this problem directly to the summation problem (with binary mechanism) and bounding the maximum flip with w, one can directly achieve wpolylogT additive error. This paper further reduces the factor w to sqrt(w) by using the Gaussian mechanism.", "questions": "Need more motivations. What might be an application for the proposed algorithm?", "limitations": "No", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper studies a very important problem, distinct count with continual observation. The observation of the hardness of the turnstile model and the reason behind the maximum flip are well presented. Adaptively estimating the maximum flip with sparse vector technique is intuitive.\n(After reading other reviewers opinion and rethinking what it is meant for a valuable theoretical result. I decided to increase my rating. While it may not yet to be practical, this paper considered important and hard problem and presented interesting results.)", "weaknesses": "When it comes to streaming, data streams can have fast velocity and huge volumes (e.g. internet traces). As a result, it motivated the design for data summaries such as flajolet-martin sketch using sublinear space to estimate distinct count of the stream. Since the paper didn’t introduce any memory-efficient algorithms for the distinct count in the turnstile model, the contribution of studying differential privacy in this setting is greatly weakened. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our paper. We respond to specific questions below:\n\n> Since the paper didn’t introduce any memory-efficient algorithms for the distinct count in the turnstile model, the contribution of studying differential privacy in this setting is greatly weakened.\n\nThat is correct, but even the unconstrained problem was not studied previously; Prior to our work, (basically) nothing was known about cardinality estimation with deletions under continual release—with or without space constraints.  We consider only the privacy constraint, since understanding the information-theoretic limitations is a precondition to understanding the additional effect of space constraints. \n\nFurthermore, our lower bounds apply to all algorithms, including space-constrained algorithms. \n\nSpace complexity is certainly a natural topic for future work. \n\n> Need more motivations. What might be an application for the proposed algorithm?\n\nOur algorithm (and future modifications) can be applied in any setting where the \"elements\" being counted are individuals who come and go. As we we mention in Lines 33-34, applications include \"monitoring traffic on websites, the number of patients in a country’s hospitals, and the number of customers in a store.\" \n\nSpace constraints are only a concern in some of these applications. (Further, as mentioned in the previous response, understanding the achievable accuracy without space constraints is a key step towards understanding what is possible with limited memory.)"}]

Author rebuttal:

Meta-review: This paper studies a fundamental problem in differential privacy, and provides interesting results (both upper and lower bounds). The main limitation of the this paper is that the techniques are not very novel; nevertheless, after discussion with the reviewers, there is an agreement that the paper would be a good addition to NeurIPS.
Decision: Accept (poster)