Order-Invariant Cardinality Estimators Are Differentially Private
Authors: Charlie Dickens
Justin Thaler
Daniel Ting
Venue: NeurIPS 2022 Accept (2022)
Keywords: streaming algorithms
differential privacy
cardinality estimation
distinct elements

Abstract:   We consider privacy in the context of streaming algorithms for cardinality estimation.
    We show that a large class of algorithms all satisfy $\epsilon$-differential privacy, 
    so long as (a) the algorithm is combined with a simple 
    down-sampling procedure, and (b) the input stream cardinality  
    is $\Omega(k/\epsilon)$. Here, $k$ is a certain parameter of the sketch
    that is always at most the sketch size in bits, but is typically much smaller.
    We also show that, even with no modification, algorithms in our
    class satisfy $(\epsilon, \delta)$-differential privacy,
    where $\delta$ falls exponentially with the stream cardinality. 
    Our analysis applies to essentially all popular cardinality estimation
    algorithms, and substantially generalizes and tightens privacy bounds from earlier works. 
    Our approach is faster and exhibits a better utility-space
    tradeoff than prior art.

Order-Invariant Cardinality Estimators Are Differentially Private
Charlie Dickens
Justin Thaler
Yahoo
Georgetown University
charlie dccens@yahoooincccom
. thaler@georretoon..cii
Daniel Ting
Meta dtingemeta.com com
Abstract
We consider privacy in the context of streaming algorithms for cardinality estima- tion. We show that a large class of algorithms all satisfy c-differential privacy, so long (a) the algorithm is combined with simple down-sampling procedure, and (b) the input stream cardinality is (2(k/e). Here, & is certain parameter the sketch that is always at most the sketch size in bits, but is typically much smaller. We also show that, even with no modification, algorithms in our class satisfy (c, 8) -differenniall privacy, where 5 falls exponentially with the stream cardinality. Our analysis applies to essentially all popular cardinality estimation algorithms, and substantially generalizes and tightens privacy bounds from earlier works. Our approach is faster and exhibits a better utility-space tradeoff than prior art.
Introduction
Cardinality estimation, or the distinct counting problem, is fundamental data analysis task. Typical applications are found in network traffic monitoring [9], query optimization [20], and counting unique search engine queries [14]. A key challenge to perform this estimation in small space while processing each data item quickly. Typical approaches for solving this problem at scale involve data sketches such as the Flajolet- (FM85) sketch [12], HyperLogLog (HLL) [11], Bottom-k [2, 6, 3]. All these provide approximate cardinality estimates but bounded space.
While research has historically focused on the accuracy, speed, and space usage of these sketches, recent work examines their privacy guarantees. These importance as companies have built tools that can grant an appropriate level privacy to different people and scenarios. The tools aid in satisfying users' demand for better data stewardship. while also ensuring compliance with regulatory requirements.
properties have grown in
We show that all cardinality estimators in a class of hash- based, order-invariant sketches with bounded size e-differentially private (DP) so long as the algorithm is combined with a simple down-sampling procedure and the true cardinality satisfies mild lower bound. This lower bound requirement can be guaranteed hold by inserting sufficiently many "phantom elements" into the stream when initializing the sketch. We also show that, even with no modification, algorithms in our class satisfy (e, difffrrertt privacy, where 8 falls exponentially with the stream cardinality.
Our novel analysis has significant benefits. First, prior works on differentially private cardinality estimation have analyzed only specific sketches [23, 25, 5, 22]. Moreover, many of the sketches analyzed (e.g., [23, 22]), while reminiscent of sketches used in practice, in fact differ from practical
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

sketches in important ways. For example, Smith et al. [22] analyze variant of HLL that Section 4 shows has an update time that can be & times slower than an HLL sketch with k buckets.
While our analysis covers an entire class of sketches at once, our error analysis improves upon prior work in many cases when specialized specific sketches. For example, our analysis yields tighter privacy bounds for HIL than the one given in [5], yielding both an c-PP guarantee, rather than an (e, 6D-DP guarantee, as well as tighter bounds on the failure probability 8-see Section for details. Crucially, the class of sketches we analyze captures many (in fact, almost all to our knowledge) of the sketches that are actually used in practice. This means that existing systems can be used in contexts requiring privacy, either without modification if streams are guaranteed to satisfy the mild cardinality lower bound we require, or with a simple pro-cessssinng step described if such cardinality lower bounds may not hold. Thus, existing data infrastructure can be easily modified to provide DP guarantees, and in fact existing sketches can be easily migrated to DP summaries.
1.1 Related work
One perspective is that cardinality estimators cannot simultaneously preserve privacy and offer good utility [7]. However, this impossibility result applies only when an adversary However, this impossibility result applies only when an adversary can create and merge an arbitrary number of sketches, effectively observing an item's value many times. does not address the privacy of one sketch itself.
Other works have studied more realistic models where either the hashes are public, but private noise is added to the sketch [23, 17, 25), or the hashes are secret [5] (i.e., not known to the adversary who trying "break" privacy). This latter setting turns out to permit less noisy cardinality estimates. Past works study specific sketches or a variant of a sketch. For example, Smith et al. [22] show that an HLL-type sketch e-DP while [25] modifies the FM85 sketch using coordinated sampling, which is also based on a private hash. Variants of both models are analyzed by Choi et al. [5], and they show (amongst other contributions) similar result to [22]. establishing that an FM85-type sketch is differentially private. Like these prior works, we focus on the setting when the hash functions are kept secret from the adversary. A related problem of differentially private estimation of cardinalities under set operations is studied by [18), but they assume the inputs to each sketch are already de-duplicated.
There is one standard caveat: following prior works [22, 5] our privacy analysis assumes perfectly random hash function. One can remove this assumption both in theory and practice by using a cryptographic hash function. This will yield a sketch that satisfies either a computational variant of differential privacy called SIM-CDP, or standard anformation-theorett notions of differential privacy under the assumption that the hash function fools space-bounded computations [22, Section 2.3].
Other works also consider the privacy- privecy-reeerrvng properties of common Lp functions over data streams. For p 2, these include fast dimensionality reduction [4, 24] and least squares regression [21]. Meanwhile, for 0 < S 1, frequency- moomett estimation has also been studied [26]. Our focus is solely the cardinality estimation problem when p O.
1.2 Preliminaries
More formally, we consider the following problem.
Problem Definition Let D = [aI,,.., 3 denote a stream of samples with each identifier xy coming from a large universe U, e.g., of size 264, The objective is to estimate the cardinality, or number of distinct identifiers, of D using an algorithm S which is given privacy parameters 6 2 0 and a space bound b, measured in bits.
Definition 1.1 (Differential Privacy [8]. A randomized algorithm S is (c. 8) diffferrenti private ((c, (DDP for short or if 8 = O, pure e-DP) for any pair of data sets DD D' that differ in one record and for all S in the range of S, Pr(S(D") E S) S e Pr(S(D) E S) + with probability over the internal randomness of the algorithm S.
Rather than analyzing any specific sketching algorithm, we analyze a natural class of randomized distinct counting sketches Algorithms in this class operate in the following manner: each time a new stream item i arrives, i is hashed using some uniform random hash function ht and then h((i) is used to update the sketch, i.c., the update procedure depends only on hii), and is otherwise independent of

---

i. Our analysis applies to any such algorithm that depends only on the set of observed hash values. Equivalently, the sketch state invariant both to the order in which stream items arrive, and item duplication. We call this class of algorithms hash-based, order-invariant cardinality estimators. Note that for any bash-based, order-invariant cardinality estimator, the distribution of the sketch depends only on the cardinality of the stream. All distinct counting sketches of which we are aware that are invariant to permutations of the input data are included in this class. This includes FM85, LPCA, Bottom-k, Adaptive Sampling, and HLL as shown in Section 4.
Definition 1.2 (Hash-Based Order-invariant Cardinality Estimators). Any sketching algorithu that depends only on the set of hash values of stream items using a uniform random hash function is hash-based order-invariant cardinality estimator. We denote this class of algorithms by C.
We denote a sketching algorithm with internal randomness by S, (for hash- hash-based algorithms, r specifies the random hash function used). The algorithm takes a data set 'D and generates a data structure S, (D) that is used to estimate the cardinality. We refer to this structure as the state of the sketch, or simply the sketch, and the values it can take by E Ω. Sketches are first initialized and then items are inserted into the sketch with an add operation that may or may not change the sketch state.
The size of the sketch is a crucial constraint, and we denote the space consumption in bits by b. For example, FM85 consists of bitmaps of length f. Thus, its state s E Ω = {0, 1 1]sxe, Typically, f = 32, so that b = 32k. Further examples are given in Section 4. Our goal is to prove such sketches are differentially private.
2 Hash-Based Order-Invariant Estimators are Private
The distribution of any hash-based, order-invariant cardinality estimator depends only on the cardinal- Denote
ity of the input stream, so without loss of generality we assume the input is D = {I....,, n). the set { by D_, for i E D and sketching algorithm with internal randomness by (D).
By definition, for an e-differential privacy guarantee, we must show that the Bayes factor comparing the hypothesis E 'D versus i & DD is appropriately bounded:
(D, = (D, =)
<
< VsERIEED.
(1)
Overview of privacy results. The main result in our analysis bounds the privacy loss of hash-based, order-invariant sketch in terms of just two sketch-specific quantities. Both quantities intuitively capture how sensitive the sketch is to the removal or insertion of single item from the data stream.
The first quantity a bound kmer on the number of items that would change the sketch if removed from the stream. Denote the items whose removal from the data set changes the sketch by
Kr = (i E D S, + ( (D))
(2)
Denote its cardinality by K, |K, and the upper bound by kmax = sup, K,.
The second quantity is a bound on a "sampling" probability. Let (s)) be the probability that a newly inserted item would change sketch in state
<ss) = (r(S + S,,(D-)) s).
(3)
Although a sketch generally does not store explicit samples, conceptually, it can be helpful to think of (s)) the probability that an as-yet-unseen item gets "sampled" by a sketch in state s. We upper bound n" == sup.en 5 Tss) to limit the influence of items added to the stream.
The main sub-result in analysis (Theorem 2.4) roughly states that the sketch is c-DP so long as (a) the sampling probability πT" < - e < is small enough, and (b) the stream cardinality n Aumue = @(kman/e ) is large enough.
We show Property (a) is necessary condition for any cDP algorithm if the algorithm works over data universes of unbounded size. Unfortunately, Property (a) does not directly hold for natural
A sketch is duplication-invaane invariant if and only if its state when run any stream a is identical to its state when run the stream o', in which all elements of the stream appear exactly once.
3

---

sketching algorithms. But we show (Section 2.2) by applying simple dawn-sampling procedure, any hash-based, order-invariant algorithm can be modified satisfy (a).
Furthermore, Section 4 shows common sketches satisfy Property (a) with high probability, thus pro- viding (c, 0)DP guarantees for sufficiently large cardinalities. Compared [5], these guarantees tighter, more precise, and more general as they establish the failure probability decays exponentially with n, provide explicit formulas for 6, and apply to a range of sketches rather than just HLL.
Overview of the analysis. The definition of c-DP requires bounding the Bayes factor in equation 1. The challenge is that the numerator and denominator may not be easy to compute by themselves. However, it is similar the form of conditional probability involving only one insertion. Our main trick re-expresses this Bayes factor as a sum of conditional probabilities involving a single insertion. Since the denominator (S, -+) 8) involves specific item which may change the sketch, we instead consider the smallest item J, whose removal does not change the sketch. This allows us re-express the numerator in terms of conditional probability (r((D(()
A J, = j) s) involving only single insertion plus nuisance term Pr, 8). The symmetry of items gives that the nuisance term is equal denominator (r, = (S = s), thus allowing us to eliminate it.
Pr,(J,- = S(D_)) = s) Pr, (r,(S((=s)
Lemma 2.1. Suppose > sup, Kr. Then Pr, (K, n) = 0, and
Pr, (r, = (S, = jED
p|[J,, =).
(4)
By further conditioning on the total number of items that, when removed, can change the sketch, we obtain conditional probabilities that are simple to calculate. A combinatorial argument simplifies the resulting expression and gives two factors in Lemma 2.2, one involving the sampling probability for new items (s) given a sketch state s and the other being an expectation involving K,. This identifies the two quantities that must be controlled in order for sketch to be e-DP.
Lemma 2.2. Under the same assumptions Lemma 2.1
1
Kr n- K, +1 s)(D- (5)
Pr(J,=j1s, - (s))
JED
To show that all hash-based, order invariant sketching algorithms can be made e-DP, we show that K, can always be bounded by the maximum size of the sketch bits. Thus, if a sketch combined with a downsampling procedure to ensure (s)) is sufficiently small, one satisfies both of the properties that are sufficient for an e-DP guarantee.
Having established (5), we can derive result showing that a bash-b inder-invariant sketch is e-DP so long as the stream cardinality is large enough and sup (ss) is not too close 1.
Corollary 2.3. Let denote the set of all possible states of a hash-basel order-invarian distinct counting sketching algorithm. When run on stream of cardinality >> sup, Kr, the sketch output by the algorithm satisfies c-DP if
To =
(U) and SEi
(6)
K2
é 1>1+E,
S,(D-))=s) for all sketch states s E Ω.
(7)
K,
Furthermore, if the data stream D consists of items from universe U of unbounded size, Condition 6 is necessarily satisfied by any sketching algorithm satisfying c-DP.
The above corollary may be difficult to apply directly since the expectation in Condition (7) is often
difficult to compute and depends on the unknown cardinality n. Our main result provides sufficient criteria to ensure that Condition (7) holds. The criteria expressed in terms of minimum cardinality no and sketch-dependent constant kmar. This constant kinoz is bound on the maximum number of items which change the sketch when removed. That is, for all input streams D and all r, kmaz 2 [A,]]. We derive kmaz for number of popular sketch algorithms in Section 4.

---

Theorem 2.4. Consider any hash-based, order-invariant distinct counting sketch. The sketch output by the algorithm satisfies an c-DP guarantee if
sup (s) m0 - and there are strictly greater than
(8)
no kaaz (1 e e) unique items in the stream.
Later, we explain how to modify existing sketching algorithms in a black-box way to satisfy these conditions. left unmodified, most sketching algorithms used in practice allow for some sketch values E Ω which violate Condition 8, i.e π (s)) > - e e We call such sketch values "privacy-violating" Fortunately, such values turn out to arise with only tiny probability. The next theorem states that, so long this probability is smaller than 8, the sketch satisfies (e, 0D- without modification. The proof of Theorem 2.5 follows immediately from Theorem 2.4.
Theorem 2.5. Let no be as in Theorem 2.4. Given a hush-bused, order-invariant distinct counting sketch with bounded size, let St' be the set of sketch states such that T()) 2 agg- 1fthe input stream DD has cardinality no, then the sketch is (c differentially private where ò (S, E Dt).
2.1 Constructing Sketches Satisfying Approximate Differential Privacy: Algorithm la
Theorem 2.5 states that, when run on stream with n 2 no distinct items, any hash-based order- invariant algorithm (see Algorithm la) automatically satisfies (e, d)-differentia privacy where 6 denotes the probability that the final sketch state s is "privacy-violating,, i.e., ((s) > myy - In Section 4, we provide concrete bounds of 5 for specific algorithms. In all cases considered, 8 falls exponentially with respect the cardinality n. Thus, high privacy is achieved with high probability so long as the stream is large.
We now outline how to derive a bound for specific sketch. We can prove the desired bound on 5 by analyzing sketches in a manner similar to the coupon collector problem. Assuming a perfect, random hash function, the hash values of universe of items defines probability space. We can identify < kmar events or coupons, Ci,..., C.. such that ((s) is guaranteed to be less than To after all events have occurred. Thus, if all coupons are collected, the sketch satisfies the requirement to be eDD.. As the cardinality n grows, the probability that a particular coupons remains missing decreases exponentially. simple union bound shows that the probability 6 that any coupon is missing decreases exponentially with n.
For more intuition to why unmodified sketches satisfy (c, 8)-P guarantee when the cardinality is large, we note that the inclusion probability (s) is closely tied to the cardinality estimate in most sketching algorithms. For example, the cardinality estimators used in HLL and KMV are inversely proportional to the sampling probability π (s)), i.e., (()) x 1/T(s), while for LPCA and Adaptive Sampling, the cardinality estimators are monotonically decreasing with respect to ((s). Thus, for most sketching algorithms. when run on a stream of sufficiently large cardinality, the resulting sketch is anivacy-violating only when the cardinality estimate is also inaccurate. Theorem 2.6 is useful when analyzing the privacy of such algorithms, as it characterizes the probability of a "privacy violation" in terms of the probability the returned estimate, (S,, is lower than some threshold Ñ (TO).
Theorem 2.6. Let S, be a sketching algorithm with estimator (S.). Ifn 2 ni and the estimate returned on sketch 8 is a strictly decreasing function of π (+),, so that (s)) = (T())) for a function N. Then, S, is (c, 8)DP where 8 = (N,,())) < (Fo)).
2.2 Constructing Sketches Satisfying Pure Differential Privacy: Algorithm 1b 1c
Thcorem 2.4 guarantees an eDD sketch if (8), (9) hold. Condition (8) requires that sup T(s) 1 - e i.e., the "sampling probability" of the sketching algorithm is sufficiently small regardless of the sketch's 's state Meanwhile, (9) requires that the input cardinality is sufficiently large.
We show that any fash-based, under-invariant distinct counting sketching algorithm can satisfy these two conditions by adding simple pre pre-processing step which does two things. First, it "downsamples" the input stream by hashing each input, interpreting the hash values as numbers in [o, 1]. and simply ignoring numbers whose hashes are larger than mp- The downsampling hash must be independent to that used by the sketching algorithm itself. This ensures that Condition (8) is satisfied, as each input item has maximum sampling probability no.
5

---

BASE(items, e) S InitSketch()
DPSKETCHLARGISETTimN e)
DPSKETCHANYSSrriiems e) S, no t -DPInitSkecc((e) To + 1
S InitSketch)) + - for items do if hash (x) < To then (.add(x)
for items do S.add(x) return (S)
for items do if hhsh(a)) < Too then S.add(z) return (SS) no (c) O)-DP for
return (S))
(a) 6)-D) for n 2 no-
(b) (c. DD- for Yio
Algorithms 1: Differentially private cardinality estimation algorithms from black box sketches. The function InitSketch() initializes a black-box sketch. The uniform random hash function hash(x) is chosen independently of any hash in the black-box sketch and is interpreted real in [0. 1). The cardinality estimate returned by sketch S is denoted (S). DPInitSketch is given in Algorithm 2a.
If there is an a priori guarantee that the number of distinct items is greater than no = Ammax then (9) is trivially satisfied. Pseudocode for the resulting c-DP algorithm is given in Algorithm 1b. If there is no such guarantee, then the preprocessing step adds no items to the input stream to satisfy (9). To ensure unbiasedness, these nig items must (i) be distinct from any items in the "real" stream, and (ii) be downsampled as per the first modification. An unbiased estimate of the cardinality of the unmodified stream can then be easily recovered from the sketch via post-processing correction. Pscudocode for the modified algorithm, which is guaranteed to satisfy e-DP, is given in Algorithm Ic.
Corollary 2.7. The functions DPSketchll aPsketchlargeset (Algorithm 1b) and DPSket tchAnySet (Algorithm Ic) yield e-D distinct counting sketches provided that 2 no and L, respectively.
2.3 Constructing c-DP Sketches from Existing Sketches: Algorithm 3, Appendix A.1
As regulations change and new ones are added, existing data may need to be appropriately anonymized. However, if the data has already been sketched, the underlying data may no longer be available, and even if is retained, it may be too costly to reprocess it all. Our theory allows these sketches to be directly converted into differentially private sketches when the sketch has a merge procedure. Using the merge procedure achieve e-differential privacy yields more useful estimates than the naive approach of simply adding Laplace noise to cardinality estimates in proportion to the global sensitivity.
The algorithm assumes possible to take a sketch (Di) of a stream D1 and a sketch (D2) of stream D2. and "merge" them to get sketch of the concatenation of the two streams D1 D2. This is the case for most practical bashe order-invariant distinct count sketches. Denote the merge of sketches S, (D)) and (D2)) by S, (D,) U (P2). In this setting, we think of the existing non- private sketch S, (D,) being converted to a sketch that satisfies e-DP by Algorithm 3 (see pseudocode in Appendix A. Since sketch S, is already constructed, items cannot be first downsampled in the build phase the way they are in Algorithms 1b-lc. To achieve c-D,, Algorithm constructs noisily initialized sketch, S. (D2), which satisfies both the downsampling condition (Condition (8)) and the minimum stream cardinality requirement (Condition (9)) and returns the merged sketch (,,) U (D2). Hence, the sketch will satisfy both conditions for e-D,, shown in Corollary A.3
This merge based procedure typically adds no additional error to the estimates for large cardinalitics. In contrast, the naive approach of adding Laplace noise can add significant noise since the sensitivity can be very large. For example, HLL's estimator is of the form (HLL(s) a/m((s where is constant and is the sketch. One item can update a bin to the maximum value, so that the updated sketch s' has sampling probability rs'') < (1=((1 1/k). The sensitivity of cardinality estimate is thus least Ñ (HLL(s)/K k. Given that the cardinality estimate, and hence sensitivity, can be arbitrarily large when n 2 k. the naive approach is unworkable to achieve c-DP.
3 The Utility of Private Sketches
When processing a data set with n unique items, denote the expectation and variance of sketch and its estimator by (N) and Var,, (N) respectively. We show that our algorithms all yield unbiased

---

estimates. Furthermore, we show that for Algorithmss la-lc, if the base sketch satisfies a relative enror guarantee (defined below), the DP sketches add no additional error asymptotically.
Establishing unbiasedness. To analyze the expectation and variance of each algorithm's estimator, (S(D)), note that each estimator uses a 'base estimate" Nbase from the base sketch S and has the form (S()) Nessr V; p is the downsampling probability and V is the number of artificial items added. This allows us to express expectations and variance via the variance of the base estimator.
Theorem 3.1. Consider a base sketching algoritim S E C with an unbiased estimator Noase for the cardinality of items added to the base sketch. Algorithms 1 (a)-(c) and 3 yield unbiased estimators.
Bounding the variance. Theorem 3.1 yields a clean expression for the variance of our private algorithms. Namely, (ar = TE[Var( Naaze [V]] which shown in Corollary B.1. The expression is a consequence of the law total variance and that the estimators are unbiased.
We say that the base sketch satisfies a relative-error guarantee if with high probability, the estimate returned by the sketching algorithm when run on stream of cardinality n (1 = 1/) for some constant с > 0. Let Nhase,n denote the cardinality estimate when the base algorithm is run on a stream of cardinality n, as opposed to Nouse denoting the cardinality estimate produced by the base sketch on the sub-sampled stream used in our private sketches DPSketchLargeSet (Algorithm lb) and DPSketchAnySet (Algorithm Ic). The relative eπrоr guarantee is satisfied when Var, < n² /c; this is an immediate consequence of Chebyshev's 's inequality.
When the number of artificially added items V is constant in Algorithms 1b and Ic, Corollary B.1 provides a precise expression for the variance of the differentially private sketch. In Theorem 3.2 below, use this expression establish that the modification of the base algorithm to e-DP sketch as per Algorithms lb and Ic satisfy the exact same relative eπтоr guarantee asymptotically, In other words, the additional error due to any pre-processing (down- sawplig and possibly adding artificial items) is insignificant for large cardinalities n.
Theorem 3.2. Suppose Nuase,n satisfies a relative error guarantee, Var (N < n² fc. for all and for some constant c. Let u- for Algorithm 1b and u = no for Algorithm Ic. Then Algorithms lb and Ic satisfy
Var (Ñ)= < (n u)² +
(n + v) + t
(n+ + +m)),
(10)
kmaz
so that Var, (ar,,(N//arr, (Nbase,)) + 1 +
In Corollary B.2 we prove an analagous result for Algorithm 3, which merges non-private and noisy sketches to produce a private sketch. Informally, the result is comparable (10), albeit with no- This is because, in Algorithm 3, the number of artificial items added V is a random variable. We ensure that the algorithm satisfies a utility guarantee by bounding V with high probability. This equivalent to showing that the base sketching algorithm satisfies an (c, 6DD guarantee as for any n 2 no and dataset D* with |D' = n², (c, 5n. )-DP ensures 8n- > (I,((((S(D))) > mn) = Pr, > n²) which follows from the definition of V in Algorithm 2b.
4 Examples of Hash-based, Order-Invariant Cardinality Estimators
We now provide (e. 8DP results for select group of samples: FM85, LPCA, Bottom-k, Adaptive Sampling, and HLL. The (e, 0DP results in this section operate in the Algorithm la setting with no modification to the base sketching algorithm. Recall that the quantities of interest are the number of bins used in the sketch k. the size of the sketch in bits b and the number of items whose absence changes the sketch kmaz. From Section 2 and Lemma A. we know that kmar < b but for several common sketches we show stronger bound of kyaa = The relationship between these parameters for various sketching algorithms is summarized in Table 1. Table 2, Appendix C, details our improvements over [22, 5] in both privacy and utility.
We remind the reader that, per (6). mo once we bound the parameter kmax for any given hash-based order-invarian sketching algorithm,
e and (9) no kimzz Furthermore, recall that
7

---

Table I: Properties of each sketch with & "buckets" (see each sketch's 's respective section for details of
what this parameter means for the sketch). Each sketch provides an (c, d).P) guarantee, where the column In ô provides an upper bound on in å established in the relevant subsection of Section 4.
Sketch
b: size (bits)
Standard Error
Kmaz
ln
Reference
FM85
32k
0.649n/v Vk n/vk3
32k
28 o(1)
[16]
LPCA
k
k
To n + O(lg n)
[27]
N(
Bottom-k
64k
n/v Vk
k
-I-=0 n + o(1)
[13]
Adaptive Sampling
k
1.2n/ Vh
21-x0 mo n + o(1)
[10]
HLL
5k
1.04n/vk
k mun (1)
[11]
Corollary 2.7 states that the derived algorithms 1b-1c satisfy e-DP provided that n 2 no and n 2 1, respectively. Accordingly, in the rest of this section, we bound kmaz for each example sketch of interest, which has the consequences for pure e-differential privacy delineated above.
Flajolet-Martin '85 The FM85 sketch, often called Probabilistic Counting with Stochastic Aver- aging (PCSA), consists of k bitmaps B; of length É. Each item is hashed into a bitmap and index (B,, G;) and sets the indexed bit in the bitmap bitmaps and the index G; ~ Geometric(1 /2. If is the length of each bitmap. then the total number of bits used by the sketch is b- = kt and maar ke for all seeds r. A typical value for E is 32 bits, as used in Table 1, Past work [25] proposed an e-DP version of FM85 using a similar subsampling idea combined with random bit flips.
1. The chosen bitmap is uniform amongst the k
Theorem 4.1. Let == [ loga Nol and Ro == 2- E (50/2, mol. n 2 no, then the FM85 sketch is (e, 6DP with 8 S kxe + 41
For any k FM85 has kmax E {32k; 64k). This is worse than all other sketches we study which have kmoz k, so FM85 needs a larger number of minimum items ne to ensure the sketch is (c, DD-DP.
LPCA The Linear Probabilistic Counting Algorithm (LPCA) consists of a length-k: bitmap. Each item is hashed an index and sets its bit to 1. If B is the number of bits, the LPCA cardinality estimate is NiPCA = k log(1 B k) = k log x (D)). Trivially, kmas k.
Since all bits are expected to be 1 after processing roughly is logg i distinct items, the capacity of the sketch is bounded. To estimate larger cardinalities, one first downsamples the distinct items with some sampling probubility p. To ensure the sketch satisfies an e-DP guarantee, one simply ensures p 2 No- In this case, our analysis shows that LPCA differentially private with no modifications if the cardinality sufficiently large. Otherwise, since the estimator (ss) is a function of the sampling probability (s), Theorem 2.6 provides an (c, 8) guarantee in terms of Ñ.
Theorem 4.2. Consider LPCA sketch with k bits and downsampling probability p. If To
k and n I-e- then LPCA is e-DP. Otherwise, let by = [k[1 - To/ m)/p)), Au = bo/k, and μi be the
expected number of items inserted to fill bo bits in the sketch. Then, LPCA is (e, 6DD if n > no with
D40 exp
[_00 (- exp(-ii)
8 = Pr(B < bo)
(11)
= where B is the number of filled bits in the sketch. Furthermore, Ho < ( where (()) 1 log(1 - 7) is the cardinality estimate of the sketch when the sampling probability म.
Bottom-k (also known as MinCount or KMV) sketches store the k smallest hash values. Removing an item changes the sketch if and only if 1) the item's 's hash value is one of these k and 2) it does not collide with another item's hash value. Thus, Kmar k. Typically, the output size of the hash function is large enough to ensure that the collision probability is negligible, so for practical purposes kmaz = k exactly. Since the Bottom-k estimator (s) = (k- 11/((s) is function of the update probability т Ts)), Theorem 2.6 gives an (e, dD- guarantee in terms of the cardinality estimate by coupon collecting; Theorem 4.3 tightens this bound on ò for stronger (e, 6D- guarantee.
This approximation holds for < k. A better approximation of the error is / /k(exp(n/k) n//k
8

---

Theorem 4.3. Consider Bottom-k with k minimum values. Given > O, let To. ny be the correspond-
ing subsampling and minimum cardinality to ensure the modified Bottom-k sketch is (c, -).. When run on streams of cardinality 2 no, then the unmodified sketch is (c, D)- where 8 = P(X S
my k) < exp(-naxs where Binomial(n, no) and an = 2 mo *o4 /3n2 11-58
k/n)²
as n cc.
The closely related Adaptive Sampling sketch has the same privacy behavior as a bottom-k: sketch. Rather than storing exactly k hashes, the algorithm maintains threshold p and stores up to k hash values beneath Once the sketch size exceeds k; the threshold is halved and only hashes less than p/2 are kept. Since at most hashes are stored, and the sketch is modified only if one of these hashes is removed the maximum number of items that can modify the sketch by removal is kmas= = k.
Corollary 4,4. For any size and cardinality n, if bottom-k sketch is (e, ()- then a maximum size k adaptive sampling sketch is (c, 8)DP with the same c and 6.
HyperLogLog (HLL) hashes each item to a bin and value G.). Within each bin, it takes the maximum value each bin is a form of Bottom-1 sketch. If there are l bins, then kmaz = k.
Our results uniformly improve upon existing DP results on the HI.I sketch and its variants. One variation of the HIL. sketch achieves e-DP but is far slower than HI..,, as it requires every item to be independently hashed once for each of the k bins, rather than just one time [22]. In other words, [22] needs (k) update time compared to (1) for our algorithms. Another provides an (c, 8) guarantee for streams of cardinality n 2 n/g for an ni that larger than our no by a factor of roughly (at least) 8, with d falling exponentially with n [5]. In contrast, for streams with cardinality provide a pure e-DP guarantee using Algorithms 1b-lc. HLL also has the following (c,6) guarantee.
Auu we
Theorem 4.5. If 2 no, then HLL satisfies an (c, 6)DP guarantee where 8 S le exxp(=For//
HLL's estimator is only function of (ss) for medium to large cardinalities as it has the form (s) N (=)))) when (=())) > 5k/2. Thus, if no is sufficiently small that (mo(s)) >> 5k/2, then Theorem 2.6 can still be applied, and HLL satisfies (c, 8)-DP with 8 (D) < ((T)).
5 Empirical Evaluation
We provide two experiments highlighting the practical benefits of our approach. Of past works, only [5, 22] are comparable and both differ from our approach in significant ways. We empirically compare only to [22] since [5] is simply an analysis of HIL. Our improvement over [5] for HLL consists of providing significantly tighter privacy bounds in Section and providing a fully e-DP sketch in the secret hash setting. We denote c-DP version of HLL using Algorithm 1b by PHLL (private-Hie HLLL) and that of [22] by QLL. Details of the experimental setup are in Appendix D.
Experiment 1: Update Time (Figure la). We implemented regular, non-private HIL., our PHIL., and QLL and recorded the time to populate every sketch over 210 updates with A E [27 .2.......2 buckets. For HLL, these bucket sizes correspond to relative standard errors ranging from ~ 9% down to Rs 1.6%. Each marker represents the mean update time over all updates and the curves are the evaluated mean update time over 10 trials.
Number of buckets: & 20
QLL
PHLL
2
2
2'0
2
27
Update Time
Space Ratio r
space ratio
10
1.4
10-4
1.2
10-5
27
28
20
210
2
212
2%
4%
6%
8%
10%
Number of buckers: &
Relative Firor
(2) Wall-clock update time seconds vs. &.
(b) Estimated space incresse using QUL [22) rather than PHILL
Figure 1: (1a) QLL's update time is not competitive since it performs O(k) hashes. (1b) QLL is less efficient spacewise than PHLL. The relative size of a QLL sketch to a PHLL sketch, the Space ratio, is larger for more accurate sketches.

---

As expected from theory, the update time of [22] grows Okk). In contrast, our method PHLL has constant update time and is similar in magnitude HLL. Both are roughly 500x faster than [22] when & = 212 Thus, figure la shows that [22] is not a scalable solution and the speedup by achieving O(1) updates substantial.
Experiment 2: Space Comparison (Figure lb). In addition to having a worse update time, we also show that QLL has lower utility in the sense that it requires more space than PHLL achieve the same error. Fixing the input cardinality at n = 2 and the privacy budget at e = In(2), we vary the number of buckets k E {27, 2 ..... .2 and simulate the e-DP methods, PHLL and QLL [22]. The number of buckets controls the error and we found that both methods obtained very similar mean relative error for given number of bins* so we plot the space usage against the expected relative eгror for a given number of buckets. For QLL, since the error guarantees tie the parameter to the number of buckets, we modify ? accordingly as well. We compare the sizes of each sketch as the error varies.
Since the number of bits required for each bin depends the range of values the bin can take, record the simulated total sketch size := k loga max; 8;, by using the space required for the largest bin value over buckets.
Although QLL achieves similar utility, it does so using a sketch that is larger: when & = 2 we expect an error of roughly 9%. QLL is roughly 1.1x larger. This increases about 1.6x larger than our PHLL sketch when k = 212 achieving error of roughly 1.6%. We see that the average increase in space when using QLL compared to PHLL grows exponentially in the desired accuracy of the sketch; when lower relative error is necessary. we obtain a greater space improvement over QLL than higher relative errors. This supports the behavior expected by comparing with space bounds of [22] with (P)HLL.
Conclusion
We have studied the (differential) privacy of a class of cardinality estimation sketches that includes most popular algorithms. Two examples are the HLL and KMV (bottom-k) sketches that have been deployed in large systems [14, 1]. We have shown that the sketches returned by these algorithms are e-differentially private when run on streams of cardinality greater than no R and when combined with simple downsampling procedure. Moreover, even without downsampling, these algorithms satisfy (c, -ddffferrenti privacy where falls exponentially with the stream cardinality once is larger than the threshold no- Our results are more general and yield better privacy guarantees than prior work for small space cardinality estimators that preserve differential privacy. Our empirical validations show that our approach is practical and scalable, being much faster than previous state-of- tate-of--the-an the-art while consuming much less space.
Acknowledgments and Disclosure of Funding
We are grateful to Graham Cormode for valuable comments on an earlier version this manuscript. Justin Thaler was supported by NSF SPX award CCF-1118989 and NSF CAREER award CCF- 1845125.
'This is shown Figure 3, Appendix D.
10

---

References
[1] Apache DataSketches. https://datassketches a
[2] Ziv Bar- Yossef,,,f, TS Jayram, Ravi Kumar, D Sivakumar, and Luca Trevisan. Counting distinct elements in a data stream. In International Workshop on Randomization and Approximation Techniques in Computer Science, pages 1-10. Springer, 2002.
[3] Kevin Beyer, Rainer Gemulla, Peter Haas, Berthold Reinwald, and Yannis Sismanis. Distinct- value synopses for multiset operations. Communications of the ACM, 52(11):877778 2009.
[4] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Jchnson-lindenstrane transform itself preserves differential privacy. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 410-419. IEEE, 2012.
[5] Seung Geol Choi, Dana Dachman-Soled, Mukul Kulkarni, and Arkady Yerukhimovich. Differentially-privatr multi-party sketching for large-scale statistics. Proceedings of Privacy Enhancing Technologies, 2020(3):153-174 2020.
[6] Edith Cohen and Haim Kaplan, Summarizing data using bottom-k sketches. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, pages 225-234, 2007.
[7] Damien Desfontaines, Andreas Lochbihler, and David Basin. Cardinality estimators do not preserve privacy. Proceedings Privacy Enhancing Technologies, 2019(2):26 2019.
[8] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[9] Cristian Estan, George Varghese, and Mike Fisk. Bitmap algorithms for counting active flows on high speed links. In Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, pages 153-166, 2003.
[10] Philippe Flajolet. On adaptive sampling. Computing, 43(4):391-400 1990.
[11] Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. In Discrete Mathematics and Theoretical Computer Science, pages 137-156. Discrete Mathematics and Theoretical Computer Science, 2007.
[12] Philippe Flajolet and G Nigel Martin. Probabilistic counting algorithms for data base applica- tions. Journal of computer and system sciences, 31(2):182-209 1985.
[13) Frédéric Giroire. Order statistics and estimating cardinalities of massive data sets. Discrete Applied Mathematics, 157(2):406-427, 2009.
[14] Stefan Heule, Mare Nunkesser, and Alexander Hall. Hyperioglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm. In Proceedings of the 16th International Conference on Extending Database Technology, pages 683-692, 2013.
[15] Svante Janson. Tail bounds for sums of geometric and exponential variables. Statisties & Probability Letters, 135:1-6, 2018.
[16] Kevin Lang. Back the future: arXiv preprint 7008 2017.
nearly optimal cardinality estimation algorithm.
[17] Darakhshan Mir, Shan Muthukrishnan, Aleksandar Nikolov, and Rebecca N Wright. Pan-private algorithms via statistics on sketches. PODS, 2011.
[18] Rasmus Pagh and Nina Mesing Stausholm. Efficient differentially private Fg linear sketching. In 24th International Conference on Database Theory (ICDT 2021). Schloss Dagstuhl-Leibmiz- Zentrum für Informatik, 2021.

---

[19] Seth Pettic and Dingyu Wang. Information theoretic limits of cardinality estimation: Fisher meets shannon. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 556-569, 2021.
[20] P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path selection relational database management system. In Pruceedings of the 1979 ACM SIGMOD International Conference on Management of Data, SIGMOD '79, page 23-34, New York, NY, USA, 1979. Association for Computing Machinery.
[21] Or Sheffet. Differentially private ordinary least squares. In International Conference on Machine Learning, pages 3105-3114, PMLR, 2017.
[22] Adam Smith, Shuang Song, and Abhradeep Guha Thakurta. The Flajolet-Martin sketch itself preserves differential privacy: Private counting with minimal space. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 19561-19572. Curran Associates, Inc., 2020.
[23] Florian Tschorsch and Björ Scheuermann. An algorithm for crivacy-preserving distributed user statistics. Computer Networks, 57 (7(14))2775-2788 2013.
[24] Jalaj Upadhyay. Randomness efficient sestjjohnson-liddesstaaaa transform with applications in differential privacy and compressed sensing. arXiv preprint
2014.
[25] Saskia Nuñez von Voigt and Florian Tschorsch. RRTxFM: Probabilistic counting for differen- tially private statistics. In Conference on e-Business, e-Services and e-Society, pages 86-98. Springer, 2019.
[26] Lun Wang. Iosif Pinelis, and Dawn Song. Differentially private fractional frequency moments es- timation with polylogarithmic space. In International Conference on Learning Representations, 2022.
[27] Kyu-Young Whang, Brad T Vander-Zanden, and Howard Taylor. A linear-time probabilistic counting algorithm for database applications. ACM Transactions Database Systems (TODS), 15(2):208-22 229, 1990.
12

---

7 Paper Checklist
1. (a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
(c) Did you discuss any potential negative societal impacts of your work? See answer to next question.
(d) Did you describe the limitations of your work? Our work shows that existing algorithms, or mild variants thereof, preserve privacy. Therefore, there should not be any negative societal impacts that consequences of positive privacy results unless users/readers incorrectly apply the results to their systems. Any mathematical limitations from the theory are clearly outlined through the formal technical statements.
2. (a) Did you state the full set of assumptions of all theoretical results?
(b) Did you include complete proofs of all theoretical results? Yes]
3. (a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? A small repository containing the experimental scripts and figure plotting has been provided.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? For Figure la the standard deviations have been plotted in shaded regions but these too small in magnitude to be seen the scale of the plot, indicating that there is very little variation. For Figure 1b we have plotted the entire distribution over all trials.
(d) Did you include the amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. (a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. (a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "m5fTfLowzMW", "reviewer": "Reviewer_da9e", "summary": "A sketching algorithm for the distinct elements problem maps a stream of elements from some universe into a small space data structure (the sketch), such that an approximation to the number of distinct elements in the stream can be recovered from the data structure with high probability. Sketches thus compress the data, and it stands to reason that the task of designing a good sketch is aligned with the goal of preserving privacy with respect to the data in the stream. Recent work has confirmed this intuition, and shown that some specific randomized sketches for the distinct elements problem preserve differential privacy, provided that \n\n* the randomness used by the sketch is hidden from the adversary;\n* the data stream contains sufficiently many elements: this can be achieved by padding.\n\nThe analyses in prior work are sketch-specific, and sometimes require modifying the existing sketch in ways that may affect its practicality. \n\nThe present paper unifies this line of work, and, in a way, shows that the privacy preserving properties of distinct element sketches are a deeper property, common to a large class of sketches. Namely, all sketches based on random hashing that are invariant under permuting and duplicating elements satisfy differential privacy, and the privacy parameter depends on two quantities associated with the sketch. One of these quantities is automatically bounded when the stream contains enough elements, and the other is usually small enough with high probability, and, in any case, can be made small enough by subsampling the stream. This unified analysis gives improved bounds, in some cases, and allows ensuring privacy for the most efficient and practical variants of the sketches.", "questions": "The explanation on lines 177-184 is not very clear. The last sentence of the paragraph is a little puzzling. Looking at the supplementary material mostly clears this up.\n\nThere are some typos in the supplementary material: at least one missing reference, one typo that says “n < n_0” rather than “n > n_0” while referencing (23). Please proofread this part of the paper.\n\nDo you think it’s possible to prove privacy for these sketches if the hash function is public but the stream is preprocessed in some random way?\n\n", "limitations": "I think limitations are addressed adequately.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The unified analysis in the paper seems to get to the core of why distinct element sketches preserve privacy. The authors have found a good abstraction that allows isolating what makes a sketch private. Thus the proofs are simple, but give strong results for a wide class of algorithms. This makes the paper much more satisfying than papers that analyze just one sketch, even though there are some nice ones in that category as well.\n\nOne minor weakness may be that the unity of the results is somewhat undermined by the fact that $\\pi(s)$ is not always bounded, which necessitates either a sketch-specific analysis, or preprocessing the stream by subsampling. The fix is simple, however, and does not affect error much. Also, even boiling down the privacy properties of a sketch to just one or two parameters is already quite interesting. \n\nA weakness of this line of work is that the proof of privacy requires the random hash to be secret, which means that the privacy properties do not hold in a distributed setting. I do not hold this against this paper in particular, however.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "N7u3SfBuT5h", "reviewer": "Reviewer_J5RJ", "summary": "The paper proposes a general technique for proving that hash-based,\norder-invariant sketching algorithms for cardinality (which encompasses most\nknown sketching algorithms for the problem) satisfy DP. The DP parameters depend\non an unconditional upper bound on the probability that a new element causes the state\nof the algorithm to change, as well as a condition that the number of unique\nelements in the stream be higher than some value. When the sketching algorithm\ndo not satisfy the conditions, they propose a lightweight, blackbox algorithm\nthat downsamples the stream and adds in \"fake\" unique elements, and show this\nhas no utility drawback and will satisfy privacy.\n\nThey derive tighter privacy guarantees for specific streaming algorithms and\nvalidate their privacy and utility results.", "questions": "In the introduction, what are the paramters b,k? They should be explained here.\nIs the privacy analysis close to being optimal or can a more fine-grained approach be\nmade, such as not having an unconditional upper bound on the stream update chance\n\\pi_0 but rather a time-dependent one?", "limitations": "    Sketching algorithms by their very nature seem to store a tiny amount of\n    data and heavily use randomness. Thus, they should be close to being\n    ``private'' already. It would be helpful if the authors could private a toy\n    example where blatant non-privacy of the sketching algorithm is\n    exposed. \n\n    This also raises the issue that perhaps the privacy analysis and techniques\n    only work in this particular sketching setting. It would be\n    helpful if the authors could compare and contrast these methods to other\n    privacy work in sketching in related works section.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "  + The results are general: they are able to make sketching algorithms for \n  cardinality satisfy DP\n\n  + The privacy overhead is small in terms of utility cost and computational\n  cost\n\n  + Their algorithm is even able to take non-private sketches which are costly\n  to recompute and combine them\n  with private sketches such that the entire computation will satisfy DP. \n\n  - One possible drawback is that the problem\n    intuitively seems slightly ``easy'', see the limitations section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LdY885-e_gO", "reviewer": "Reviewer_wzWL", "summary": "The paper studies the general problem of cardinality estimators in insertion only streams with differential privacy. The authors present a novel and general analysis framework that establishes the privacy property of a vast set of algorithms. The framework shows that any algorithm that is order invariant, based on a purely random hash,  limited in space, and with some sensitivity property is DP.  They show that many standard algorithms respect this property with a simple analysis. This results in improved approximation/privacy tradeoffs. More precisely they show that existing algorithms (not designed for privacy) are private on large enough streams or can be made private with a simple downsampling of the input. This is very useful in practice as it allows to reuse original implementations. The analysis framework seems easy to use and general. The authors also experiment with the algorithms derived.\nThe results hold a slightly relax setting for DP that involves cryptographic assumptions but this framework seems very reasonable.", "questions": "Would it be possible to clarify in a table what novel (or improved) tradeoffs between accuracy and privacy the method allows for the algorithms presented (vs the best known result)?\n\nDo you think the work can be adapted to the continual release model?\n\nCan you add a short statement that the algorithm gets better bound than simply running the non-private algorithm and then perturbing the output?", "limitations": "No negative impact to society", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ general framework for the analysis of algorithms\n+ results hold for well known algorithm with no or limited modifications to their implementations\n- slightly less strong setting for DP (requires cryptographic assumptions on secrecy of hash functions and indistinguishability from random distribution).\n- works in the single release model not in the continual release model which is more applicable in stream settings.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5KraWAn6JxW", "reviewer": "Reviewer_8qSU", "summary": "The authors prove that nearly all **hash-based**, **order-invariant** cardinality estimators are differentially private once combined with a down-sampling procedure. This class includes several well-celebrated cardinality streaming algorithms such as Flajolet-Martin, HyperLogLog, and Bottom-k.", "questions": "Please address the below questions in the rebuttal.\n1. Give an empirical comparison of accuracy between QLL and PHLL. Discuss the reason for different trade-offs between space, update time and accuracy.\n2. Change the title to avoid overclaim.\n3. Discuss the relevant works mentioned above in Related Work section.\n4. Fix line 135.\n5. (Optional) Discuss whether the down-sampling procedure can be used for privacy amplification.", "limitations": "The authors should exhibit accuracy evaluation results and discuss the limitations if it is worse than QLL.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I really enjoyed reading the paper. The text is well-organized and the authors did a good job explaining the tedious math proof in an intuitive and easy-to-follow way. Overall I think the paper makes solid contribution and passes the bar of acceptance. Concrete strengths and weaknesses are listed below and I am willing to further improve the score if the authors can address most of the weaknesses in their rebuttal.\n\n**Strength**:\n1. The paper considers a class of cardinality estimators and proves DP for them as long as they satisfy several conditions, compared to prior works only considering one specific sketching algorithm.\n2. The paper evaluates the update time and space ratio which exhibits the superiority of the proposed algorithm.\n\n**Weakness**:\n1. I am a little bit worried about the accuracy of the proposed sketching with down-subsampling. In Section 5, only update time and space ratio are evaluated. However, it is unclear how QLL and PHLL compares in terms of accuracy. If QLL is much better in accuracy, then a more thorough discussion of the different trade-offs between QLL and PHLL is needed. \n2. Subsampling is also known to provide privacy amplification for DP guarantees. In the proposed algorithm, down-sampling is used to eliminate the $\\delta$ term. Does it also contribution to privacy amplification?\n3. The related work section ignores some recent progress on DP streaming algorithms. These works consider a broader class of streaming algorithms in which cardinality estimation is a special case of order 0. Specifically [1]-[3] consider another special case of order 2 and [5] considers cases of real orders from 0 (exclusive) to 1.\n\n[1] \"The johnson-lindenstrauss transform itself preserves differential privacy.\" Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. FOCS 2012.\n\n[2] \"Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing.\" Jalaj Upadhyay.  CoRR, abs/1410.2470, 2014.\n\n[3] \"Differentially private ordinary least squares.\" Or Sheffet. ICML 2017.\n\n[4] \"Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space.\" Lun Wang, Iosif Pinelis, and Dawn Song. ICLR 2022.\n\n4. The title needs change. Maybe \"Nearly all hash-based order-invariant cardinality estimators are differentially private\"? The current one seems to be an overclaim.\n5. Line 135: The sentence \"By further conditioning on the total number of items $K_r$ that can be removed without changing the sketch\" seems misleading. $K_r$ is the total number of items that change the sketch once removed if I understand correctly according to Equation (2)?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept