Counting Distinct Elements Under Person-Level Differential Privacy
Authors: Thomas Steinke
Alexander Knop
Venue: NeurIPS 2023 poster (2023)
Keywords: differential privacy
user-level privacy
person-level privacy
sensitivity
TL;DR: We show how to privately compute the number of unique elements, despite this having infinite sensitivity in the user-level DP setting.

Abstract: We study the problem of counting the number of distinct elements in a dataset subject to the constraint of differential privacy. 
We consider the challenging setting of person-level DP (a.k.a. user-level DP) where each person may contribute an unbounded number of items and hence the sensitivity is unbounded.

Our approach is to compute a bounded-sensitivity version of this query, which reduces to solving a max-flow problem. 
The sensitivity bound is optimized to balance the noise we must add to privatize the answer against the error of the approximation of the bounded-sensitivity query to the true number of unique elements.

Counting Distinct Elements Under Person-Level Differential Privacy
Alexander Knop"
Thomas Steinke" Google DeepMind steinke@google. com
Google alerandarknop@goggle.coo
Abstract
We study the problem of counting the number of distinct elements in a dataset subject to the constraint of differential privacy. We consider the challenging set- ting of person-level DP (a.k.. user-level DP) where each person may contribute unbounded number of items and hence the sensitivity is unbounded.
Our approach is compute bounded-sensitivtty version of this query, which reduces to solving a max-flow problem. The sensitivity bound is optimized to balance the noise we must add to privatize the answer against the error of the approximation of the bounded-sensee -enniid-eesittiity query to the true number of unique ele- ments.
Introduction
An elementary data analysis task is to count the number of distinct elements occurring in dataset. The dataset may contain private data and even simple statistics can be combined to leak sensitive information about people [DN03]. Our goal that ensures the privacy of the people who contributed their data. As a motivating example, consider collection of internet browsing histories, in which the goal is compute the total number of websites that have been visited by at least one person.
release (an approximation to) this count in way
Differential privacy (DP) [DMNS06] is a formal privacy standard. The simplest method for ensuring DP is to add noise (from either Laplace or Gaussian distribution) to the true answer, where the scale of the noise corresponds to the sensitivity of the true answer i.e. how much one person's 's data can change the true value.
If each person contributes a single element to the dataset, then the sensitivity of the number of unique elements one. However, person may contribute multiple elements to the dataset and our goal is to ensure privacy for all of these contributions simultaneously. That is, we seek to provide person-level DP (a.ka. user-level DP
This is the problem we study: We have a dataset D = (u,, U2 Un of person records. Each person in] contributes finite dataset u, E Ω², where some (possibly infinite) universe of potential elements (e.g., all finite-length binary strings) and Ω USe Ω2 denotes all subsets of of finite size. Informally, our goal is to compute the number of unique elements
DC(D) = U M4
(1)
kE(n)
AAlphahttical author order. We prefer the term "person" over "user," as the latter only makes sense in some contexts and could be confusing in others.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

in way that preserves differential privacy. A priori, the sensitivity of this quantity is infinite, as single person can contribute an unbounded number of unique elements.
In particular, is not possible to output meaningful upper bound on the number of distinct elements subject differential privacy. This is because single person could increase the number of distinct elements arbitrarily and differential privacy requires us to hide this contribution. It follows that we cannot output differentially private unbiased estimate of the number of distinct elements with finite variance, However, it is possible to output lower bound. Thus our formal goal is to compute a high-con cogficeniee lower bound on the number of distinct elements that as large as possible and which is computed in differentially private manner.
1.1 Our Contributions
Given a dataset = " (u E (I²)" and an integer 2 1, we define
DC(D; == max
U 02 sE|n]
(2)
That is, DC(D; E) is the number of distinct elements if restrict each person's contribution to E elements. We take the maximum over all possible restrictions.
It is immediate that e) < DC(D) for all & 2 1. Thus we obtain lower bound on the true number of unique elements. The advantage of DC(D; E) is that its sensitivity is bounded by (see Lemma A. for precise statement) and, hence, we can estimate it in a differentially private manner. Specifically,
Me.e (D) = DC(D; + Lap (e/E)
(3)
defines an e- e-DP algorithm Me. : (22)) + R. where Lap (b) denotes Laplace noise scaled to have mean 0 and variance 212. This forms the basis of our algorithm. Two challenges remain: Setting the sensitivity parameter E and computing DC(D; E) efficiently.
To obtain high-confidence lower bound the true distinct count, we must compensate for the Laplace noise, which may inflate the reported value. We can obtain such a lower bound from Mr (D) using the cumulative distribution function (CDF) of the Laplace distribution: That is, vb 43 (o, 1/2] IP
Lap (b) 2 b 1-log
8, so
MD. l
P
log 2,3
S DC(D)
(4)
confidence
lower bound
Choosing the sensitivity parameter l. Any choice of é gives us lower bound: DC(D; DC(D). Since vD lime- DC(D; () ever, the larger ( is, the larger the sensitivity of DC(D; E) is. That is, the noise we add scales linearly with L.
DC(D) this lower bound can be arbitrarily tight. How-
Thus there is a bias-variance tradeoff in the choice of é. To make this precise, suppose we want lower bound on DC(D) with confidence 1 - 3 E 1 1), as in Equation (4). To obtain the tightest possible lower bound with confidence 1 1 3, we want to maximize the expectation
1
Me. - log Mi,
1 23
((D; = DC(D; log
E
(5)
23
We can use the exponential mechanism [MT07] to privately select & that approximately maximizes q( D; f). However, directly applying the exponential mechanism is problematic because each score has different sensitivity - the sensitivity of q(:: is Instead, we apply the Generalized Expo- nential Mechanism (GEM) of Raskhodnikova and Smith [RS15) (see Algorithm 3). Note that assume some a priori maximum value of is supplied to the algorithm; this is fmax-
Our main algorithm attains the following guarantees.

---

Theorem 1.1 (Theoretical Guarantees of Our Algorithm). Let > 0 and B E (0. 2) and Emax E N. Define M (12*)* - N be M DDDISTINCTCCOUNT(DD... maxx E, B) from Algorithm 1.
Then M satisfies all of the following properties.
Privacy: M is E-differentially private.
Lower bound: For all E (9*)",
DDCD]] 2 3.
(6)
(LD))M(()
Upper bound: For all D (St)",
108 - 186 log
mmax
P 2 max ((D))
DC(D;
1 2/3 (7)
tE[emax]
8
where Ea arg max (fme)
DC(D; - log 23
Computational efficiency: M(D) has running time O (|D) 8. Lmax), where [
Σ
The upper bound guarantee (7) is somewhat difficult to interpret. However, if the number of items
per person is bounded by l., then we can offer clean guarantee: If D = (wI,".. , Un) E (st* ) satisfies max;e[n] [ual S l. S lmax, then combining the upper and lower bounds of Theorem 1.1 gives
P DC(D) 2 D2 DC(D) 28kx log
mmax
}
2 1 - 33.
(8)
(L
Note that l. not assumed to known to the algorithm, but the accuracy guarantee able to adapt. We only assume la < Lmax. where fax is the maximal sensitivity considered by the algorithm.
In addition to proving the above theoretical guarantees, perform experimental evaluation of our algorithm.
Algorithm Distinct Count Algorithm
1: procedure SENSIIIVEIISTICTCOINNTD (w1, u.) ((7));
b DC(D;))
2: Let U2 Ute ((1) x [min(e, [u/)]) c [n] x [q.
3: Let V = =Uiej u, C Ω.
4:
Define Fg C U V by ((1,)),)) E E - 14.
5:
Let G5 be a bipartite graph with vertices partitioned into U, and V and edges Eg. >- [HK73; Kar73]
6: me -MXMMUNNAATHINNSSIZSS
7: return m, E N
8: end procedure
9: procedure DPDISTINCTCOUNT(D- " (2")"; Lmax EN, EN, EE,E
for l E [Emax] do
11: Define (D) SENSITVEDDSTINeTCOOUNTDDD.. 26 llog 29
12: end for
GEM(D; (geteetemat Suc.eetmmmlll(tteeeeeee....e (0teetemm)) - (D) Lap (2L/s).
Algorithm
14:
15:
return (ê, [[max]] R.
16:
end procedure
Efficient computation. The main computational task for our algorithm is to compute DC(D; E). By definition (2), this is optimization problem. For each person i [r]], we must select subset of that person's 's data u, of size at most so as to maximize the size of the union of the subsets Uke(n) U..

---

We can view the dataset D = (u1, Un) E (22") people and on the other side we have the elements of the data universe 52. There is an edge between i [n] and x E f2 if and only if x: E
" as a bipartite graph. On one side we have the n
We can reduce computing DC(D; E) max-flow problem: Each edge in the bipartite graph has capacity one. We add a source vertex which is connected to each person E [n]] by an edge with capacity l. Finally we add a sink that is connected each æ E Q by edge with capacity 1. The max flow through this graph is precisely DD(D;
Alternatively, we reduce computing EC( to bipartite maximum matching. For é = 1, DC(D; 1) is exactly the maximum cardinality of a matching in the bipartite graph described above. For f 2 2, we simply create l copies of each person vertex E [n] and then DC(D; is the maximum cardinality of a matching in this new bipartite graph.*
Using this reduction, standard algorithms for bipartite maximum matching [HK73; Kar73] allow us compute DC(D; with ([D]1.5. E) operations. We must repeat this computation for each é E [fmaa].
Algorithm 2 Linear- Time Approximate Distinct Count Algorithm
1: procedure DEAPRONDISTINCTCOUNTOOOUU un) (II"); max EN, EN, 3 (0,
2:
S+ 0.
3:
for E [[max]] do
4: for i E [n] with u, \ + do
5:
Choose lexicographically first ui \ S.
b Match (i, to c.
6:
Update S + S (v).
7: end for
8: Define (D) = |S| - 26 log
b This loop computes {qe (De()))eE)(mma))
23
9:
end for GEM(D; (gel (mmmol) (emeax)) ()2,
10:
Algorithm
(e(D) Lap (2(/s).
12: return (ê, E [fmax] x R.
end procedure
Linear-time algorithm. Our algorithm above is polynomial-time. However, for many applica- tions the dataset size [D] is enormous. Thus we also propose linear-time variant of our algorithm. However, we must trade accuracy for efficiency.
There are two key ideas that differentiate our linear-time algorithm (Algorithm 2) from our first algorithm (Algorithm 1) above: First, we compute a maximal bipartite matching instead of maximum bipartite matching. This can be done using linear-time greedy algorithm and gives a 2-approximation to the maximum matching. (Experimentally we find that the approximation better than factor of 2.) Second, rather than repeating the computation from scratch for each [emax], we incrementally update our maximal matching while increasing é. The main chal- lenge here ensuring that the approximation to DC(D; é) has low sensitivity - i.e., must ensure that our approximation algorithm doesn't inflate the sensitivity. Note that DC(D; E) having low sensitivity does not automatically ensure that the approximation to it has low sensitivity.
Theorem 1.2 (Theoretical Guarantees of Our Linear-Time Algorithm). Let E E () and (max E N. Define M (?*)* > N be M(D) =
and
"The data universe Q may be infinite, but can restrict the computation the finite set Usenn ui Thus there most DC(D) S [D] item vertices in the graph.
"We need only create min [a.|] copies of the person i E [n]. Thus the number of person vertices is at most min (nl, [D]]
'To clarify the confusing terminology: A matching is subset of edges such that no two edges have vertex in common. maximum matching is a matching of the largest possible size. A maximal matching is a matching such that no edge could be added to the matching without violating the matching property. A maximum matching also maximal matching, but the reverse is not true.

---

Estimated Vocabulary Size
Data Sct
Vocabulary Size
10th Percentile
Median
90th Percentile
Amazon Fashion
1450
1220.6
1319.1
1394.2
Amazon Industrial and Scientific
36665
35970.5
36198.9
36326.7
Reddit
102835
102379.7
102512.6
102643.9
IMDB
98726
98555.6
98670.4
98726.8
Table I: True and estimated (using DPDistinctCout with = 1, B = 0.05 and fmax = counts per data set.
100)
DRAPPROXDISTNNCCCUUNTT. E E, from Algorithm 2. Then M satisfies all of the fol- lowing properties.
Privacy: M is E-differentially private.
Lower bound: For all E (St")"
P ((
18 s DC(D)) 2 1
(9)
Upper bound: Df (n1 .. un) (52*)" satisfies max(e(n) |us| S S.,
maxx then
2 DCC( 28hx
(mmxx
P
log
2
233
(10)
((.))-M(D)
8
Computational efficiency: M(D) has running time O (ID) + mmxx log mmxx). where
DD >, [/].
The factor the upper bound guarantee (10) the main loss compared Theorem 1.1. (The win O(DD)) runtime.) This is worst-case bound and our experimental result show that for realistic data the performance gap is not so bad.
The proofs of Theorems 1.1 and 1.2 are in Appendix A.
2 Related Work
Counting the number of distinct elements in a collection one of the most fundamental database computations. This is supported as the COUNT (DISTINCT ...) operation in SQL. Hence, unsur- prisingly, the problem computing the number unique elements in a differentially private way has been extensively investigated.
In the case where we assume each person contributes only one element (a.k.a. event-level privacy or leeel privacy), the number of distinct elements has sensitivity 1 and, hence, we can simply use Laplace (or Gaussian) noise addition release. However, may not be possible compute the number of distinct elements exactly due to space, communication, or trust constraints (e.g. in the local model of DP [KLNRS11),
Most efforts have been focused on creating differentially private algorithms for counting distinct elements under space constraints (and assuming each person contributes single element). To save space, we wish to compute a small summary of the dataset (called a sketch) that allows us to estimate the number of distinct elements and which can be updated as more elements are added. Smith, Song, and Thakurta [SST20] proved that variant of the Flajolet-Martin sketch is private and Pagh and Stausholm [PS20] analyzed sketch over the binary finite field. Dickens, Thaler, and Ting [DTT22] proved general privacy result for order- invariant cardinality estimators. Hehir, Ting, and Cormode (HTC23) provided a mergeable private sketch (i.e. two sketches can be combined to obtain a sketch of the union of the two datasets). In contrast, Desfontaines, Lochbihler, and Basin [DLB19] proved an impossibility result for mergeable sketches, which shows that privacy or accuracy must degrade as we merge sketches.
5

---

Amazon Fashion
-104
Amazon Industrial
1,400
1,200
Distinct Count
1,000
800
600
400
200
40
100
20
60
80
Person Contribution Bound
Person Contribution Bound
-109
Reddit
-105
IMDB
0.8
0.8
Distinet Count
0.6
0.4
0.4
0.2
20
40
80
100
5
10
15
20
25
30
Person Contribution Bound
Person Contribution Bound
true value
matching algorithm
greedy algorithm
sampling algorithm
Figure 1: Performance of different algorithms estimating distinct count assuming that each person can contribute at most elements (e.g., these algorithms are estimating DC(D;))). (These algo- rithms have bounded sensitivity, but do not add noise for privacy yet.)
Counting unique elements has been considered in the pan-private streaming setting [DNPRY (the aforementioned algorithms also work in the pan-private setting) and in the continual release streaming setting [GKNM23]. (In the continual release setting the approximate count is continually updated, while in the pan-pin can-private setting the approximate count is only revealed once, but at an unknown point in time.) Kreuter, Wright, Skvortsov, Mirisola, and Wang [KWSMW20) give private algorithms for counting distinct elements the setting of secure multiparty computation. In the local and shuffle models, the only known results are communication complexity bounds [CGKM21].
A closely related problem is that of identifying as many elements as possible (rather than just count- ing them); this is known "partition selection." " "set union." or "key selection" [SDH23; DVGM22; KKMN09; CWG22; RCR22; GGKSSY20; ZDKSTMAS23J. Note that, by design, DP prevents us from identifying elements that only appear once in the dataset, or only a few times. Thus we can only output items that appear frequently.
The most closely related work to ours is that of Dong, Fang, Yi, Tao, and Machanavajihala [DFYTM22] and Fang, Dong, and Yi [FDY22]. These papers present two different algorithms for privately approximating the distinct count (and other statistics). We discuss these below and present an experimental comparison in Table We also remark that both papers prove instance optimality guarantees for their algorithms.

---

Amazon Fashion
-104
Amazon Industrial
3.7
1,460
3.68
Distinet Count
1,450
3.66
1,440
3.64
1,430
3.62
3.6
5
10
15
20
25
30
10
15
20
25
30
-109
Reddit
-104
IMDB
9.88
1.03
Distinet Count
1.03
9.87
9.87
1.03
9.86
1.03
10
20
25
15
25
30
true value
matching algorithm
greedy algorithm
sampling algorithm
shifted inverse algorithm
Figure 2: Performance of different algorithms estimating distinct count in a differentially private way for different values of E; for all of them 8 0.05 and &max 100. The values between 10th and 90th percentile of each algorithms estimation are shaded into corresponding colors. For the shifted inverse algorithm, the first two plots contain the results for 9 0.05 and equal the true number of distinct elements in the dataset. The later two datasets are lacking the results for shifted inverse algorithm due the computational constraints.

---

User
Supplier
Customer
Attribute
PS.AQ
L.EP
0,OD
L.RD
R2T [DFYTM22]
0.0658
0.1759
0.0061
0.150
(Approx)ShiffeelIneess [FDY22]
0.0553
0.0584
0.005
0.0061
DPAApproxDissinntCCom
0.0140
0.0110
0.0008
0.0037
DPDistinctCount
0.0100
0.0096
0.0008
0.0001
Table 2: Average relative absolute error of algorithms described in this paper and in [DFYTM22; FDY22] on the TPC-H dataset. For each algorithm we executed it 100 times, removed 20 top and 20 bottom values and computed average error for the rest of 60 values.
Most similar our algorithm is the Race-to-the-Top (R2T) algorithm [DFYTM22]; R2T is generic framework and the original paper did not specifically consider counting distinct elements, but the approach easily be applied DC(D; While [RS15] to select the sensitivity f, R2T computes multiple lower bounds with different sensitivities l and then outputs the maximum of the noisy values. This approach incurs the
the generalized exponential mechanism
of composition
across the multiple evaluations. To manage this cost, R2T only evaluates & = 2, 4, -, 2 Emax,
Compared to our guarantee (8) with an error O
f log
R2T has a slightly worse theoret-
ical error guarantee of O ( log((max)) log
log Emau -B
[DFYTM22, Theorem 5.1].
The shifted inverse mechanism [FDY22] takes different approach to the problem. Rather than relying on adding Laplace noise (as we do). it applies the exponential mechanism with an ingenious loss function (see [Ste23] for additional discussion). When applied counting distinct elements, the shifted inverse mechanism gives an accuracy guarantee comparable to ours (8). The downside the shifted inverse mechanism that computing the loss function in general, NP-hard. Fang, Dong, and Yi [FDY22] propose polynomial-time variants for several specific tasks, including counting distinct elements. However, the algorithm is still relatively slow.
3 Technical Background on Differential Privacy
For detailed background on differential privacy, see the survey by Vadhan [Vad17] or the book by Dwork and Roth [DR14]. We briefly define pure DP and some basic mechanisms and results.
Algorithm 3 Generalized Exponential Mechanism [RS15]
1: procedure GEM(D Ex"; X + IR for i [m/] A, > 0 for iE [m], >> 00 8
2: Require: q has sensitivity sup ''x""" (4(x) - <(>')l S A, for all E [m].
3: Let / log
4: for i [m] do
5: 8; minje(m) (Q)1))-1A))))0((--11)))))) A,+A,
6: end for
7: Sample i E [m] from the Exponential Mechanism using the normalized scores 8;; i.e.,
exp (1
Vi E [m]
IP
=
Exe(m) exp (5
8: return i [m]. 9: end procedure
Definition 3.1 (Differential Privacy (DP) [DMNS06] ). A randomized algorithm M X* - y satisfies e-DP if. for all inputs D, D' E X differing only by the addition or removal of an element and for all measurable S V. we have P [M) S < é { (D') E S).
We refer to pairs of inputs that differ only by the addition removal one person's 's data as neigh- boring. Note that it is common to also consider replacement of one person's 's data; for simplicity,

---

Size
Words per Person
Data Set
Vocabulary Size
People
Records
Min
Median
Max
Amazon Fashion
404
8533
14.0
139
1450
Amazon Industrial and Scientific
11041
1446031
0
86
2059
36665
Reddit
223388
7117494
0
18.0
1724
102835
IMDB
50000
6688844
110.0
925
98726
Table 3: Data sets details.
do not do this. We remark that there are also variants of DP such approximate DP [DKMMN06] and concentrated DP [DR16; BS16), which quantitatively relax the definition, but these are not relevant in our application. A key property of DP that it composes and is invariant under postpro- cessing.
Lemma 3.2 (Composition & Postprocessing). Let M1 y be E1-DP. Let M2 X Z be such that, for all Y. the restriction (.).)) X + 2 is D2-DP. Define M12 X - 2 by M22(D)= (D, M, Then M (E, + E2)-DP.
A basic DP tool is the Laplace mechanism [DMNS06). Note that we could also use the discrete Laplace mechanism [GRS09; CKS20).
Lemma 3.3 (Laplace Mechanism), Letq: x - R. We say has sensitivity A if (D) 9(D')
A for all neighboring D' X Define M X + R by M(D) = ((D) + Lap(AAE) E.) where Lap (b) denotes laplace noise with mean 0 and variance 25² iee. P >
{ [alla(())
P Lapp))
< -t] exp (5) for all t O. Then M E-DP.
Another fundamental tool for DP is the exponential mechanism [MT07]. It selects the approximately best option from among of options, where each option has quality function q with sensitivity A. The following result generalizes the exponential mechanism by allowing each of the quality functions to have a different sensitivity.
Theorem 3.4 (Generalized Exponential Mechanism [RS15, Theorem 1.4)). For each [m]) let q. X + be a query with sensitivity A; Let E, 3 > 0. The generalized exponential mechanism (:EM(;; {q: [e(m); (am) e, (3) in Algorithm 3) is e-DP and has the following utility guarantee. For all D E X", we have
4
P
(:(D)
max gj (D) AS jE(m)
log
-188 3
Experimental Results
We empirically validate the performance of algorithms using data sets of various sizes from different text domains. We focus on the problem computing vocabulary size with person-level DP. Section 4.1 describes the data sets and Section 4.2 discusses the algorithms we compare.
4.1 Datasets
We used four publicly available datasets to assess the accuracy of our algorithms compared base- lines. Two small datasets were used: Amazon Fashion S-core [NLM19] (reviews of fashion products on Amazon) and Amazon Industrial and Scientific 5-core [NLM19] (reviews of industrial and sci- entific products on Amazon). Two large data sets were also used: Reddit [She20] (a data set of posts collected from r/AskReddit) and IMDb [N20; MDPHNP11] (a set of movie reviews scraped from IMDb). See details of the datasets in Table 3.

---

4.2 Comparisons
Computing the number of distinct elements using a differentially private mechanism involves two steps: selecting a contribution bound (& in our algorithms) and counting the number of distinct elements in way that restricts each person only contribute the given number of elements.
Selection: We examine four algorithms for determining the contribution limit:
1. Choosing the true maximum person contribution (due to computational restrictions this was only computed for Amazon Fashion data set).
2. Choosing the 90th percentile of person contributions.
3. Choosing the person contribution that exactly maximizes the utility function qc(D) =
EC - log( ( where = 1, and B 0.001.
4. Choosing the person contribution that approximately maximizes the utility function using the generalized exponential mechanism with e 1.
Note that only the last option differentially private, but we consider the other comparison points nonetheless.
Counting: We also consider three algorithms for estimating the number of distinct elements for given sensitivity bound &:
1. For each person, we uniformly sample & elements without replacement and count the num- ber of distinct clements in the union the samples.
2. The linear-time greedy algorithm (Algorithm 2) with
and / 0.001.
3. The matching- algorithm (Algorithm 1) with e = 1 and B = 0.001.
All of these can be converted into DP algorithms by adding Laplace noise to the result.
In all our datasets "true maximum person contribution" and "90th percentile of person contributions" output bounds that are much larger than necessary to obtain true distinct count; hence, we only consider DP versions of the estimation algorithm for these selection algorithms.
4.3 Results
Figure shows the dependency of the result on the contribution bound for each of the algorithms for computing the number of distinct elements with fixed person contribution. It is clear that matching and greedy algorithms vastly outperform the sampling approach that currently used practice.
Tables 4 to 7 show the performance of algorithms for selecting optimal person contribution bounds on different data sets. For all bound selection algorithms and all data sets, the sampling approach to estimating the distinct count performs much worse than the greedy and matching based approaches. The greedy approach performs worse than the matching- based approach, but the difference is about 10% for Amazon Fashion and is almost negligible for other data sets since they are much larger. As for the matching-baa based algorithm, it performs as follows on all the data sets:
The algorithm that uses the bound equal to the maximal person contribution overestimates the actual necessary bound. Therefore, estimation. It is easy to see that while the median of the estimation close to the actual distinct count, the amount of noise is somewhat large.
only consider the DP algorithms for counts
2. The algorithm that uses the bound equal to the 99th percentile of person contributions also overestimates the necessary bound and behaves similarly the one we just described (though the spread of the noise is bit smaller).
3. The algorithms that optimize the utility function are considered: one non-private and one private. The non-prie non-private algorithm with non-private estimation gives the answer that is very close to the true number of distinct elements. The private algorithm with non-private estimation gives the answer that is worse, but not too much. Finally, the private algorithm with the private estimation gives answers very similar to the results of the non-private estimation.
10

---

Acknowledgments and Disclosure of Funding
We would like thank Badih Ghazi, Andreas Terzis, and four anonymous reviewers for their con- structive feedback and valuable suggestions. We thank Markus Hasenöhrl for helpful discussions, which helped us identify the problem. In addition, we are grateful to Ke Yi, Wei Dong, and Juanru Fang for bringing their related work [DFYTM22; FDY22] to our attention.
References [BS16]
M. Bun and T. Steinke. "Concentrated differential privacy: Simplifications, ex- tensions, and lower bounds". In: Theory of Cryptography: 14th International Conference, TCC 2016-B, Beijing, China. October 31-November 3, 2016, Pro- ceedings, Part Springer. 2016, pp. 635-658. URL: https: / arxiv. org/
abs/ 1605.605..00 02065 (cit. on 9).
[CGKM21]
L. Chen, B. Ghazi, R. Kumar, and P. Manurangsi. "On Distributed Differential Privacy and Counting Distinct Elements". In: 12th Innovations Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Confer- ence. Ed. by J. R. Lee. Vol. 185. LIPIcs. Schloss Dagstuhl Leibniz-Zentrun für Informatik, 2021, 56:1-56::8. URL: https / doi org / 10 4230
LIPIcs. ITCS. 2021.56 (cit. on p. 6).
[CKS20]
C. L. Canonne, G. Kamath, and T. Steinke. "The discrete gaussian for dif- ferential privacy". In: Advances in Neural Information Processing Systems 33 (2020), pp. 15676- 15676-15688. URL: https: //txxaaxvvv////////////////aaavl org/ abs 2004. 00010 (cit. on p. 9).
brg//bs//
[CWG22]
R. S. Carvalho, K. Wang, and L. S. Gondara. "Incorporating Item Frequency for Differentially Private Set Union". In: Thirty-Sixth AAAI Conference Artificial Intelligence, AAAI 2022, Thirty-Fourdy Conference on Innovative Applications of Artificial Intelligence. IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 March 1, 2022. AAAI Press, 2022, pp. 9504-9511. URL: https: //ojj aaai org / innex...x.. php AAAI article wwtecc/eeveeeeeee / 21183 (cit. p. 6).
[DKKWWWZ233
Z. Ding. Durrell, D. Kifer, P. Protivash, G. Wang, Y. Wang, Y. Xiao, and D. Zhang. "A Floating- Secure Implementation of the Report Noisy Max with Gap Mechanism".
arXiv preprint arXiv:2308.0mm 08057 (2023). URL:
https: //arxiv org/abs/ aasaabbs/00 /2008 08057 (cit. p. 21).
[DFYTM22]
W. Dong, J. Fang, K. Yi, Y. Tao, and A. Machanavaijhala. "R2T: Instance- Optimal Truncation for Differentially Private Query Evaluation with Foreign Keys". In: Proceedings of the 2022 International Conference on Management of Data. SIGMOD '22. Philadelphia, PA, USA: Association for Computing ISBN: 9781450392495. URL: https cse hkust edu hkk/-yik/R2TT pdf (cit. on pp. 6, 8. 11).
Machinery, 2022, 759-772.
[DKMMN06]
C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. "Our data, ourselves: Privacy via distributed noise generation". In: Advances in Crypooloy-EURRCCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June 2006. Proceedings 25. Springer. 2006, pp. 486-503 503 (cit. p. 9).
[DKSWZZ+21]
Z. Ding, D. Kifer, T. Steinke, Y. Wang, Y. Xiao, D. Zhang, et al. "The permute- and-flip mechanism is identical report-noisy-max with exponential noise". 100.002000 (2021). URL: https : //arxiv... org/
In: arXiv preprint
abs/2105. 07260 (cit. on p. 21).
[DLB19]
Desfontaines, A. Lochbihler, and D. Basin. "Cardinality Estimators do not Preserve Privacy". In: Proc. Priv. Enhancing Technol. 2019.2 (2019), pp. 26-46. URL: attpp:///oos org/ 10. 22-.////ppte-22011110 2019-00188 (cit. on p. 5).

---

[DMNS06]
C. Dwork, F. McSherry, K. Nissim, and A. Smith. "Calibrating noise to sen- sitivity in private data analysis". In: Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3. Springer. 2006, pp. 265-284 (cit. on pp. 1,8,
[DN03]
I. Dinur and K. Nissim. "Revealing information while preserving privacy". In: Proceedings of the twenty-second ACM IGMOD-SIGACT-SN posium on Principles of database systems. 2003, pp. 202-210 (cit. on 1).
sym-
[DNPRY10]
C. Dwork, M. Naor, T. Pitassi, G. N. Rothblum, and S. Yekhanin. "Pan- Private Streaming Algorithms". In: Innovations Computer Science ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings. Ed. by A. C. Yao. Tsinghua University Press, 2010, pp. 66-80. URL: http: //onference, iiis. tsinghua edu cn/Ics2010 conntent/papers.e html (cit. on p. 6).
[DR14]
C. Dwork and A. Roth. "The algorithmic foundations differential privacy". In: Foundations and Trends()) in T'heoretical Computer Science 9.3 (2014), Pp. 211-407. URL: https //www. cis upenn. edu/-aarotha Pappers/ privacybook. pdf (cit. on p. 8).
[DR16]
Dwork and G. N. Rothblum. "Concentrated differential privacy". In: arXiv preprint arXiv: 0603660088800 (2016). URL: https /ttpxaaaivv////////a////aaa/aaaa org/ abs 1603. 01887 (cit. on p. 9).
[DTT22]
C. Dickens, J. Thaler, and D. Ting. "Order-Invariane Cardinality Estimators Are Differentially Private". In: NeurIPS. 2022. URL: https://arxi:: org/
abs/2203 11200.15400 15400 (cit. on p. 5).
[DVGM22]
D. Desfontaines, J. Voss, B. Gipson, and C. Mandayam. "Differentially pri- vate partition selection". In: Proc. Priv. Enhancing Technol. 2022.1 (2022), pp. 339-352. URL: https doi. org/ 10, 2478 popets 2022 0017 (cit. on p. 6).
[FDY22]
J. Fang, W. Dong, and K. Yi. "Shifted Inverse: General Mechanism for Monotonic Functions under User Differential Privacy". In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Secu- rity. CCS '22 Los Angeles, CA. USA: Association for Computing Machinery, ISBN: 9781450394505. pdf (cit. on pp. 8, 11).
2022, 1009-1022.
URL: https: / /ce. hkust edu.
htt/yyike/Shfftedlle/ Gopi, P. Gulhane, J. Kulkarni, J. H. Shen, M. Shokouhi, and S. Yekhanin. "Differentially private set union". In: International Conference on Machine Learning. PMLR. 2020, pp. 3627-3636. URL: https : /t////axxiv org/ /bs//
[GGKSSY20]
2002. 09745 (cit. on p. 6).
[GKNM23]
B. Ghazi, R. Kumar, J. Nelson, and P. Manurangsi. "Private Counting of Dis- tinct and k-Occurring Items in Time Windows". In: 14th Innovations in Theo- retical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, Ed. by Y. T. Kalai. Vol. 251. LIPlcs. Schloss Dagstuhl Leibniz-Zenttrne für Informatik, 2023, 55:1-55:24. URL: https: / //doi. org/10..///
ITCS. 2023.52222222... 55 (cit. on 6).
[God]
W. Goddard. A brief undergraduate text for Algorithms. Chapter G4: Approx- imation Algorithms. URL: https : / /woplee computing. clemson. edu/ "goddard tetaar//eexts//a// aat///llg/r/eeeeeeeeeee pdf (cit. on p. 19).
[GRS09]
A. Ghosh, T. Roughgarden, and M. Sundararajan. "Universally utility- maximizing privacy mechanisms". In: Proceedings of the forty-first annual
ACM symposium Theory of computing. 2009, pp. 351-360. URL: https: / //ar //arziv.. wwwg//oggooo..o. brg//bs//a /0811. 2841 (cit. on p. 9).
[HK73]
J. E. Hopcroft and R. M. Karp. "An 5/2 Algorithm for Maximum Match-
ings Bipartite Graphs" In: STAM Comput. 2.4 (1973), pp. 225-231, URL: https:/ //doi. org/oor.//oo 2trg/10.10 10.11377 00002199 (cit. on pp. 3, 4).
[HTC23]
J. Hehir, D. Ting, and G. Cormode. "Sketch-Flip-Merr for Private Distinct Counting". In: arXiv preprint arXiv:2302.02000 (2023).
Mergeable Sketches
URL: https: / //tp///avvvv///////////////aaav/ org/ abs/ abs/2302 02056 (cit. on 5).
12

---

[[lv20]
C. Ilvento. "Implementing the exponential mechanism with base-2 differential privacy". In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. 2020, pp- 717-742. URL: https / arxiv. org/ abs/ 1912. .0222222222 (cit. on p. 21).
[Kar73]
A. Karzanov. "An exact estimate an algorithm for finding a maximum flow, applied to the problem "on representatives"". In: Issues of Cybernetics. Proc. of the Seminar on Combinatorial Mathematics (1973), pp. 66-70 (cit. on pp. 3, 4).
[KKMN09]
Korolova, K. Kenthapadi, N. Mishra, and A. Ntoulas. "Releasing search queries and clicks privately". In: Proceedings of the 18th International Confer- ence on World Wide Web, WWW 2009, Madrid, Spain, April 20-24. 2009. Ed. by J. Quemada, G. León, Y. S. Maarek, and W. Nejdl. ACM, 2009, pp. 171- 180. URL: https::t///// /ttpps://di... org/ 10. /141//126661
1526733 (cit. on p. 6).
[KLNRS11]
"What Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. learn privately?" In: SIAM Journal Computing 40.3 (2011), pp. 793-826 826. URL: https: penttss:/arreen /arxiv/ org/ abs/0803. 0924 (cit. on pn
[KWSMW20]
B. Kreuter, C. W. Wright, E. S. Skvortsov, R. Mirisola, and Y. Wang. "Privacy- preserving secure cardinality and frequency estimation", In: (2020). URL: https://resear:
google/ pttp////pbbpppbb11///09 / (cit. p. 6).
[MDPHNPI1]
A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts. "Learn- ing Word Vectors for Sentiment Analysis", In: Proceedings of the 49th An- nual Meeting of the Association for Computational Linguistics: Human Lan- guage Technologies. Portland, Oregon, USA: Association for Computational
Linguistics, June 2011, pp. 142-150. URL: http www aclweb org anthology/P11- 1015 (cit. on 9).
[MS20]
R. McKenna and D. R. Sheldon. "Permute-and-Fin A new mechanism for differentiallyy private selection". In: Advances in Neural Information Process- ing Systems 33 (2020), pp. 193-203. URT.: htt::ttps:/ pestps://arxxe //tp//rxvvv///////////e/////aav/ org/ 2010.
12603 (cit. on p. 21).
[MT07]
F. McSherry and K. Talwar. "Mechanism design via differential privacy". In: 48th Annual IEEE Symposium Foundations of Computer Science
(FOCS'07) 07). IEEE. 2007, pp. 94-103 (cit. on pp. 2, 9).
[N20]
L. N. IMDB Dataset of 50K Movie Reviews. English. 2020. URL: https / //ww. kaggle. com datasets aaaasttsllasshmmi htt.//aaammmmmmm htt.haiimmmmpatiihhiaamam himdb oft 50k-move movie-vee---- wwooveerrvveeee (cit. 9)
[NLM19]
N. J. Li, and J. McAuley. "Justifyyng Recommendations using Distantly- Labeled Reviews and Fine- GrainGr Aspects". In: Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing. EMNLP- IJCNLP 2019, Hong Kong, China, November 3-7, 2019. Ed. by K. Inui, J. Jiang. V. Ng, and Wan. Association for Computational Linguistics, 2019, pp. 188-197. URL: https / /ooi org/10. 18653/v1/D19 1018 (cit. p. 9).
[PS20]
R. Pagh and N. M. Stausholm. "Efficient Differentially Private F Linear Sketching". In: arXiv preprint arXiv:2001. (2020). URL: https // arxiv. org/abs/2000 11932 (cit. on 5).
[RCR22]
A. Rivera Cardoso and R. Rogers. "Differentially Private Histograms under Continual Observation: Streamiig Selection into the Unknown". In: Proceed- ings The 25th International Conference tics. Ed. by G. Camps-Valll Valls, F. J. R. Ruiz, and I. Valera. Vol. 151. Proceedings of Machine Learning Research. PMLR, 2022, pp. 2397-2419. URL: https:
Artificial Intelligence and Statis-
/ //aaxivv.. //axxiv.or//abae............a..a httg:/ab/2210
16787 (cit. on p. 6).
[RS15]
S. Raskhodnikova and A. D. Smith. "Efficient Lipschitz Extensions for High- Dimensional Graph Statistics and Node Private Degree Distributions". In: CoRR aws///////00/ 504.07912 (2015). arXiv: 1504. 07912. URL: http :/ arxiv.
org/abs//e 150.../50...000 07912 (cit. on pp. 2, 9, 20).
13

---

[SDH23]
M. Swanberg, D. Desfontaines, and S. Haney. "DP-SIPS: A simpler, more scalable mechanism for differentially private partition selection". In: CoRR 0bs/2301.01999 (2023). arXiv: 2301 01998. URL:: https //oo///ooo/// org/10.
48550/arXiv 2301 01998 (cit. on p. 6).
[She20]
J. H. Shen. Ask Reddit. English. 2020. URL: https / github
com / heyyjudes differentially private set union / tree A.T522ffaesscce9022200777222 c888//a18//aae (cit. on p. 9).
[SST20]
A. D. Smith, S. Song, and A. Thakurta. "The Flajolet-Martin Sketch Itself Preserves Differential Privacy: Private Counting with Minimal Space". In: Ad- vances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual. Ed. by H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and p/ppceeeeeiggopsppsooooo..aa neurips.... cc paper Abstract html (cit. on
Lin. 2020. URL: https: /
hash / /1t01777711123359223330353131111 p. 5).
[Ste23]
T. Steinke. Beyond Local Sensitivity via Down Sensitivity. DifferentialPri- org down sensitivity/.
vacy.org. htttps///dfffeeetiiiappiisess Sept. 2023 (cit. on p. 8).
[Vad17]
S. Vadhan. "The complexity of differential privacy". In: Tutorials on the Foun- dations of Cryptography: Dedicated Oded Goldreich (2017), pp. 347- 450. URL: https privccytooossss.....oooo seas harvard edu files
Setierippp20i6....1e pdf (cit. on p. 8).
[ZDKSTMAS23]
B. Zhang, V. Doroshenko, P. Kairouz, T. Steinke, A. T.aakuuta, 7. Ma, H. Apte, and J. Spacek. "Differentallly Private Stream Processing Scale". In: arXiv preprint arXiv:2303. 18086 (2023). URL: https: //rxxixxvvv//////////////////av/ org/ aa///bb///333 18086 (cit. on p. 6).
14

---

Person Contribution Bound
Distinct Count
Selection
Counting
10th PC
Median
90th PC
10th PC
Median
90th PC
Max Contrib
DP Sampling
139
1196.8
1407.5
1649.1
Max Contrib
DP Greedy
139
1174.2
1439.2
1646.5
Max Contrib
DP Matching
139
1222.2
1460.9
1631.0
90th PC Contrib
DP Sampling
48
1225.4
1296.2
1377.9
90th PC Contrib
DP Greedy
48
1367.0
1432.6
1516.3
90th PC Contrib
Matching
1365.3
1444.7
1524.8
Max Utility
Sampling
41
1247.0
1259.0
1270.0
Max Utility
Greedy
1376
Max Utility
Matching
17
1428
Max Utility
Sampling
16.0
28.0
661.6
892.5
1124.5
DP Max Utility
Greedy
8.0
11.0
17.0
1148.0
1241.0
1348.0
DP Max Utility
Matching
7.0
9.0
14.0
1252.0
1317.0
1400.0
DP Max Utility
DP Sampling
9.0
16.0
27.1
702.4
899.1
1145.1
DP Max Utility
DP Greedy
8.0
10.0
19.0
1128.5
1224.4
1370.8
DP Max Utility
DP Matching
6.9
9.0
13.1
1220.6
1319.1
1394.2
Table 4: Amazon Fashion: the comparison for l max 100.
Person Contribution Bound
Distinct Count
Selection
Counting
10th PC
Median
90th PC
10th PC
Median
90th PC
90th PC Contrib
DP Sampling
297
32458.1
32943.8
33452.6
90th PC Contrib
DP Greedy
297
36270.3
36669.5
37019.0
90th PC Contrib
DP Matching
297
36236.2
36651.7
37102.7
Max Utility
Sampling
99
24967.0
25039.0
25121.2
Max Utility
Greedy
36246
Max Utility
Matching
42
36364
DP Max Utility
Sampling
85.9
96.0
99.0
23852.8
24739.0
25049.8
DP Max Utility
Greedy
34.0
49.0
66.1
35393.0
35839.0
36116.9
DP Max Utility
Matching
22.9
30.5
43.2
36026.8
36243.5
36371.2
DP Max Utility
DP Sampling
87.0
95.0
99.0
23997.6
24701.1
25067.7
DP Max Utility
DP Greedy
32.9
47.5
68.0
35336.6
35776.2
36136.6
DP Max Utility
DP Matching
22.0
28.0
38.0
35970.5
36198.9
36326.7
Table Amazon Industrial and Scientific: the comparison is for Lmxx 100.
A Proofs
Lemma A.1 (Sensitivity of DC(D; E)). As in Equation for D E (I*)" and E N, define
DC(D; max
U sE(m]
Let D, D' E * be neighboring. That is, D and D' differ only by the addition or removal of one entry. Then (DC(D:)) DC(D': s for all & N.
Proof. Without loss of generality D (u,,... ... un) (Or)" and D' (ui, ("1,'.. un-1) (Ω* n-1) Le., D' is D with person removed. Let l N.
15

---

Person Contribution Bound
Distinct Count
Selection
Counting
10th PC
Median
90th PC
10th PC
Median
90th PC
90th PC Contrib
DP Sampling
75
92480.7
92654.8
92812.1
90th PC Contrib
DP Greedy
75
102544.8
102665.7
102817.7
90th PC Contrib
DP Matching
75
102651.1
102784.1
102907.8
Max Utility
Sampling
99
95606.9
95692.0
95750.3
Max Utility
Greedy
.2
102543
Max Utility
Matching
32
102685
DP Max Utility
Sampling
89.0
96.0
99.0
94549.9
95394.5
95656.5
DP Max Utility
Greedy
26.0
33.0
50.0
102015.0
102253.0
102527.0
DP Max Utility
Matching
14.0
18.5
30.0
102357.0
102501.5
102671.0
DP Max Utility
DP Sampling
88.8
96.0
99.0
94665.2
95375.5
95693.5
DP Max Utility
DP Greedy
27.0
34.0
53.0
102053.2
102289.6
102531.2
DP Max Utility
DP Matching
14.9
18.5
28.0
102379.7
102512.6
102643.9
Table Reddit: the comparison is for fmax 100.
Person Contribution Bound
Distinct Count
Selection
Counting
10th PC
Median
90th PC
10th PC
Median
90th PC
90th PC Contrib
DP Sampling
238
95264.5
95593.5
95966.1 I
90th PC Contrib
DP Greedy
238
98411.0
98734.0
99120.0
90th PC Contrib
DP Matching
238
98354.2
98729.4
99164.2
Max Utility
Sampling
29
49907.8
50036.5
50195.3
Max Utility
Greedy
29
98459
Max Utility
Matching
19
98712
DP Max Utility
Sampling
29.0
29.0
29.0
49899.6
50070.5
50220.9
DP Max Utility
Greedy
22.0
25.0
29.0
98244.0
98364.0
98459.0
DP Max Utility
Matching
13.0
21.0
98586.0
98674.0
98721.0
DP Max Utility
DP Sampling
29.0
29.0
29.0
49924.2
50053.7
50211.9
DP Max Utility
DP Greedy
20.0
26.0
29.0
98126.7
98369.6
98451.8
DP Max Utility
DP Matching
12.0
16.0
21.0
98555.6
98670.4
98726.8
Table 7: IMDB: the comparison is for Lmax 30.
Let U1 C "1,-. S un and of C un, ". 2 S un satisfy
1A
[n|]
laal <
and U 02 (E(m]
DC(D:E)
and
Vi
In -
<
and
o DC(D';))
ie(n-)
1]
16

---

We can convert the "witness" vy.... 2y for D' into a "witness" for D simply by adding the empty set. Define in 0, which satisfies vn S un and o S Then
DC(D:0) - max
U iE|n
Vi E [n] u A
2
())
Similarly, we can convert the "witness" U1 1o Un for into a "witness" for D' simply by discard- ing Un:
DC(D'; = max
Vi Im -1-1 1 u. AEAAE
iE(n-1)
U1
iE m- 1]
U 05
|u2
2 () - l.
Thus (DC(D:)) -CC(D))) S l, required.
Proof of Theorem 1.1. Privacy: First note that (D) DC(D; log(1/233) has sensitivity Algorithm accesses the dataset via (e( in two ways: First it runs the generalized exponential mechanism to select é and second it computes & + (D) + Tap (2L/$) Since the generalized exponential mechanism E/2-DP and adding Laplace noise is also e/2-DP, the overall algorithm is e-DP by composition.
Lower bound: Since & (D( Lap (22/s). we have
P p (D)) + 2ê
28
1
log
=
P
9; (D(
log
3.
(11)
23
28
Since DC DC(D) and (D)) DC(D; 2 log(1/2.3) Equation (11) gives
I DC(D) 2 B DC(D: 3.
This is the guarantee of Equation (6); P is lower bound on DC(D) with probability 1 B. Upper bound: The accuracy guarantee of the generalized exponential mechanism (Theorem 3.4) is
P i
(g(
2 max ge (D) (E(Fmax)
log( log(emax/ 13) 2 - B.
(12)
e/2
Combining Equations (11) and (12) with union bound yields
28 + 2
88 log
(max
P ((D))
è max tE(fmax]
DC(D;
log 23
2/3. (13)
E
E
3
To interpret Equation (13) we need high-probability upper bound on E. Let A > later and define
determined
E+ = arg max DC(D; Al
(14)
&5 [max)]
17

---

so that (C) & DC(D; (e x2 for all l E [fmax]
Assume the event in Equation (12) happens. We have
28
A
2
1
DC(D;
log
S (DC(D;E))
e2) log
2
2,3 (by Equation (14))
2
1
4
DC(D;
log
(p(
2 max EE maax
ge (e - l.
log (as(Cmux/// (3)
(by assumption)
23
E/2
28
1
88
max
max EE (E(faun (faas
DC(D;
log
log
8
2/3
E
B
28 log
1
88
Lyaxx 13
2 DC(D;E))
log
E
2/
8
Combining inequalities yields
28
88
Luux 3
A
28
DC(D; (4)
log
log
S
DC((D)E) +(e -0-)
log
E
2,3
e
6
2/3
(15)
which simplifies to
1
1
mmax
i.
log
S Ea :
2 log
8log
A)
(16)
23
2/3
3
Now we set A = log
to obtain
23
mmax B
é log
S E7
log
+ 8 8log
(17)
23
23
Substituting Equation (17) into Equation (13) gives
2 + 26
1
88 + 164%
mmax
P ((.))-(())
1 V max EE KE(Emax]
DC(D;
log
log
2 1 1-233 2,3
E
2/3
E
B
(18)
We simplify Equation (18) using log
S
log
fmaz g
obtain Equation (7).
20
Computational efficiency: Finally, the runtime of DPDISTINCTCOUNT(D is dominated by m calls to the DENSIIIDDISTINCCCOUNNDD subroutine, which computes the maximum size of a bipartite matching graph with |E| ΣiE(n] [u] minff, |u,]} [D| Emax edges and [V| +
|U| DC(D) Eiejo min{e, [u]]} s 2|D| vertices. The
algorithm
runs in time O(EE) VV [T] O(D lmax) time.
Proof of Theorem 1.2. Privacy: For convenience we analyze Algorithm 4, which produces the same result Algorithm 2. (The difference is that Algorithm 4 is written be efficient, while Algorithm/ 2 is written in redundant manner to make the subroutine we are analyzing clear.) The privacy of the algorithm follows by composing the privacy guarantees of the gener- alized exponential mechanism and Laplace noise addition. The only missing part is to prove that BENSTIVEAPRRODDDSSTTTCOOOOOT,TT has sensitivity l.
Note that
= SENSTIVEAPPOOODSSTTTTCCCOOOO Un. U1, ... 1, 1):
times
therefore, it is enough to prove that SENSSTVEAAPRODDSSTRCCCOOOTT 1) has sensitivity 1.
Assume D = (ui..... un) and D' (uI.... uj- ",41, "., and U1, ... Un be the states of S and (v. =1 if 4 S 0), respectively, when
"",,,"".,," ..,,.,) Let S
18

---

Algorithm Approximate Distinct Count Algorithm
1: procedure SEASTTTVEAPRRODDSSTTTTTCOOOTTTDT o,t. ",))(()))))
2: S
3: for E' E [c] do
4: for i E [n]] with u, \ do Choose lexicographically first uz \S.
5:
Match (i, to
6:
Update + S (v).
7: end for
8: end for
9: return |S|
10: end procedure
11: procedure DPAPPRONDISTINCTCONNTT , (2*)"; lmx E 8, B
)))
12:
for EE [max] do
13:
Define (D( SENSIIVAAAPRODDDSTTTTTCCOUOOOO -log end for
14:
15:
i + GEM(D; (E(
Algorithm:
+ q3(D) Lap (2(/E)
17: return (ê, () [emaxx] x R.
end procedure
APPROXEENSIIVEDSTIICCCOUUUTT 1). Similarly, let S1, S o1 .. 1/-1. -.. v%
S
be the states of S and (o) =1 if u, S 0), respectively, when ,)). Our goal is show that ||S | 1. Define Sj S and v/ -. Clearly S S; and of = for all i < j. For i 2 j. we claim that S S St and |S|| |S|| + This is true for i j. since 5 S Sj-1 and Sj = ( We prove the claim for i by induction. L.e. assume S; = [ for some 2 (possi- bly - 1. whence S, 1) Now ey is the lexicographically first element of u, S and of is the lexicographically first element of u, 5 (or 1 if these sets are empty). By the induction assumption, u, - S u; S S (u: S(1) U (w[_1)- Thus either vy = 8/ or o/ = o If o 0% then S
we rum APPROSSENIITVVDDDSIIICCCCCUUTTT
St and f S U (w:] = S. If of ui-1 then S S (ot_)) C S 1 ( = S
S U 1 S, S and o (v:] Si, so the claim holds with ii Ui.
c S [v,)
The sensitivity bound implies that (e(D) |S| 2 (1/3) has sensitivity l. Since the gen- cralized exponential mechanism is s/2-DP and adding Laplace noise is also e/2-DP, the overall algorithm is eDD by composition.
the value of [S] we obtain on Line in Algorithm Note that DC(D; E) is the size of maximal matching in Gr. where Ge is the bipartite graph corresponding to the input D with & copies of each person (see Algorithm for formal description of the graph). Since maximal matching is 2-approximation to maximum matching [God], we have
Lower bound: Let denote by DC(D; = SENSTIVAAPPODDSTIITCCOOUNT
DC S DC(D: (DC(D:)) DC(D;)) S DC(D).
(19)
Since + (D) + Lap (2t/E). we have
2i
28
1
p i D
log
= P 1 (D)
log
1
3.
(20)
2,3
23
For notational convenience, define {1} 0.
19

---

Substituting (e(D) - (C( 24 log(1/28) into Equations (19) and (20) gives Equation (9)
P & DC(D)) 2 P DC(D: 3.
Upper bound: The accuracy guarantee of the generalized exponential mechanism (Theorem 3.4) is
4
P (3(D)2
max (e(D)
6. s/2
log( log((fax/
2 1 -. B.
(21)
LE (fmax)
Combining Equations (20) and (21) and the definition of qe (D) with union bound yields
26 + 2
88
mmax
P ((D))
2 max (E
DC(D;E)
log
log
- 23. (22)
2,3
B
Now we assume maXie[n] |usl S l, S max for some Lu This implies DC(D) DC(D; We have
26 + 2
8e
m
max (E(ema)]
DC(D;E)
log
log
(23)
23
B
2 DC(D;L.) 2h. 2
8l.
Exax
log
log
(24)
2,3
DC(D)
2l, 20
8la
Emax
log
log
(25)
&
2/
E
As in the proof of Theorem 1.1, if the event in Equation (21) happens, can show that
(mux
))
é log
log
+ 8 8log
(26)
2/
23
3
where
E = arg max DC(D:E) [E(Faux)
log
(27)
28
Note that l S lup since DC(D; S DC(D; for all é [fmax]- (That simply to say that the size of the maximal matching cannot be increased by making more copies of vertex once there is one copy for each neighbor.) Combining bounds yields
è 8 DDC(D
48. E
24E.
mmax
log
log
2 2,8.
(28)
(L.D))-M(D)
233
B
Since log
log Lmnax this implies Equation (10).
23
Computational efficiency: only remains to verify that Algorithm 2 can be implemented in that O(ID + Enax log (max) time. We implement S using hash table to
add
an element or query membership of an element constant time. (We can easily maintain a counter for the size of S.) We assume D is presented and furthermore that the linked lists u, are sorted in lexicographic order. The outer loop proceeds (wi, ..-, un). For each ui simply pop elements from the linked
linked list of linked lists representing each u,
through the linked list for list and check if they are in S until either we find e E us \ (and add v to S) or u, becomes empty (in which case remove it from the linked list for D.) Since each iteration decrements [D], the runtime of the main loop is O(IDI). Running the generalized exponential mechanism (Algorithm 3) takes (E log m time.
B Implementing the Generalized Exponential Mechanism
We conclude with some remarks about implementing the generalized exponential mechanism of Raskhodnikova and Smith (RS15) given in Algorithm There are two parts to this; first we must compute the normalized scores and then we must run the standard exponential mechanism.
20

---

Implementing the standard exponential mechanism is well-studied [1lv20] and can be performed in linear time (with some caveats about randomness and precision). We remark that, instead of the exponential mechanism, we can use report-noisy-max or permute-and-fijy [MS20; DKSWX7++11; DDKPWWX/23JJ These variants may be easier to implement and may provide better utility too.
The normalized scores are given by
(q.(D) tA,) - tر,)
Vi E [m]] 8/ = min JE[m]
(29)
A. A,
where (D(D) is the value of the query on the dataset, A, > 0 is the sensitivity of qo and / is a constant. Naively it would take ((m²) time to compute all the normalized scores. However, more complex algorithm can compute the scores in O(m m) time.
Observe that, for each i [m]] we have
(g:(D) - + - (D) tz2)
(q:(D) - -A,) (g) - - + +4y) 0
$1 min /E [m]
min
A + Aj
/ [m]
A. A,+ A,
min (g:(D) - -1;) - (g)( - 111) -A(A, + +A,) =0
jE[m]
(DD)) - ( = max 9j 9,( + +(s tt)s
jE(m]
f(sc-t)
That is, we can compute s; by solving the equation ( (s: t)4, f(s:-
Since f(x)= == ma (D) + rA, is the maximum increasing linear functions, we have that is a convex, increasing, piecewise-linees linear function, with most m pieces. We represent by a sorted list of the points where the linear pieces connect, along with the linear function on each of the pieces. We can compute this representation of as pre-processing step in O(m log m) time; we sort the lines (()) = g;(D) + =A, by their slope A; and then compute the intersection points between consecutive lines (we delete lines that never realize the max).
Given the above representation time. We must solve (D) (s; + f)A, f(: t) for sq. We can perform binary search on the pieces f to identify j such that f(;: 1) (D) + (s; - t)Aj. Once we have this we can (1) A,+A,
f and the values q, (D), A., t, we can compute s; in Olog m)
The binary search takes O(log m) time and must compute m scores. Thus the overall runtime (including the pre- rrepprocessing) is Om log m).
directly compute 8;
21


Reviews:
[{"review_id": "AQhkMfFLJc", "reviewer": "Reviewer_fhMe", "summary": "\nThis paper proposes an algorithm to count the maximum number of unique items one can get from considering from every individual in a dataset at most l items, while preserving differential privacy.  \n", "questions": "--", "limitations": "\nThe paper doesn't have a conclusions section, and doesn't mention limitations nor societal impact.\n\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\n\nThe paper offers an (as far as I know) original contribution, which is simple and nice.  The explanation is clear.  The result may be significant to the extent one can cast applications needing to count the number of unique items into the relaxation considered in the current paper.\nThe paper performs an interesting empirical evaluation, even if it doesn't fully succeed to bring up a convincing application.\n", "weaknesses": "\nThe paper also proposes a linear time algorithm, which is very nice, but which makes a second approximation, making it even more unclear how to determine whether it is suitable for a specific application.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for reviewing the paper, we respond below.\n\n**Applications:** We believe that applications of our algorithms are abundant. COUNT(DISTINCT …) is a very common SQL aggregation that is missing in all existing differentially private SQL solutions. [A concrete example](https://socialscience.one/blog/unprecedented-facebook-urls-dataset-now-available-research-through-social-science-one) query would be counting the number URLs that a set of users have shared on a platform.\n\n**Suitability of our algorithms:** The motivation for our linear time algorithm is that our main algorithm may not scale to massive datasets. While the linear-time algorithm doesn’t provide strong provable accuracy guarantees, the experiments show that it performs comparable to the optimal algorithm and outperforms the baseline by a large margin.\n"}, {"review_id": "RXiLsVIOHi", "reviewer": "Reviewer_REV6", "summary": "Edit: Overall decision recommendation changed from borderline reject to borderline accept under the expectation that limitations and future work directions as discussed in the reviewer discussion are incorporated into the manuscript.\n\nThe manuscript studies the problem of approximating the number of unique items in a multiset under (user-level) differential privacy (DP). Unlike in prior work users can contribute arbitrarily many items to the multiset.\n\nThe authors propose to select for each user a subset of contributed items that maximises the total number of unique items. The maximisation problem is solved exactly in polynomial-time via bipartite maximum matching or alternatively a 2-approximation is found in linear-time via a greedy algorithm.", "questions": "Q1a) Presuming number of distinct items per user cannot be arbitrarily large, is it possible to derive an unbiased estimator using the proposed method or is there some strong indication that any unbiased estimator would be inherently impossible (presuming upper limit on items per user) or could not provide good enough accuracy in this setting?\n\nQ1b) Is there some indication that the released noisy counts correlate with the correct counts sufficiently to rank multiple noisy counts somewhat accurately?\n\nQ2a) What is correct count for each table and what is the achieved count with the proposed method? \n\nQ2b) Is there any strong indication that the proposed solution could not be easily improved upon?\n\nQ3) Do the authors plan to release the code that was used for the experiments?", "limitations": "Some limitations do not seem to be mentioned (see Weaknesses W1) and there is generally no discussion of limitations in the abstract or an explicit paragraph in the main paper or appendix.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1) Non-trivial results: Sensitivity analysis of approximate DC(D;l) and application of generalized exponential mechanism is interesting.\n\nS2) Could be useful: Probability that noisy count is a lower bound can be calibrated and lower bound can be useful to check if certain thresholds are exceeded.\n\nS3) Improvement over naive baselines: Computing/approximating DC(D;l) seems clearly preferable to selecting l random items for each user.", "weaknesses": "W1) Heavily biased estimator.\n\nA DP count would seem to prohibit deterministic lower/upper bounds. While a lower bound w.h.p. could still be useful, most settings would seem to call for an unbiased estimator (see also Q1a & Q1b).\n\nW2) Quality of solution unclear.\n\nApart from the poorly presented tables that do not clearly indicate the correct count, there is also no analysis of how much more utility could potentially be possible for this problem under a given DP regime. Thus, it is difficult to appreciate the solution in terms of how practically useful it is or how much utility is potentially lost due to the method (see also Q2a & Q2b).\n\nW3) Reproducibility\n\nWhile the datasets seem to be specified, the submission does not seem to provide code for experiments (see also Q3).\n\nW4) Minor: Some parts of the paper are hard to understand. Particularly, Section 3 could focus more on explanations related to the Generalized Exponential Mechanism (GEM) rather than well-known basics.\n\nIt would be better to move the basics of DP and basic Exponential/Laplace mechanism to the appendix and instead provide more explanations/intuitions on how the GEM is used in this work, why it is needed and some intuitions how it leads to better results.\n\nW5) Minor: Sensitivity analysis of DC(D;l) is missing.\n\nIt could be stated more explicitly why if a user is added that contributes X items DC(D;l) can increase by at most X, i.e., the added user cannot improve the solution for the previous users (e.g., due to optimal solution for previous users). That would also make it clearer why the sensitivity analysis for the approximation of DC(D;l) is non-trivial where an added user could potentially improve the solution for the previous users and removing a user could lead to less optimal solutions for the rest of users.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thoughtful comments. We address the questions and weaknesses listed.\n\n**Q1a. -- bias of estimator** Under the assumption that a bound $\\ell$ on the number of distinct elements per person is known, it is possible to estimate $DC(D)$ in an unbiased manner by releasing $DC(D, \\ell) + Lap(\\ell / \\varepsilon)$. However, this assumption is very restrictive and, in practice, $\\ell$ may be so large that it gives us an estimator with unacceptably large variance. The issue is that the distribution on sizes of $u_i$’s is usually heavy-tailed. Thus we opt for a biased estimator, which provides a clear guarantee – that it is a lower bound with high probability.\n\n**Q1b. – quality of solution** Unfortunately we are not sure that we understand the question. In the worst case the estimate and the true count could be arbitrary different, but in realistic examples they are close to each other.\n\n**Q2a.  – true counts.** We apologize that this was not clear; we will update the results to clarify. Table 1 contains the true counts for each dataset and Tables 2-5 contain the results of the proposed methods; however, the attached table contains the summary with the results returned by the proposed method (for $\\varepsilon = 1$, $\\beta = 0.05$, and $\\ell_\\mathrm{max} = 100$).\n\n**Q2b. – possible improvement.** Our intuition is that our algorithm is optimal, but it is not clear how to even state such a claim formally. Roughly, we believe that $DC(D,\\ell)$ is the “best” possible estimator for $DC(D)$ that has sensitivity bounded by $\\ell$.\n\n**Q3. – reproducibility.** Yes, we plan to release the code with the next revision of the paper. Unfortunately, we were not able to obtain the necessary approval in time for the NeurIPS deadline.\n\nAs for weaknesses mentioned, we are going to add more details in the discussion of the Generalized Exponential Mechanism, since this is not well known; however, it is not the novel contribution of our paper so we don’t want to over emphasize it. We will also add a more detailed sensitivity analysis of $DC(D, \\ell)$.\n"}, {"review_id": "XkYhxkPW16", "reviewer": "Reviewer_FDcy", "summary": "The authors study the fundamental problem of counting the number of distinct elements in a dataset\nin a user-level DP setting, where a user can contribute an unbounded number of items. The main\ncontribution of the paper is an approach to obtain lower bounds through a bounded sensitivity\ncount and a bias-variance perspective. The authors give interesting algorithms to compute\nit quite efficiently, and show a linear time version which trades off efficiency with accuracy.\nThe algorithms are evaluated empirically and show good performance.", "questions": "In line 51, what is the motivation for considering\nM_{\\ell,\\epsilon}(D) - \\frac{\\ell}{\\epsilon}\\log(1/2\\beta)?\n\nIs it assumed that there is a fixed \\ell_{max} for all the data (line 58)? It appears as an input in\nprocedure DPDISTINCTCOUNT, and in the bounds in Theorem 1.1.  This should be clarified\nearlier in that case. The algorithm needs to know \\ell_{max} in that case. Is there a way to specify it?\n\nLine 13 of algorithm 1 and line 10 of Algorithm 2: it might be helpful to make GEM consistent with\nthe name \"Generalized Exponential Mechanism\" used in Algorithm 3\n\nThe baseline sampling algorithm mentioned in lines 131-134 is not really related work, but just a\nbaseline, and could be in the experiments section.\n\nline 176: \"three\" should be \"four\"\n\nline 191: is the sampling done with replacement?\n\nWhat is the \\epsilon value in Fig 1? Does the \"Person Contribution Bound\" refer to \\ell_{max}?\nThe plots are quite interesting. Is there an explanation for why the gap between the algorithms\nand the true counts decreases as in the figure?\n\nTables 2 and 3 are not very easy to interpret. It might be easier to compare the counts as\nfractions or visually.\n\nHow do the results vary with \\epsilon?\n\nWhat is the motivation for considering \\epsilon=1 in the person contribution for the baseline?", "limitations": "To some extent. There are no negative social impacts", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "\nThe problem is very natural and well motivated. The approach considered in the paper, in terms of\nbounded sensitivity, seems quite natural, and is connected to a big literature on Lipschitz extension.\nThe authors give rigorous bounds on the bounds achieved by their algorithms. The empirical results\nare also interesting, and show reasonable performance. The greedy algorithm is also shown to perform\nquite well. The presentation is quite good.", "weaknesses": "The basic ideas in the paper, and the techniques used in the algorithms are fairly simple. The experiments section could be strengthened", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for reviewing the paper. \n\n**Q1. Why $M_{\\ell,\\varepsilon}(D) - \\frac{\\ell}{\\varepsilon}\\log(1/2\\beta)$?** \nUnder user-level DP, it is impossible to compute the exact number of distinct elements since a single user could contribute an arbitrary number of unique elements and differential privacy prevents us from revealing the contribution of a single user.\nThus our goal is to produce a *lower bound* on the number of distinct elements that is as close as possible to the true count. This is the only meaningful guarantee that we can provide under user-level differential privacy.\nHence, to ensure that our output is a lower bound, we have to lower the estimate by $\\frac{\\ell}{\\varepsilon}\\log(1/2\\beta)$ in order to compensate for the possibility that the noise increases the estimate.\n\n\n**Q2. $\\ell_\\mathrm{max}$** The parameter $\\ell_\\max$ is a hyper parameter that is provided as input to the algorithm. This is necessary, as there is no a priori way for the algorithm to know how many elements users are contributing.\n\n**Q3. GEM.** Thanks for highlighting this issue, we will change the caption of the algorithm to say “Generalized Exponential Mechanism (GEM)”.\n\n**Q5. Typo.** Thanks for catching this, we will change this in the next revision of the paper. \n\n**Q6. Sampling.** The sampling is without replacement, since it would only reduce the quality of the algorithm to do sampling with replacement.\n\n**Q7. Fig 1.** Figure 1 shows the results without noise, i.e. $\\varepsilon=\\infty$. The person contribution bound is $\\ell$. So the “matching algorithm” is simply plotting $DC(D,\\ell)$ as $\\ell$ varies, while the other algorithms show how well the baseline and linear-time algorithm can approximate this.\n\n**Q8. Tables 2 & 3.** Thanks for the suggestion! We will explore possibility of splitting the tables or using some sort of bar plots to visualize them.\n\n**Q9. $\\varepsilon$ dependence.** See the attached document for the plot showing dependency on epsilon. (It will be a part of the next revision).\n\n**Q10. Why $\\varepsilon = 1$.** This choice is arbitrary; we consider 1 to be a reasonable value to evaluate, but we will add further values.\n"}, {"review_id": "MKqr86UTrK", "reviewer": "Reviewer_BQdm", "summary": "Suppose a data set consists of (user, item) pairs. The paper provides an estimate of the count of the number of distinct items that satisfies user level differential privacy. This differs from existing work in two ways. Existing work 1) considers item streams with item, not user, level differential privacy and 2) is highly concerned about computation costs and uses data sketches which have bounded size. \n\nIt solves the problem by generating lower bounds with bounded sensitivity by converting the distinct count to a max flow problem.", "questions": "1. What is the distinction between maximal and maximum bipartite matching? A quick search seems to regard these descriptions as the same problem. Does the greedy algorithm generate the maximal matching that approximates the maximum matching? \n\n2. I'd be happy to increase the rating if the weaknesses 1 & especially 2 are addressed.", "limitations": "yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a novel user-level privacy formulation of the distinct count problem. The main ideas are presented well, and it is technically sound.", "weaknesses": "1. The title could better describe the key feature of the problem, providing user level privacy. Since most distinct counting papers are about approx distinct counting and streaming/distributed algorithms, I think readers have an expectation that this paper would address this given the title and it's a bit of a let down when it doesn't.\n\n2. The related work section is somewhat inaccurate in its descriptions. E.g.\n* Desfointaine et al is a universal result about any distinct counting method which is mergeable. Changing the algorithm design can't get around this. But the results only imply that you can't merge many times and preserve both privacy and accuracy, not that you can't build a private sketch.\n* Smith et al doesn’t actually analyze the Flajolet-Martin (a.k.a. PCSA) sketch but their own tweak of the LogLog sketch (by Durand and Flajolet). (Though this inaccuracy is totally understandable given their title.)\n* Dickens et al is also a universal result for any order invariant sketch. \n* Both Smith et al and Dickens et al are pan private in the streaming setting as well\n* Note neither claim to provide privacy under merges. \n\n3. There is also some related work on private multiparty computation for distinct counts. e.g. \"Privacy-Preserving Secure Cardinality and Frequency Estimation\" Kreuter et al 2020\n\n4. The empirical results for the greedy algorithm are nice, but the bound is quite bad for this application since it only gives you an estimate of the correct order of magnitude. It's also not clear what to do in large scale distributed data settings. These are fairly minor weaknesses given the paper's scope though.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thoughtful comments. \n\n**W1.** We agree that the title could be misleading, we will rename the next revision to “Counting Unique Elements Under Person-level Differential Privacy”. \n\n**W3 & W3.** Thank you very much for pointing out the issues in our related work section, we will make all the suggested changes in the next revision of the paper.\n\n**W4.** Unfortunately, the linear time algorithm’s worst-case guarantees are not great, but it is well-known that the greedy algorithm for approximating maximum matching performs well in practice.  As for the distributed data case, unfortunately we don’t have a solution now: it is known that computing maximum matching in a distributed case is tricky, and it is even more tricky for us since we must bound the sensitivity.\n\n**Q1.** “Maximal matching” and “maximum matching” is the standard terminology (see https://en.wikipedia.org/wiki/Matching_(graph_theory)#Definitions ) though it is understandably confusing.\n\n- A maximal matching is a matching that is maximal by inclusion; i.e., M is a maximal matching iff for any matching M’ such that M subset of M’, M’=M.\n- A maximum matching is a matching that is maximal by size/cardinality; i.e., M is a maximum matching iff for any matching M’ such that |M| <= |M’|, |M’|=|M|.\n"}]

Author rebuttal:
Plots that we requested by reviewers are in the attached file.

Meta-review: Summary:
=======
This paper introduces a user-level differentially private method for counting unique elements of a dataset that is shared by users. A user may contribute many elements to this count. The difficulty is that that there is no bound on individual contribution and some users may have very skewed contributions in the tail.

This paper presents two algorithms: a polynomial time exact solution and linear approximation of the $\epsilon$-DP counting algorithm. Theoretical definition and analysis of the algorithm is provided first, alongside evaluation on four datasets. And contributes the user contribution bounds (including 10,50,90%ile) for the datasets.

Reviews:
=========
The paper has borderline reviews. However the high confidence (4) reviewers have given the higher scores (5,6,7) leaning towards accept and the lower confidence (3) reviewers leaning towards the lower scores (4). The authors addressed weaknesses and concerns in review BQdm, resulting in an increase in score to 7. 
Reviewers are generally in concordance with understanding the contributions of the paper. However, each reviewer identifies several weaknesses of the work.

* CW1: Application areas
* CW2: Biased estimator
* CW3: Solution quality
* CW4: Simplicity of algorithm
* CW5: Inaccuracy in related work section
* CW6: Novelty of work w.r.t. Kreuter et al., 2020

Some of these are mitigated through discussion:

* CW1: Federated settings, and multi-party counting are application areas where this work can be applied

* CW2: The authors respond with a suitable justification for why biased estimator is not a major issue, providing a formulation of unbiased estimator with discussion justifying why the variance of this estimator would be unacceptable.

* CW3: Empirical results show the generation solutions were acceptable. I assume that modification of $\epsilon$ will allow some tuning of the privacy-accuracy tradeoff. However, this was not studied empirically in the paper. 

* CW4: I do not believe this to be a reasonable reason to reject a paper. The underlying task is counting unique elements. The paper uses a DP framework where the contributions of a single party are bounded. This is a reasonable contribution.

* CW5: I believe these issues to be minor and would encourage the authors to follow the corrections from  BQdm.

* CW6: The Wright/Skvortsov/Kreuter/Wang/Mirisola paper does introduce the privacy preserving problem with a DP framework introduced by reviewer BQdm. I would suggest this could be included in the literature survey. Reading the paper, it appears as if this is an introduction of many methods including database-level DP rather than user-level DP and has much less rigorous analysis than the submitted manuscript.




Reason for decision:
========
Reviewing the merits of the paper and in conjunction with the reviews, there are some weaknesses identified with adequate mitigations.  I think it is probably worthy of acceptance, but probably a weaker accept.  Reviewers provided accept ratings of 5,4,6,7 with confidence 4,3,4,4
Decision: Accept (poster)