Differentially Private Linear Sketches: Efficient Implementations and Applications
Authors: Fuheng Zhao
Dan Qiao
Rachel Emily Redberg
Divyakant Agrawal
Amr El Abbadi
Yu-Xiang Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Differential Privacy
Linear Sketch
Frequency
Top K
Heavy Hitter
Frequent Items
Quantile
Streaming Algorithm

Abstract: Linear sketches have been widely adopted to process fast data streams, and they can be used to accurately answer frequency estimation, approximate top K items, and summarize data distributions. When data are sensitive, it is desirable to provide privacy guarantees for linear sketches to preserve private information while delivering useful results with theoretical bounds. We show that linear sketches can ensure privacy and maintain their unique properties with a small amount of noise added at initialization. From the differentially private linear sketches, we showcase that the state-of-the-art quantile sketch in the turnstile model can also be private and maintain high performance. Experiments further demonstrate that our proposed differentially private sketches are quantitatively and qualitatively similar to noise-free sketches with high utilization on synthetic and real datasets.

Differentially Private Linear Sketches: Efficient
Implementations and Applications
Fuheng Zhao"t fuheng_zhao www.hugshaauussb..om edu
Dan Qiao* danqlao@ucsb. edu
Rachel Redberg" rredbergducsb edu
Divyakant Agrawal" agrawallcs www.uccccee.. edu
Amr EI Abbadi'
Yu-Xiang Wang" yuxiangwBucsb.. edu
amrêca ucsb. edu
Abstract
Linear sketches have been widely adopted to process fast data streams, and they can be used to accurately answer frequency estimation, approximate top K items, and summarize data distributions. When data are sensitive, is desirable to provide privacy guarantees for linear sketches preserve private information while delivering useful results with theoretical bounds. We show that linear sketches can ensure privacy and maintain their unique properties with small amount of noise added at initialization. From the differentially private linear sketches, we showcase that the state-of-the-arr quantile sketch in the turnstile model can also be private and maintain high performance. Experiments further demonstrate that our proposed differentially private sketches are quantitatively and qualitatively similar to noise-free sketches with high utilization on synthetic and real datasets.
Introduction
Data sketches are fundamental tools for data analysis, statistics, and machine learning [Cormode and Yi, 2020]. Two of the most widely studied problems in data summaries are frequency estimation and quantile approximation. Many real world applications need to estimate the frequency of each item in the database and understand the overall distribution of the database. These applications include stream processing [Das et al., 2009, Bailis et al., 2017], database management [Misra and Gries, 1982, Metwally et al., 2005, Zhao et al., 2022], caching [Zakhary al., 2020], system monitoring [Gupta et al., 2016, Ivkin et al., 2019, Zhao et al., 2021], federated learning [Rothchild et al., 2020], among others.
On one hand, the motivation for data sketch algorithms is to efficiently process a large database and extract useful knowledge, since computing the exact information for large amount of data is both time and memory intensive. For instance, Munro and Paterson [1980] proved that to find the true median of a database with n items using p sequential passes requires at least Q(n l/)) memory. On the other hand, to protect user-level privacy, privacy- privacy-preserving algorithms limit the disclosure of private information in the database so that an observer cannot infer much about an individual. Recent works have shown that data sketches be integrated with privacy-enhancing technologies to provide insightful information and preserve individual privacy at the same time [Cormode, 2022).
Differential privacy [Dwork al., 2006] is widely-accepted definition of privacy. Recently, re- searchers have observed that some data sketches are inherently differentially private [Blocki et al., 2012, Smith et al., 2020], while many other data sketches need modifications to the algorithm to be
DDepartment Computer Science, UC Santa Barbara. The first two authors contributed equally.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

differentially private. In particular, substantial amount of literature has focused on differentially private data sketches for tasks such as linear algebra [Upadhyay, 2014, Arora et al., 2018], cardi- nality estimation [Mir et al., 201 1, Pagh and Stausholm, 2021, Dickens et al., 2022] and quantile approximation [Tzamos et al., 2020, Gillenwater et al., 2021, Alabi et al., 2022].
In this paper, we introduce new differentially private algorithms that support both insertions and deletions for frequency, top k, and quantile approximation. While many data sketches assume an insertion-only model [Greenwald and Khanna, 2001, Shrivastava et al., 2004, Karnin et al., 2016] or
hounded-deletion model [Jayaram and Woodruff, 2018, Zhao al., 2022, 2021], our algorithms build on top of linear sketches [Charikar et al., 2002, Cormode and Muthukrishnan, 2005] and operate in the turnstile model, which allows an arbitrary number of insertions and deletions into the database. Earlier, researchers attempted to prove CountSketch [Charikar et al., 2002] itself preserves differential privacy, but the authors acknowledged that there are issues the proof [L. et al., 2019]. Instead of proving that linear sketches, i.e., both Count-Min and CountSketch, are inherently differentially private, we add a small amount of Gaussian noise at their initialization to provide privacy guarantee, while maintaining linear sketches' original properties, providing high utility for frequency and top K estimations, and keeping update and query algorithms unchanged. We also demonstrate that our analysis provides the tight uniform bound (Section 3.1 and Appendix E). In addition, we propose the first differentially private quantile sketch in the turnstile model by leveraging the differentially private linear sketch. Our differentially private sketches affecting privacy guarantees based on the post-pa post-procsssing immunity. Following prior works [Choi et al., 2020, Smith et al., 2020], we assume ideal random hash functions exist, and this assumption can be replaced in practice by cryptographic hash functions [Dickens et al., 2022].
be queried an arbitrary number of times without
2 Preliminaries
Consider database X= ( DE[N] of N items that drawn from large universe of size U, such as IPv4 address of size 2 and for each insert or delete operations, one item can be inserted into or deleted from the database X. To support ordered statistic such as quantile, we assume that the universe is some finite totally ordered data universe.
Definition 2.1. Given a database X, the frequency of an item x is f(x)= =i returns if x, and O otherwise.
where π (it=
=x)
Definition 2.2. Given database X of items drawn from an ordered universe, the rank of an item is R(z)= Σm (i, z) where π. returns if is less equal to x and O otherwise.
Given the large size of N, calculating the actual statistics, such as frequency and quantile, is often hard, and hence most applications are satisfied with an approximation. The randomized frequency estimation problem takes an accuracy parameter and a failure probability 33 such that, for any item x, f(z) - f=)] < 7-N N with high probability 1 - 8, where f(x)) is the estimated frequency and f(x) the true frequency [Cormode and Hadjieleftheriou, 2008]. In addition, the randomized quantile approximation problem also takes an accuracy parameter and a failure probability 3 such that, for any item æ, [f(x))) R(x)] < 7 N with high probability 1 - where R(x)) is the estimated rank
and R(x) the actual rank [Karnin et al., 2016].
2.1 Differential Privacy
Definition 2.3. Databases X and X' are neighbors (X ~ X'), if they differ in at most one element.
Through this paper, we assume the update/ree /replace definition of differential privacy instead of add/remove definition of differential privacy, in which one item in X is updated or replaced by another item in X' [Vadhan, 2017].
Definition 2.4 (Differential Privacy [Dwork et al., 2006)). A randomized algorithm M satisfies (c. 6) diffferennta privacy ((c, 6)-DP) if for all neighboring databases X, X' and for all possible events E in the output range of M, we have
(X E E) E . IP(((X)) E EE+ 5
When 8 0, e-DP is known as pure DP, and when 8 > 0, (e. 6)-DP is known approximate DP.

---

Definition 2.5 (Gaussian Mechanism [Dwork et al., 2006]), Define the lg sensitivity of a function f: N H Rd as
22 sup neighboring X.X
[I((X) 5(x))=(())lll>
The Gaussian mechanism M with noise level is then given by
M(X) ((0)
Specifically, the Gaussian mechanism is known to satisfy a stronger notion privacy known as zero- concentrated differential privacy (zCDP, defined below); zCDP lies between pure and approximate DP and can be translated into standard DP notations, as shown in Lemma 2.9. Moreover, zCDP satisfies cleaner composition theorems, as shown in Lemma 2.7.
Definition 2.6 (zCDP [Dwork and Rothblum, 2016, Bun and Steinke, 2016]). A randomized mecha- nism M satisfies p-Zero- Concentrated DiffeddDiiiffe Differential Privacy (P-ZCDP), for all neighhoring databases X, X' and all a E (1,00),
D& (M(()X)) S po:,
where Da is the Renyi divergence [Van Erven and Harremos, 2014].
Lemma 2.7 (Adaptive composition and Post Processing of zCDP [Bun and Steinke, 2016]). Let M. X² - y and M' x y + Z. Suppose M satisfies p-zCDP and M' satisfies p'-xCDP (as a function of its first argument). Define M" X - Z by (x) M' (z. M())). Then M" satisfies (p + pf) >zCDPP
Lemma 2.8 (Privacy Guarantee of Gaussian mechanism [Dwork al., 2014, Bun and Steinke, 2016)). Let f N& + Rd be an arbitrary d-dimensional function with &g sensitivity 22 = sup mnigghhboinng x,X IIf(X) fl2) Then for any p 0, Gaussian Mechanism with parameter
2² Ai
satisfies p-zCDP.
2p
Lemma 2.9 (Converting zCDP DP [Bun and Steinke, 2016)). If M satisfies p-zCDP then M satisfies (p + 2/ (og()))))
As we use exclusively Gaussian mechanisms and their composition in our proposed algorithms, our method actually satisfies (c, 5)-DP guarantees with stronger parameters than what is implied by zCDP via techniques from [Balle and Wang, 2018, Dong et al., 2019], which reduces the e parameter by a sizable fraction in typical parameter regimes. We stick to zCDP for clarity and generality, because all our results would apply without changes if we modify the noise into other mechanisms satisfying zCDP, e.g., the Discrete Gaussian Mechanism [Canonne et al., 2020].
2.2 Revisiting Linear Sketches
Charikar al. [2002] proposed the CountSketch, randomized algorithm that summarizes database and solves the frequency estimation problem. The CountSketch uses a x w array of counters, i.e, Cid, w], where all the counters are initialized to zero, and has two sets of independent hash functions and g. For each row r, the hash function h, maps input items uniformly onto {l...., w) and the hash function 9, maps input items uniformly onto (-1, +1]. For item with value E {-1, +1}, CountSketch updates d counters, one per each row, based on the hash values such that for a particular row r, (x)) will be added subtracted to the counter at the (x: index depending on whether is being inserted or deleted respectively, as shown in Algorithm 1. Hence, the update time is O(d). To estimate the frequency of item x, CountSketch will output the median gr (x) C[r, hy, as shown in Algorithm 2. By updating each row's counter based on the hashed value of either 1 or and reporting the median for query, CountSketch provides an unbiased estimate. To reduce the failure probability of bad estimations, d is set to Ollog (1o)(118)) and it uses O 1 log( })) space to solve the frequency estimation problem.
Algorithm Linear Sketch Update(z, (z.
I: Input: Item x with value v E (-1,+1), counter arrays C, and two sets of hash functions (hı,.. ... .......herree hows and (01,-...9..rowel
for o <- 1,2.....
..2......roows C.rous
3: Clr, ly (x)] ) + C/r, hy (x)) + 9. (x)
4: end for
5: Output: C.
3

---

Cormode and Muthukrishnan [2005] proposed the Count-Min sketch that shares the same initializa- tion, update, and data structure as CountSketch. Count-Min sketch also uses O log( (3)) space to solve the frequeney estimation problem. major difference that Count-Min sketch makes all hash functions in set y return positive 1. As a result, to estimate the frequency of item Count-Min sketch returns min Srea C[r, (x)] instead of the median, as shown in Algorithm 2. In addition, it has the nice property of never underestimating item's 's frequency. Since linear sketches can approximate an item's 's frequency accurately, they also solves the top K approximation problem by returning the items associated with the highest estimated frequency.
Algorithm 2 Linear Sketch Query(z)
1: Input: Item v, counter arrays C, and two sets hash functions (hr,.... hC.rows) and {gi,... gC.rawa)
2: arr f-
3: for r f- 1,2... ,,,,,..,,Crousss Crows do
4:
(rr.ap)eudgg-(x) C'r, (x)))
5: end for
6: Output: min(arr) for Count-Min or median(arr) for CountSketch.
Gilbert et al. [2002] made the connection between frequency and quantiles, in which the quantile range can be decomposed into at most log U dyadic intervals [Cormode et al., 2019] and the sum of the estimated frequencies for these intervals gives the estimated rank. Wang et al. [2013] leveraged the unbiased property of CountSketch and proposed the Dyadic CountSketch (DCS) to estimate the frequencies of each dyadic interval. For more specific details, Appendix and [Cormode and Yi, 2020] provide a comprehensive analysis of quantile sketches.
3 Private Linear Sketches
In this section, we present new algorithms for differentially private linear sketches. We highlight that our Private Count-Min and CountSketch only require different initialization while they share the same update (Algorithm 1) and query (Algorithm with the original Count-Min and CountSketch. Therefore, the implementation of our algorithms is efficient. Below we show our private initialization.
Algorithm 3 DP Linear Sketch Initialization with Gaussian Noise
1: Input: Desired accuracy parameter failure probability 3, and budget for zCDP
2: Initialize Counter Arrays
3: a + /log(2/3)) 3)PP
2
logt log
4: E +-
B
for r' 6- 1,2, 1........
(3) do
6:
for a +- 1,2,.... 1/7 do
7:
Clr, + (00, a²) if Private CountSketch
8:
Clr, + E (O0 if Private Count-Min
end for end for
10:
11:
Output: C.
In Algorithm 3, the set of arrays we use C' which consists of log(2/3) arrays with length 1/7, which has the same space complexity as original Count-Min and CountSketch. Recall that two neighboring databases and X' differ by at most one item. Therefore, after updating all the items respectively, for each corresponding array in C(X) and C(X'), they differ by most two elements and the difference at most 1. Then the fe-sensityvity of the set of arrays C' is bounded by
A /2 log(2/3).
By applying the Gaussian Mechanism (Definition 2.5), can add independent Gaussian noises (0 2 to each counter in C, where log(2/8) Due to the privacy guarantee of Gaussian
Mechanism (Lemma 2.8), it satisfies 2
p-zCDP.

---

for simplicity, will use E in Algorithm 3 and the proof in Appendix A. The private version of Count-Min can be derived by adding independent Gaussian noises WE,, E, o²) to each counter of C, while the private version of CountSketch can be derived by adding independent Gaussian noises (0, o²) to each counter of C. The private versions of Count-Min and CountSketch are derived by combining Algorithm 3, Algorithm I, and A Algorithm 2.
Define (3,,% 7, p)
V 10g
log
logi (
3.1 Main results about Private Count-Min and CountSketch
We present the privacy guarantee and utility analysis of our Private Count-Min and CountSkerch below. Recall that for each item x, we perform update as in Algorithm 1 and query in Algorithm 2.
In addition, f(z) the output estimated frequency and (=) is the actual frequency. To provide bound for the additional error due to DP, we define f() to be the non-private estimated frequency (the output of the original Count-Min and CountSketch with the same of hash functions). We begin with the properties of Private Count-Min. Note that all the proofs are deferred to Appendix A.
Theorem 3.1. Private Count-Min satisfies p-zCDP regardless of the number of queries. Furthermore, with probability 3, the output (x) satisfies that
xx 0 S f(x) f(x) - 2E.
In addition, for each item n, with probability 8,
0 0 f(z) fz) y N 22E.
Comparison to Count-Min. Comparing our Theorem 3.1 with the conclusion in [Cormode and Muthukrishnan, 2005], our Private Count-Min preserves the nice property that the output will not underestimate the frequeney with high probability. Furthermore, within the most popular regime where the privacy budget is a constant, the additional error bound due to differential privacy is independent of the size database N, therefore will become negligible N goes large.
Justification of our Gaussian noise. Note that with high probability, all the noises we add (E + di.j Jif NO, o²)) will be non-negative. Therefore, the noise we add and the original error induced by Count-Min will directly sum up and lead to larger error in evaluation. However, additional E ensures that with high probability, for item x, the output will not underestimate the actual frequency. This nice property enables the good performance of our Private Count-Min when used in approximate top i task, as shown Section 5.
claim that the
Next, Theorem 3.2 shows the properties of Private CountSketch.
Theorem 3.2. Private CountSketch satisfies p-ZCDP regardless of the number queries. Further- more, the frequency query from Private CountSketch is unbiased and with probability B,
Vx, (f(x)) F((x)) s E.
In addition, for each item x, with probability 1-3. B.
lf(z) - f(x) S N E.
Comparison to CountSketch. Comparing our Theorem 3.2 with the conclusion [Charikar et al., 2002], our Private CountSketch preserves the nice property that the output will be an unbiased estimate of the frequency. This property enables our use of Private CountSketch in quantile estimation below (Section 4). Furthermore, within the most popular regime where the privacy budget p is constant, the additional error bound due to differential privacy is independent of the size of database N, thus it will become negligible as N goes large.
3.2 The Uniform Bound of Additional Error
Theorem 3.1 and Theorem 3.2 show a uniform bound sup, 1f((x) S O(E) for linear sketches, which upper bounds the additional enror imposed the estimated frequency due to Differential Privacy guarantees. To derive the point-wise bound for [f(x) fx)) combine
result with
the point-wise bound for [f(x) [x)) [Cormode and Muthukrishnan, 2005, Charikar et al., 2002] (note it is straightforward to apply other analyses on the point- wise bound [Minton and Price, 2014,
Larsen et al., 2021] due to the triangle inequality). Moreover, Appendix F, we demonstrate that
analysis provides the tight uniform bound when items drawn from a large universe.
5

---

Private Quantile Sketches
In this section, we apply our Private CountSketch to state of the quantile sketches in the turnstile model. Our private Dyadic CountSketch can estimate all the quantiles accurately at the same time while ensuring differential privacy.
4.1 Revisiting DCS
In [Wang et al., 2013], it is shown that DCS can return all 7-approximate quantiles with constant probability using space O ( log" 1.5 U log 1oggl~(1o (Lor)) More specifically, the sketch structure here consists of log U CountSkecches, each CountSketch uses counter arrays C, which is d counters. The choice of d, follows d = θ (log( (ox and w O (Vlog U log( log )/7)
4.2 Private DCS
In this work, we aim to estimate the quantiles accurately while preserving privacy. We do this by replacing CountSketch with PrivateCountSketch which bases on the same structure as CountSketch discussed above. Given the privacy budget p. the privacy budget of each Private CountSketch thus Po U due to composition of zCDP (Lemma 2.7). The fz-sensitivity of each Private CountSketch
A2 = =2=2(Vv1) = (Vine log U
? )
To keep the whole zCDP (Lemma 2.7).
algorithm p>CPP, it suffices Therefore, Gaussian Mechanism (Definition 2.5) with x²
keep each CountSketch Po-
O (log U log
log Ui /p
ensures p-zCDP (Lemma 2.8).
Similar to Lemma A.I. define
log log log
log log to we can prove that with constant probabil-
E(y,U)=0 =
log
ity, all the Gaussian noises we add to all log U CountSketches are bounded by E (for simplicity, we use E to represent E(y,U) U)).
Conditioned on the high probability event above, we prove that for a fixed quantile, the estimated quantile will be accurate with high probability. As has been proven in Theorem 3.2, the output estimated frequency is unbiased for any item. Therefore, similar to [Wang et al., 2013], for any item (corresponding fixed CountSketch), we have the output f(x) of that CountSketch satisfies
P [[()) f(x))
> N E
< exp (-O(d))
log U
By union bound, with probability log U O log = - O(r), for any item corresponding to this fixed quantile, the error of CountSketch is bounded by 1 N E. Conditioned upon this event, by Hoeffding's inequality, with probability O errors is bounded by
log U the sum of log U such independent
log U 7
N -
log U log
+ = N
Ing U/ log
lon
log U/ logg
where E' =
log
To sum up, for a fixed quantile, with
vp
probability O(r), the estimating error bounded by y N E'.
Finally, apply another union bound on the 1 different quantiles, with constant probability, all the 7 quantiles are estimated accurately (within the error bound (2)). Note that similar to [Wang et al., 2013], the failure probability here is constant. For any failure probability 3, we can further increase d by factor of log 1 to reduce this failure probability to B.

---

Take-away of Private DCS. First, our Private DCS has a same space complexity as the original DCS. In addition, according to (2), the additional emror bound is proportional to
log U log + (ignoring
sp
log log terms), and independent the size of database N. In the most popular regime where the privacy budget is constant, the additional error bound only appears as lower order terms, which will become negligible as goes large.
Evaluation
We have implemented DP linear sketches and DP DCS, and conducted extensive experiments to evaluated the privacy-utility trade-off of our proposed private sketches. The implementations are written in Python with the advantage of fast prototyping and good readability. The code for the following experiments can be found on Github "
5.1
Data Sets
The experimental evaluation is conducted using both synthetic and real world data sets. We consider the synthetic Zipf dataset Zipf [2016] with universe size of 2 and the source IP addresses from CAIDA Anonymized Internet Trace 2015 dataset pas with universe size of 232, For each independent run in the experiments, we use an input database size N 105.
5.2 Metrics
In all experiments, average the various metrics over 5 independent runs minimize the measure- ment variance. The metrics used in the experiments are:
Average Relative Error: Let the set y denotes all unique items in the database. Average Relative Error (ARE) is computed based on V in which v Σeev [[(e)=((e))
f(e)
F1 Score: Fl score is the harmonic mean of the precision and recall (2 precision precision+recatl
Average Rank Error: For each evenly spaced quantile and its associated item, we average the distance between the true rank and estimated rank.
We use ARE evaluate sketch performance on frequency estimation and Fl score evaluate the sketch's 's performance in identifying the top 10 items. For quantile approximation, we consider the m evenly spaced quantiles and items. For instance, m we consider the rank error for the median item; if m = 2, we consider then average rank eтror for the 33rd and 67th percentile items. Lower ARE and average rank error, and higher F1 score indicate better approximation.
5.3 Private Linear Sketches Experiments
To evaluate the utility of DP linear sketches, compare the average relative error (ARE) and F1 score for frequency estimation and identify the top 10 items, respectively. As shown in Figure 1, the x-axis represents the space budget for each sketch (from 9.2 KB to 147.3 KB), and the y-axis denotes ARE or Fl score. The DP linear sketches use E {0.1, 1, 10} in which lower value indicates more noise need to be added, and all sketches assume 8 1%.
For frequency estimation, the performance our private CountSketch with various privacy budgets basically equivalent the performance of the non non-private CountSketch. Under different space and privacy budgets, they have minimal difference in ARE for both Zipf and CAIDA datasets, meaning that, while providing strong privacy guarantee, the estimated frequencies are still very accurate. The accurate estimation of private CountSketch is primarily due to the unbiased nature CountSketch in which, by adding Gaussian noise, the private CountSketch still provides unbiased estimation for an item's frequency as proved in Theorem 3.2. As shown in both Figure ((a) and Figure 1(b), the performance of private Count-Min degrades when the space budget increases the privacy budget decreases. This behavior is expected as the upper bound on the frequency error in Theorem 3.1 has dependency on both 7 and p. order to preserve the property of underestimating an item's
https//iihhab.oomm//offouuulenee Private-Linest SheteeeLinear-Skechhess
7

---

frequency, the private Count-Min sketch needs to add larger noise to each counter when the number of counters increases. As result, the estimated frequencies for fow-frequency items become inflated and this in turn decreases the overall accuracy.
Zipf(1.0)
CAIDA
3000
CM
CM. p-0.1
CM. p-0.1
p=1
2000
p=1
CM, p=10
CM, p=10
ARE
p.O
p=0.1
CS, p-1
CS.p-1
3000
p=10
3000
p=10
500
Space(KB)
Space(KB)
(a) Frequency Estimation with Zipf
(b) Frequency Estimation with CAIDA
Zipf(L.0)
CAIDA
1.00
CM
Score
094
C5
Score
0.2
p=0.1
0725
CM, p-0.1
CM, pm1
0.00
p-10
p-10
C5, p-0.1
0675
C5, p=0.1
p-1
0850
p=1
084
C5 p=10
C5 p-10
2'
Space(KB)
Space(KB)
(c) Top 10 with Zipf
(d) Top 10 with CAIDA dataset
Figure Comparison of non-private linear sketches and DP linear sketches with various privacy budget under synthetic and real world datasets. The experiments assume 1% and N 10
For approximate top 10 items, private CountSketch has similar performance to CountSketch. Since both non-private and private CountSkerch are unbiased, they may underestimate the frequency of true top K items and decrease the recall. On the other hand, the property of no underestimation is desirable for approximate top K items. In particular, non-pre non-private and private Count-Min sketch score high Fl scores for all datasets. While providing privacy guarantees, private Count-Min achieve 1.0 Fl scores for all space and all privacy budgets in Zipf dataset, as shown Figure ((c).
5.4 Private Quantile Sketch Experiments
Zipf(1.0)
CAIDA
DCS
Average Rank Error
Average Rank Errar
p-0.1
DCS, p-1
DCS
p-10
p=:0.1
Upper Bound
DCS, p=1
p=10
Upper Bound
quantiles
quantiles
(a) Quantile Approximation with Zipf
(b) Quantile Approximation with CAIDA
Figure 2: Compare DCS and DP DCS with various privacy budget under synthetic and real world datasets. The experiments assume y 1%, 10a. and the desired error upper bound is 10x (y

---

To evaluate the utility of DP DCS, we compare the average rank error. As shown in Figure 2, the x-axis represents the number of evenly spaced quantiles. and the y-axis denotes the average rank error. The DP DCS use privacy budget p E {0.1,1, 1, 10) and all sketches assume 7 = 1%.
For the quantile approximation, we observe that the increase in the number of evenly spaced quantiles does not impact the average rank eπrоr, as shown in both Figure 2(a) and Figure 2(b), Since the CAIDA dataset universe size (2 is larger than Zipf dataset universe size (2*%), the average rank error in the CAIDA dataset is larger than the average rank error in the Zipf dataset. As shown in Equation (2), the error bound has term depending on the universe size in which large universe size leads to more error. When the privacy budget decreases, the average rank eπror increases as more noise needs be added. Comparing DP DCS with strong privacy (p 0.1) to DCS, the increase in rank error is relatively small compared to the database size of 10 In addition, the desired rank eπror upper bound 7 N 10 and all the rank errors are one order of magnitude lower.
6 Related Works
In this section, we discuss and compare our results to previous literature on Private Count-Min Sketch [Mir et al., 2011, 1, Melis et al., 2015, Ghazi et al., 2019], and the concurrent work on Private CountSketch [Pagh and Thorup, 2022]. In fact, Pagh and Thorup [2022] and us both independently discovered the same algorithm for Private CountSketch with differences in the theoretical analysis. To the best of our knowledge, we are the first to present DP quantile sketch in the turnstile model.
Private Count-Min. Mir et al. [2011] proposed to add Laplace noise into the Count-Min Sketch estimator to derive the number of heavy hitters with Pan- Pan-Privacy [Dwork et al., 2010]. Similarly, Melis et al. [2015] add independent Laplace noise to each counter of the sketch instead of the estimator. However, adding Laplace noise breaks the nice property of never underestimation in Count-Min. In contrast, our private Count-Min guarantees no underestimation with high probability. [Ghazi et al., 2019] added one-sided binomial noise into each counter of the sketch to preserve the property of no underestimation. However, using the Binomial mechanism inherently implies approximate differential privacy [Canonne et al., 2020]. In contrast, by using the Gaussian mechanism, our Private Count-Min provides the stronger concentrated differential privacy guarantee.
Private CountSketch. Pagh and Thorup [2022] and us both independently discovered the same algorithm for private CountSketch. There is a major difference in the analysis and we believe both analyses are valuable, in which Pagh and Thorup [2022] focused on deriving a tight point-wise bound for [f(x)) - f(x)], while we focused on deriving a uniform bound for sup, 1f(x)= - f(x)). Our uniform bound for sup., If(x) - f(x) can derive the point-wise bound for If(x) f(x)). by combining our result with any point-wise bound for [=() fx)) due to the triangle inequality. [Pagh and Thorup, 2022] obtains a tighter point-wise bound by using concentration of median instead of
triangle inequality. However, Pagh and Thorup [2022]'s analysis can not imply the point-wise bound
for (x) f(x)). More detailed comparisons are included in Appendix C.
7 Conclusion
In this work, we demonstrate that linear sketches can he made differentially private and provide useful information while maintaining their original properties by adding a small amount of Gaussian noise at initialization. In addition, leveraging the private CountSketch, we propose the DP DCS for quantile approximation in the turnstile model. DP DCS achieves low rank errors even for a large data universe. Moreover, for all the proposed algorithms, when the privacy budget is constant, the additional error due to privacy is independent of the database size and the error will become negligible when the database grows larger. Moreover, private linear sketches bring new opportunities for other statistical questions such as the private euclidean distance estimation [Stausholm, 2021] which can be calculate as the dot product of two private linear sketches As a result, we believe our proposed algorithms are efficient and practical for real-world systems and enable these systems to perform data analysis and machine learning tasks privately.

---

Acknowledgments and Disclosure of Funding
This work partially supported by gifts from Snowflake Inc, and NSF grants CNS-1703560, CNS- 1815733 and CNS-2048091. The authors thank Rasmus Pagh for helpful discussion regarding their concurrent work [Pagh and Thorup, 2022]. The authors also thank Adam Smith for clarifying the mergeability in the inherently private Flajolet-Martin Sketch (Smith et al., 2020].
References
Anonymized internet traces 2015, https://catalog. caida, http://aaaaaaaaaaaaoooooooaaaaaa www.///taali//tttttttaaaaaaaaaaa 2015_pcap. Accessed: 2022-5-10.
Daniel Alabi, Omri Ben-Eliezer, and Anamay Chaturvedi. Bounded space differentially private quantiles. arXiv preprint WXXi:2201.03338 2022.
Raman Arora, Jalaj Upadhyay, et al. Differentially private robust low-rank approximation. Advances in neural information processing systems, 31, 2018
Peter Bailis, Edward Gan, Samuel Madden, Deepak Narayanan, Kexin Rong, and Sahaana Suri. Macrobase: Prioritizing attention in fast data. Proceedings of the 2017 ACM International Conference Management of Data, pages 541-556, 2017.
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning. pages 394-403. PMLR, 2018.
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The johnson-lindenstraus transform itself preserves differential privacy. In 2012 IEEE 53rd Anmual Symposium on Foundations of Computer Science, pages 410-419, IEEE, 2012.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryplography Conference, pages 635-658. Springer, 2016.
Clément L Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. Advances in Neural Information Processing Systems, 33:1 33:15676-15688, 2020.
Moses Charikar, Kevin Chen, and Martin Farach-Colton Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pages 693-703. Springer, 2002.
Seung Geol Choi, Dana Dachman-Soled, Mukul Kulkarni, and Arkady Yerukhimovich. Differentially- private multi-party sketching for large-scale statistics. Cryptology ePrint Archive, 2020.
Graham Cormode. Current trends in data summaries. ACM SIGMOD Record, 50(4))6-15, 2022.
Graham Cormode and Marios Hadjieleftheriou. Finding frequent items in data streams. Proceedings of the VLDB Endowment, 1()):1530-155) 2008
Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58-75, 2005.
Graham Cormode and Ke Yi. Small summaries for big data. Cambridge University Press, 2020.
Graham Cormode, Tejas Kulkarni, and Divesh Srivastava. Answering range queries under local differential privacy. Proceedings of the VLDB Endowment, 12(10): 126-0):1126-1133 126-1138, 2019.
Sudipto Das, Shyam Antony, Divyakant Agrawal, and Amr El Abbadi. Thread cooperation in multicore architectures for frequency counting over multiple data streams. Proceedings of the VLDB Endowment, 2(1):217-228, 2009.
Charlie Dickens, Justin Thaler, and Daniel Ting. (nearly) all cardinality estimators are differentially private. arXiv preprint arXh::2003.15400, 2022.
10

---

Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 2019.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. 1603.0003331888 2016.
arXiv preprint
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages (64. Springer, 2006.
Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N Rothblum, and Sergey Yekhanin. Pan- Pan-private streaming algorithms. In ics, pages 66-80, 2010.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4)2211400 2014.
Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. On the power of multiple anonymous messages. arXiv preprint arXiv: 1908. 11358, 2019.
Anna C Gilbert, Yannis Kotidis, S Muthukrishnan, and Martin J Strauss. How summarize the universe: Dynamic maintenance of quantiles. In VLDB 02: Proceedings of the 28th International Conference on Very Large Databases, pages 454-465. Elsevier, 2002.
Jennifer Gillenwater, Matthew Joseph, and Alex Kulesza. Differentially private quantiles. In International Conference Machine Learning, pages 3713-3722 PMLR, 2021.
Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries.
ACM SIGMOD Record, 30(2):58-66 2001.
Arpit Gupta, Rüdiger Birkner, Marco Canini, Nick Feamster, Chris Mac-Stoker, and Walter Willinger. Network monitoring as streaming analytics problem. In Proceedings of the 15th ACM workshop on hot topics networks, pages 106-112, 2016.
Nikita Ivkin, Zhuolong Yu. Vladimir Braverman, and Xin Jin. Qpipe: Quantiles sketch fully in the data plane. In Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies, pages 285-291, 2019.
Rajesh Jayaram and David Woodruff. Data streams with bounded deletions. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAN Symposium on Principles of Database Systems, pages 341-354, 2018
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling shuffling. In International Conference on Machine Learning, pages 5213-5225. PMLR, 2021.
Zohar Karnin, Kevin Lang, and Edo Liberty. Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs), pages 71-78. IEEE, 2016.
Kasper Green Larsen, Rasmus Pagh, and Jakub Tětek. Countsketches, feature hashing and the median of three. In International Conference on Machine Learning, pages 601 1-6000. PMLR, 2021.
Tian Li, Zaoxing Liu, Vyas Sekar, and Virginia Smith. Privacy for free: Communication -iffiiiitiinnefiiieintt learning with differential privacy using sketches. arXiv preprint urXiv:191..00979 2019.
Luca Melis, George Danezis, and Emiliano De Cristofaro. Efficient private statistics with succinet sketches. arXiv preprint arXiv: 1500. 000 10, 2015.
Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. Efficient computation of frequent and top-k elements in data streams. In International conference database theory, pages 398 -122. Springer, 2005.
Gregory T Minton and Eric Price. Improved concentration bounds for count-sketch. In Proceedings of the twenty-fitth annual ACM-SIAM symposium on Discrete algorithms, pages 6699688.. SIAM, 2014.
11

---

arXiv preprint Darakhshan Mir, Shan Muthukrishnan, Aleksandar Nikolov, and Rebecca N Wright. Pan-private algorithms via statistics on sketches. In Proceedings of the thirtieth ACM SIGMOD-SIGACT: SIGART symposium on Principles of database systems, pages 37-48, 2011.
Jayadev Misra and David Gries. Finding repeated elements. Science of computer programming, 2(2):
143-152, 1982.
J lan Munro and Mike S Paterson. Selection and sorting with limited storage. Theoretical computer science, 12(3):315-324 1980.
Rasmus Pagh and Nina Mesing Stausholm. Efficient differentially private 10 linear sketching. In 24rd International Conference on Database Theory, 2021.
Rasmus Pagh and Mikkel Thorup. Improved utility analysis of private countsketch. 2022.
Dan Qiao and Yu-Xiang Wang. Near-optimal differentially private reinforcement learning. arXiv preprint #rXiv:22/2.0468// 2022a.
Dan Qiao and Yu-Xiam Xiang Wang. Offline reinforcement learning with differential privacy, arXiv preprint arXiv:2206. 200000 2022b.
Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficien reinforcement learning with loglog(T) switching cost. In Proceedings of the 39th International Conference on Machine Learning, pages 18031-18061. PMLR, 2022.
Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. Fetchsgd: Communication-efficeenn federated learning with sketching. In International Conference on Machine Learning, pages 8253 8265. PMLR, 2020.
Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri. Medians and beyond: new aggregation techniques for sensor networks. In Proceedings of the 2nd international conference on Embedded networked sensor systems, pages 239-249, 2004.
Adam Smith, Shuang Song, and Abhradeep Guha Thakurta. The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space. Advances in Neural Information Processing Systems, 33: 1911911999772 2020.
Nina Mesing Stausholm. Improved differentially private euclidean distance approximation. In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGA Symposium Principles of Database Systems, pages 42-56, 2021.
Christos Tzamos, Emmanouil- Vasileios Vlatakis Saaakii-Gaarakkuunis,, and Ilias Zadik. Optimal private median estimation under minimal distributional assumptions. Advances in Neural Information Processing Systems, 33:3301-3311, 2020.
Jalaj Upadhyay. Differentially private linear algebra in the streaming model. arXiv: arXiv:1409.520 1409.5414, 2014.
Salil Vadhan. The complexity of differential privacy. In Tatorials on the Foundations of Cryptography, pages 347-450. Springer, 2017.
Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions Information Theory, 60(7):3777-3800, 2014.
Lu Wang, Ge Luo, Ke Yi, and Graham Cormode. Quantiles over data streams: an experimental study, In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pages 737-748, 2013.
Victor Zakhary, Lawrence Lim, Divyakant Agrawal, and Amr El Abbadi. Cot: Decentralized elastic caches for cloud environments. arXiv preprint arXiv:2006.00 08067, 2020.
Fuheng Zhao, Sujaya Maiyya, Ryan Wiener, Divyakant Agrawal, and Amr El Abbadi. Kll+ ap- proximate quantile sketches over dynamic datasets. Proc. VLDB Endow., 1257):125-1 mar 2021. ISSN 2150-8097. doi: 10. 10.14778//34509903455099 URL https:t//tt...... http:///o..oo////////// org/ /00 14778/ 3450980. 3450990.
12

---

Fuheng Zhao, Divyakant Agrawal, Amr EI Abbadi, and Ahmed Metwally. Spacesavingt: An optimal algorithm for frequency estimation and frequent items the bounded-deletion model. Proc. VLDB Endow. 15(6):1215-122) feb 2022. ISSN 21 215008097. doi: 10.14778/3514066 https://doll org/10. 10. 04777/3554400 1000061..5114000 3514068.
URL
George Kingsley Zipf. Human behavior and the principle of least effort: An introduction to human ecology. Ravenio Books, 2016.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the pa- per's contributions and scope? [Yes] Claims in abstract and introduction reflect our contributions.
(b) Did you describe the limitations of your work? [Yes] In Theorem 3.1, the private Count-
Min frequeney estimation's 's additional error has dependency of V log 1 keep the property of not underestimating item's frequency. Assume database size is fixed, decreasing gamma will increase the average error. Note the error is independent from the database size, and when database size grows, the error will become negligible.
y in order to
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Apply our proposed algorithms to current systems will protect user privacy.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We put some proves in Appendix A due to space limits
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or as a URL)? [Yes] We will provide an url to our Github Repo once the paper is accepted.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] We provide the parameters used for the experiments.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A] We didn't 't use random seed
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] we didn't use any external resources beside a macbook pro.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We did not use existing assets.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was 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. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] We did not use crowdsourcing or conducted research with human subjects.
13

---

(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]
14


Reviews:
[{"review_id": "nW_3pK5J5JB", "reviewer": "Reviewer_fzjL", "summary": "The paper present differentially private variants of linear sketches such as Count Min and Count Median sketches. The differential privacy guarantees are provided using a recent notion of differential privacy: zDP  [Dwork and Rothblum, 2016, Bun and Steinke, 2016]. The only change from vanilla sketches is the initialization provided in algorithm 3, which when combined with the update (Algorithm 1) and query (Algorithm 2) components of Count Min and Count median sketches leads to the differentially private versions of these sketches. The initialization itself adds Gaussian noise to each array item. Any other noise source satisfying zCDP would also suffice. The analysis of the algorithms directly follows by combining the analysis for vanilla sketches with the recent differentially privacy results.\n\n Building on the Differentially Private Count Median Sketch, the authors propose a Dyadic Count-Median sketch that can estimate all the quantiles simultaneously while ensuring differential privacy. The experimental evaluations validate the practicality of the algorithms.\n\nOverall, while the algorithms presented, as well as their analysis, are not novel. The paper does a good job of reviewing the literature in two disjoint fields and providing a comprehensive set of differential private linear sketches, which need to be documented. Therefore, I recommend acceptance. ", "questions": "Can the authors comment on the lower bounds for the various problems considered? If not, can the authors comment on the challenges in coming up with such a result?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n1) The authors systematically study the literature on linear sketches and differential privacy and provide a comprehensive set of differentially private linear sketches\n 2) The paper is well written and easy to follow.\n3) However, there isn't any novelty either algorithmically or in the theoretical analysis of the algorithms: The only real change from an algorithm standpoint is the initialization phase of the linear sketches. The proofs follow by bootstrapping the standard proofs for linear sketches and using the recent differentially privacy results.\n4) This would be a solid paper had the authors presented some sort of impossibility result for frequency estimation under privacy guarantees. \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": "dpxHrDpohhv", "reviewer": "Reviewer_a3xv", "summary": "The paper shows that the Count (Median) Sketch and the Count Min sketch for frequency estimation can be made differentially private by adding a small amount of Gaussian noise. The sketches are then used for quantile estimation, similarly to how the non-private sketches are used for the same problem.", "questions": "I would suggest giving either an improved analysis or a proof that your analysis is tight for either sketch. Alternatively, a less immediate application of the private sketches can also strengthen your paper.", "limitations": "No comment.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "For better or worse, this is a very straightforward application of textbook differential privacy techniques. The small dimension of the sketch leads to a good bound on the ell_2 sensitivity, which allows adding a small amount of Gaussian noise to achieve privacy. This is a useful tool to have, but, in my opinion, a straightforward application of the Gaussian noise mechanism to a well-known sketch is not enough to meet the bar for publication.  The paper needs either a tighter analysis (note that a recent preprint by Pagh and Thorup claims a tighter bound on the error of the Count Sketch with added Gaussian noise), or a more impressive application.", "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": "K-WjGG3orSM", "reviewer": "Reviewer_FaJp", "summary": "The paper considers differential privacy for some standard sketches, determining their differential privacy bounds under Gaussian noise.  ", "questions": "I believe there are other similar (contemporaneous?) works on the arxiv.  See https://arxiv.org/abs/2205.08397.\nPerhaps you can compare with this paper.  ", "limitations": "n/a\n", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nNatural problem from differential privacy.\nAnalysis + experiments.  \nGood set of experimental results.\n\nWeaknesses:\nAnalysis is straightforward.\nDoesn't get same one-sided error bounds just a \"with high probability\" variant.\n\nOriginality:  I'm concerned about the originality.  In some sense, similar results (with perhaps weaker or incomparable results?, it's hard to tell) appear in other papers, such as \nMir, D., Muthukrishnan, S., Nikolov, A., and Wright, R. N. Pan-private algorithms via statistics on\nsketches. In Proceedings of Symposium on Principles of database systems (PODS), pp. 37–48,\n2011. (which is cited in this paper)\nand\nMelis, L., Danezis, G., and Cristofaro, E. D. Efficient private statistics with succinct sketches. In\nAnnual Network and Distributed System Security Symposium (NDSS). The Internet Society, 2016. (which is not).  \nThe results seem to follow just by applying the standard Gaussian mechanism and then applying composition theorems from other work.  (Lemmas 2.7-2.9).  Perhaps nobody has written this down before, but I have trouble believing it was not known as it seems a straighforward composition.  \n\nQuality:  Given the originality concerns above, the quality is OK.\n\nClarity:  The writing is generally good and clear.\n\nSignificance:  See the originality issues above.", "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": "DkljMH6yZRH", "reviewer": "Reviewer_kKXq", "summary": "This paper demonstrates that linear sketches can be made differentially private by adding a small amount of Gaussian noise at initialization. Experimental results on Zipf and the real CAIDA dataset show that the utility is less influenced by this modification.", "questions": "W1 and W3.", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Trendy topic\n- Well-organized paper\n- The improvement is simple yet effective\n\nWeaknesses:\n\n- The assumption limits the application scenarios\n- Lack of analysis\n\nDetailed Weakness Comments:\n\nThis paper points out that linear sketches can be made differentially private and provide useful information while maintaining their original properties. Specifically, contrary to the standard operation that initializes each counter with 0, the authors initialize each counter with a noise sampled from certain Gaussian distribution, whose parameters are determined by the accuracy parameter, failure probability, and budget for zCDP.\n\nI like this idea overall, though this modification is small, the authors prove that this could make the linear sketches differentially private. However, this paper also has some flaws, such as the assumption, and lacking analysis of the case where the adversary is actively involved. I list my concrete concerns in the following:\n\nW1. The assumption limits the application scenarios. In section 2.2, the authors briefly introduce linear sketches, they assume that item x has value v equals either -1 or 1, which limits the application scenarios of linear sketches. However, from algorithms 1 and 2, I didn’t see any operation that relies on this assumption. Therefore, I would like to know whether this is a redundant assumption, or if this assumption is required to make sure the private linear sketches satisfy differential privacy. If this assumption is only needed to achieve the DP guarantee, I think the trade-off between privacy and applicability should be discussed.\n\nW2. It would be nice if the authors could provide a brief illustration about why vanilla linear sketch does not hold differential privacy property, which may make the improvement intuition clearer in this paper.\n\nW3. Lack of analysis. The key idea to making existing linear sketches private is to initialize counters with random noise, as shown In algorithm 3. And the authors provide a series of analysis to prove that the modified scheme satisfies the DP definition, which is nice. However, I wonder whether these properties still hold when the private linear sketches are attacked. For example, the authors initialize counter C with E plus noise sampled from a gaussian distribution (for count-min case), yet, the attacker could eliminate this E in the initialization step, since E is determined once the accuracy parameter, failure probability, and budget for zCDP are fixed. I would like to know would the scheme still satisfy the DP requirement?  \n\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": {}}]

Author rebuttal:

Decision: Accept