Differentially Private Approximate Near Neighbor Counting in High Dimensions
Authors: Alexandr Andoni
Piotr Indyk
Sepideh Mahabadi
Shyam Narayanan
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Differential Privacy
Near Neighbor Search
Locality Sensitive Hashing
Data Structures
Range Query
TL;DR: We provide the first differentially private approximate near neighbor data structure with low error even for high-dimensional datasets.

Abstract: Range counting (e.g., counting the number of data points falling into a given query ball) under differential privacy has been studied extensively. However, the current algorithms for this problem are subject to the following dichotomy. One class of algorithms suffers from an additive error that is a fixed polynomial in the number of points. Another class of algorithms allows for polylogarithmic additive error, but the error grows exponentially in the dimension. To achieve the latter, the problem is relaxed to allow a “fuzzy” definition of the range boundary, e.g., a count of the points in a ball of radius $r$ might also include points in a ball of radius $cr$ for some $c>1$. In this paper we present an efficient algorithm that offers a sweet spot between these two classes. The algorithm has an additive error that is an arbitrary small power of the data set size, depending on how fuzzy the range boundary is, as well as a small ($1+o(1)$) multiplicative error. Crucially, the amount of noise added has no dependence on the dimension. Our algorithm introduces a variant of Locality-Sensitive Hashing, utilizing it in a novel manner.

Differentially Private Approximate Near Neighbor Counting in High Dimensions
Alexandr Andoni Columbia University
Piotr Indyk MIT indyk@mit.
Sepideh Mahabadi Microsoft Research
andoni@cs. cow.mbia.....o.oooooooc.m.m... edu
smahabadi @mi crosoft.
Shyam Narayanan MIT
shyamen@mit.co edu
Abstract
Range counting (c.g., counting the number data points falling into given query ball) under differential privacy has been studied extensively. However, the current algorithms for this problem are subject to the following dichotomy. One class algorithms suffers from additive error that is fixed polynomial in the number of points. Another class of algorithms allows for polylogarithmic additive error, but the error grows exponentially in the dimension. To achieve the latter, the problem is relaxed to allow a "fuzzy" definition of the range boundary, e.g., a count of the points in ball of radius might also include points in ball of radius or for some e > 1. In this paper we present an efficient algorithm that offers a sweet spot between these two classes. The algorithm has an additive error that is an arbitrary small power of the data set size, depending on how fuzzy the range boundary is, as well small (1 o(1)) multiplicative error. Crucially, the amount of noise added has no dependence on the dimension. Our algorithm introduces a variant of -eealty-Sensiivvee Hashing, utilizing it in a novel manner.
Introduction
Differential Privacy (DP) [DMNS06, D DMNS16] is widely used tool for preserving the privacy of sensitive personal information. It allows data structure to provide approximate answers queries about the data holds, while ensuring that the removal addition of single database entry does not significantly affect the outcome of any analysis. The latter guarantee is accomplishe by adding some amount of noise the answers, that the data cannot be "reverse-engineeree" from the answers to the queries. See Definition 2. for the formal setup. The notion has been deployed in many important scenarios in industry [DKY17, EPK14, BEM 17, Shal4, G+ 16] as well the U.S. census [Abo18].
One of the key data analysis problems studied under differential privacy is range counting. Here, the goal is to construct a data structure that answers queries about the total number of data items in a database satisfying given property. Formally, given multiset X of elements from universe U, the goal of range counting queries to report the number of points within given range Q E Q from prespecified class of query ranges Q. For example, this could correspond retrieving the number of users in particular geographic location, or number of patients with given symptoms.
Differentially private range counting has been studied extensively, for many classes of queries. For example, the case of Q 24 i.e., when the queries ask for the number occurrences a given element in the database, this correspond the well-known histogram problem [HKR12, EPK14).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

May be included
Must be included
cr
Cannot be included
Figure 1: An illustration of approximate near neighbor query, with parameters and r.
More generally, a large body of research has focused on the case where universe U is the d-dimensional space Rd (or its discretization), and Q consists of natural geometric objects, like rectangles, half- planes or balls. The seminal work of [MN12] demonstrated a strong relationship between the amount of additive noise necessary guarantee the privacy. and the discrepancy of the space of queries Q. Unfortunately, except for a few classes of queries such as axis uxis-parallel rectangles, most natural geometric objects have discrepancy that polynomial in the number of data points n. This means that, in order to guarantee privacy, it is necessary to distort the counts by an additive term O(n²), for a fixed constant p > that depends on Q.
To alleviate this issue, [HY21] introduced differentially private data structures for approximate range queries. For simplicity, consider in the rest of the paper. We assume that U is metric space equipped with a distance function dist. For radius parameter r, we define the query family Q {B(q.r) r): q E UJ, where B(g.r) = {p E U: dist(p, q) S r} is the ball of radius r around q. In other words, in the exact problem, the goal is to count the number of data points that are "near" the given query point. In turn, the approximate problem is parameterized by approximation factor e 2 1, and the algorithm is allowed to report any number between X B(g. r) and XX n B(g,er) Figure illustrates this notion. We will refer to the approximate version as the (c,r)- r) neighbor counting problem.
recap their notion for the special case of ball queries that
The main result of [HY21] shows that, if one allows approximate queries as defined above, then one can construct a data structure that guarantees privacy while adding much less noise. Specifically, if u [u] (i.e., the universe is the discrete d-dimensional space) for some fixed d ((1) and dist(p. q) = lp olls for some la norm, then their algorithm achieves privacy while adding noise of magnitude roughly (O(1/a))² polylog(1z + n)) where 0 < a < is a constant that depends on <> 1. This guarantees that the noise amount only polylogarithmic,
long the dimension d is constant. However, the exponential dependence the noise bound on the dimension precludes the applicability of this algorithm to the common case of high-dimensional data sets.
Our contribution Our main result is an efficient data structure that can approximate the number of near neighbors to any query point over Fuclidean (f2) space, with differential privacy (see Preliminaries for the formal of definition of privacy). Specifically, for any fixed radius r, and any series of query points g, the data structure can privately answer (c, -neea neighbor counting queries, where we are allowed small additive error (nº for small constant p) and multiplicative error 1 1 o(1). Let Bp(g,r) denote the L, ball of radius around q.
Theorem 1.1. Fix radius 0 and constant integer a and dimension d, there exists a differentially private algorithm that, on a dataset X Rdd of most points, creates data structure that answer m (ton-adaptive) queries and that satisfies the following properties.
1, and privacy parameters > E, > O. For any
1. (Privacy) The full output of the algorithm is (c, diffferrentll private.
2. (Accuracy) With high probability, for every non-adaptive query q, the output ans(g) is between
(1 (1-o (x- Belg.r) pto(1) log(log m/8) log m
and
(1 + o(1) IX Bz or) + moto(1) log(log m/6) (eg(logm/))
log

---

where
4r [c"+1y=
Oz2).
3. (Runtime) The preprocessing time is O( d log m.), and the expected runtime for answering each query is (nn++ol1) d log m).
The key two features of the above result are as follows. First, the amount of additive noise is controlled by the amount of allowed approximation: the exponent p tends 0 grows large. This makes it possible to trade the "proximity" error с and the "privacy" error n to achieve the best results. Second, the magnitude of added noise does not depend the dimension; in particular, it avoids the exponential dependence of [HY21].
Finally, we remark that our algorithm can be extended to alternative/more general settings:
1. & metric: we considered the balls Bi Bi r) rather than B2(q, r), we can still obtain a similar result, at the cost of having
[c+1y= 4r O This is based on the fact that the E
metric embeds vear-isometrically into the squared metric.
2. Pure differential privacy: We can modify our algorithm to handle pure-DP queries (i.e., when 0), while still having good accuracy. In this case, however, the algorithm, while fast in expectation, has some small probability of being very slow.
3. Large Our results also hold even when 1 S E S no(1)
4. Adaptive queries: Our method also extends to adaptive queries, at the expense of the runtime and additive error multiplying by a factor of poly(d log R/r), where R is some promised bound on the radius of the dataset.
5. k-NN queries: Finally, we note that using similar approach to that of [HY21], one can get data structure for finding approximation to the distance of the query to its k-nearest neighbor. However, as opposed to [HY21], our data structure works only for a fixed value of and thus needs to build separate data structures for various choices of r leading to worse privacy guarantees which depend on the aspect ratio.
We discuss extensions 1-4 more formally in Appendix C.
A natural question is whether the tradeoff between approximation ratio e and additive error nf is necessary, or whether one can obtain e = ((1) and p to be an arbitrarily small constant. While we are unable prove such a lower bound in the Euclidean setting, we show that under the closely related & norm for approximation ratio 3 o(1), one must have additive enror of n ((1)
Theorem 1.2. For sufficiently large there exists d = C' log n for a large constant C, fixed constants 1 >> e, ô, p > and n query points = : 9n3. with the following property. For any (arbitrarily small) >> 0 and any differentially private algorithm A that acts on dataset X Rd of al most n. points, and outputs {ans(g) (a(g)))e00 19E must have
2
P(Vg E Q, |Bx 0.5)l n² S (ans(g)= S BB 1.5 - a)l - n²)
3
Theorem 1.2 provides some evidence that a tradeoff may be necessary even in the fg case; proving such result is an interesting open problem. We defer the proof of Theorem 1.2 to Appendix B.
Overview of the techniques. Our high-level approach similar to that of the low-dimensional approximate range query data structure of [HY21], and consists of the following steps. First, we design a partition of Rd and count the number of points that fall into each cell the partition. Then add Laplace noise each cell to ensure the privacy of the counts. Finally, for each query q, approximate the ball B(g, r) using the cells in the partition, and report the sum the (noisy) counts of the approximating cells.
However, applying this approach as described requires using an exponential (in d) number of partition cells to approximate query ball B(g. r), leading to the exponential error bound. To overcome this issue, we resort to randomized space partitions obtained using Locality-Sensitio techniques [IM98]. These partitions have the property that, for any two points p and q, the probability that both of them belong the same partition cell depends on the distance ||p gl|2- As shown in [Pan06] in the context of (non-pun moin-rrivate) approximate near neighbor search, enumerating a bounded
Hashing (LSH)
3

---

number (n²) of cells in such partition makes it possible to report each data point from the range B(q.r) r) with probability at least 1/poly(log n.). To amplity the probability of correctness, the process is repeated (ppoly log n) times, using different random partition in each repetition.
Unfortunately, the aforementioned approach does not appear yield an efficient algorithm for approximately counting the number of points in Big, r). The main issue is that, as indicated above, when enumerating the n² cells corresponding a query's ball, we are guaranteed to include only 1 1/poly (log(((o)))) n) fraction of points, leading to a large approximation factor. The standard way to deal with this- - using multiple partitions - yields inconsistent counts which are difficult to aggregate. A number of follow-up works showed improved bounds on exponent p. but all of them similarly have a guarantee of identifying only a S 1/poly(log n) fraction of points [LJW 07, A106, Kap15, Chr17. 17, ALRW17J. To overcome these obstacles, we show how we can adapt the algorithm from [ALRW]] 17], which yield an approximate near neighbor data structure with the best known tradeoff between space and time. However, their randomized algorithm does not yield partitions (technically, they construct so-called locality-sensitive filters, which are not partitions).
Our main technical contribution is two-fold. First, we show it is possible to "force" the algorithm of [ALRW17] to construct proper partitions. The quality of those partitions is comparable to the original structures, at the price of a more involved analysis. We then use those partitions to compute the counts and approximate the query ball as outlined at the beginning of this section. Second, we show that it is also possible to modify the algorithm so that the probability of including each qualifying point into the count is at least o(1). This is of separate interest, as this yields the most efficient algorithm for approximate nearest neighbor search with space (nd)), improving over [Kap15].
1.1 Related work
The problem of range counting when the query class Q is arbitrary, can be solved with an optimal error bound of vni poly(1/a log 1 [HR 10]. In the setting of approximate near-neighbor queries, the size of Q and U/ can be thought of as at most exponential in the dimension d, by using a standard e-net technique. Hence, their error is in fact smaller than ours when
402
1.4 or equivalently,
when e S v2. However, whenever approximation of c 1 /2 is acceptable, our error is smaller than [HR10]. Moreover, our approach is computationally efficient, whereas their method has runtime linear in the size of U, which very inefficient.
When the query class is restricted to points in 24 i.e., histogram queries, then the best achievable When the points are in 1-dimensional Euclidean space taking values in [u]. and Q is a set of intervals, [DNPR10] got an (c, DDD algorithm with error O log!.6 1.5 u) and lower bound of 22 log ). When resorting to (e, dD-DP, [BNSV15] showed an algorithm with error 2(1+o(1)) log" loog(1 (1/8)/ and lower bound of 22og u log(1/8)/e for e-nn/ log" < 8 < 1/re². The problem for the axis-parallel rectangles have been further studied [CSSI1, DNRR15] where polylogarithmic error bounds were obtained.
error is O min(log (24,, [ad
More generally, [MN12, NTZ13] showed an equivalence between the error and the discrepancy of the range space Q. Given that the discrepancy of many natural range spaces such as half-spaces, simplices, and spheres is (a()) where (d) [1/4, /, 1/2] is constant depending on [Mat99], rules out such polylogarithmic error for these range spaces. For non-convex ranges, the discrepancy
already becomes /ni reaching the threshold for arbitrary query ranges.
There are number of papers based on space decompositions that provide a DP data structure for range counting that perform relatively well in practice [CPS+ + 12, HRMS09, LHMW14, QYL13a, QYL13b, XWG10, 2XX16] but perform poorly on high-discrepancy point sets.
Finally, we note that several prior works used LSH for differentially private kernel estimation (CS20, WNM23). However, those works do not seem to be applicable to ball range queries, which correspond to uniform kernels.

---

2 Preliminaries
Range Counting: In the range counting problems, given point set X U, where 4/ is universe, the goal is to construct a differentially private data structure that for any query Q S UI from a certain query family 2, one compute IQ n
Here we focus on Near Neighbor counting queries in high dimensions. In particular is metric space equipped with a distance function dist. Given prespecified radius parameter the query family @ = r): g E W} where (gg,r) = {o E W: dist 9) S r is the ball radius r around q. In other words, in this problem the goal is count the number of neighbors of given query point.
Similar to the work of [HY21], we consider the approximate variant of the problem where the points within distance and or of the query can either counted or discarded. In particular for an approximation factor e 2 1, any number between X n B(g, r)] and |X n B(g, er) is valid.
Differential Privacy (DP): For two datasets X and X', we use X X' mean that they neighboring datasets, i.e., one of them can be obtained from the other by an addition of a single element (in our problem point).
Definition 2.1. (Differential Privacy [DR* 14]). For e > 0, 5 2 0, a randomized algorithm A is (c, 8) difffrrentially private ((c, -DPP) for any two datasets X ~ X', and any possible outcome of the algorithum S "[annge(A), P (A(X) E S] S . PPA((') E S] + When 0, the algorithm is said to have pure differential privacy.
The sensitivity of function is defined be A x (f(X) f(X').
We use Lap(A) A) denote the Laplace distribution with parameter À with PDF TP [Z which has mean and variance X We also use TLap(A, e, to denote the Truncated Laplace dis- tribution with PDF proportional to e =|/c/A on the region [-B, B), where B
2xe e la/AA -1/A/
log (1 c(=1
Lemma 2.2 ((Truncated) Laplace Mechanism [DR + 14, GDGK20J). Given numeric function that takes a datasel X as the input, and has sensitivity A, the mechanism that outputs f(X) (X)= + 7 where 7. ~ Lap(A/e) is O)-P.. In addition, e, 2: f(X) Z, where Z TTap(A, e, 6), is (e, -D. Moreover, the Truncated Laplace mechanism is always accurate up to error B.
Upper Bound
In this section, we describe the algorithm and perform the majority of the analysis for Theorem 1.1. We defer certain parts to Appendix A, and finish the proof there.
3.1 Setup
The algorithm we develop is inspired by the iata-independent approximate nearest neighbor algorithm in [ALRW17]. We will use similar notation their paper well.
Define 5d-1 be the (d - 1)ddieensia unit sphere in Rd. For any parameter r E (0, 2), let a(r) = and ((r)= /1 2 2 be the cosine and the sine, respectively, of the angle between 17 define
two points in 5d-1 of distance For any parameter
F(r) = IP
Kg. u) 2 7),
g=~((o.1)
where u E Sdd is an arbitrary point on the unit sphere. Note that F() independent of by the spherical symmetry of Gaussians, and in fact equals the probability that univariate standard Normal exceeds r7. Next, for any parameters E (0, 2) and ng. 7u E R, we define
Kg q) ml and (g. p) 2 nu). G(r, Ng. Th) g~~((o,1)
where p, E 5 are points that have distance exactly r between them. As with F, G has no dependence the specific points p.q but only on the distance r = ||p 4ll2 between them. Note also that G(r, Dg: Nh)) is non-increasing in even if 7) or T) is negative.
Next, we note the following well-known bounds for F.
5

---

Algorithm Data Structure
1: Input: data X of size at most 7t, privacy parameters ō, parameters T, K, Ta.
2: Output: data structure D = (T: [go JEET (oa
3: Create T: Tarry tree of depth K, with root Vroot-
4: for each node E do
5: e (O) {Random d-dimensional Gaussian)
6: Co 0. [Counts number of points assigned to each node]
7:
for point E X do
8:
V. - Uroot-
9:
for l to K- --] do
10:
(v) then
11:
BREAK (Break out of "for / = 0 to K loop (y failed to map a child))
for to do
13:
U2 <- ith child of
14:
(g...P) p) 2 7a then
15:
Co. Cv. +1
16:
V f 222
17:
BREAK (Break out of "for i 1 to T" loop)
18:
for each leaf node v E do
19:
Co + TLap(1, 21 2)
if cf < 2 log 1 + 1//2
20:
then
21:
Co 00 0
Proposition 3.1. For 77 1.
1 Ω
e 1212 & F(1)) 15-12
In addition, as + 0o, F(n) o(1) 12
3.2 Algorithm for data on the sphere
We now present an algorithm that obtains the desired privacy and accuracy guarantees, assuming both the data points and query points are on a unit sphere and the radius is not too small. The initial algorithm description will not necessarily run in polynomial time, but we will later describe simple modification make this algorithm efficient. Finally, in Appendix A.2 we will modify the algorithm to work for general and in Euclidean space, rather than just on the unit sphere. This follows from known embedding methods [BRS11], 1], which why we defer the Appendix.
Data Structure: We describe the data structure in words here, provide pseudocode Algorithm 1. Fix K and T' be positive integers, to be set later. We generate data structure, which T-ary tree of depth K. We index the levels as 0, I,..., K, where level 0 is the root and level K consists of the T leaves. For each node v except the root, we generate independent d-dimensional standard Gaussian ~ A I). In addition, we will define two parameters 77 and Mu. to be set later.
The tree nodes at level will partition the unit sphere 5dl-1 into 2 regions, plus an extra "remainder" region of points that are not mapped into any of the 7 regions. At level 0, all points in S are sent to the single region indexed by the root. For any node v in the tree of depth 0 < l $ and with children Vi,.... UK. the region P. is partitioned into P P....... Poy follows. A point p E P. is sent to Po, if i < T' is the smallest index such that (gt, 2 nu Note that some points in P. may not be sent to any of P ........ P For each leaf node v, store approximate count X n P.l + TLap (1, 8), where we added Truncated Laplace noise. If the noised count 6 is too small (at most A log (1 + ا we replace the count G, with 0.
G,
We remark that the partition is technically not a full partition, because some data points may not be sent to any P...

---

Algorithm 2 ANSWER V/. 4, v): Answering query
Input: data structure D (T, fgoLeET, (CeJeteteT) parameter 772 query point q, node v.
2:
if (gu, q) 2 The then
3: if a leaf node then
4: Return Co
5: else
6: ans =
7:
for to do
8:
Us ith child of
9:
ans < ans + ADsWER(D, N7: 9,
10: Return ans
Answering query: We describe the algorithm in words here, provide pseudocode in Algorithm 2. Given a query q, we "send" q to every leaf node v = UK such that the path U/, V2...... UK from the root Vooot satisfies (9e,, 9) Tl for all 1 s S K. Hence, each query 9 will correspond to subset Vg of leaf nodes. The response to the query g will be
Σ Cv. EVV,
To improve the accuracy of the algorithm, we repeat this procedure O(log m)) times if there are m queries, each initialized to (e', 8'DD for e' = (0olggmm m) and 8' = 5/O m)). The overall algorithm will still be (c, 6)-DP, by the well-known Basic Composition theorem [DR+14 14, Corollary 3. 3.. For each query, output the median response of the individual data structure responses. In the analysis, we will ignore this amplification procedure, as by Chernoff bound it suffices to show that each individual query is answered accurately with least 2/3 probability.
3.3 Analysis
Privacy: The analysis privacy is quite simple. First, note that the responses to all of the queries do not depend the data direetly, but only depend the counts {c.). If we let 2, : [X n P. and č, (X) = | P TTapp(1, e, 6), then note that ey (X) is entirely dependent on (,(X) Hence, it suffices to show the following.
Lemma 3.2 (Privacy). The set (Cx(X)) ET is (e, 6)-DP with respect to the data X. Hence, the entire algorithm is also (c, 8)DD, even if we have an arbitrary number of queries.
Proof. Consider two adjacent datasets X, X', i.e., where we either removed added single data point from to obtain X'. Note that the construction partitioning
the dataset into leaves is not dependent on the data, but merely on random vectors Je over all nodes Therefore, if we condition on the partitioning of the entire space, the values (X) = [X n Pol and č, (X') = |X' n P.l are the same for all but most one leaf v, which changes by at most 1. The sensitivity of each such ê (X) at most 1, which means that we have (c, 8) --rivacyy loss from č (X). Because this happens for single choice of v, have (c, 6) -prrivcy loss in total.
We will only consider the accuracy with respect to a fixed query g and a single copy of the data structure, and show accuracy holds in expectation. For of m queries, since we repeat this data structure Ollog m.) times and use the median estimate, a Chernoff bound implies all queries will be answered accurately with at least 99% probability.
Accuracy:
We prove the following lemma to bound accuracy.
Lemma 3.3 (Accuracy, assuming parameters are set properly). Suppose the following hold, for some fixed choice of parameters e, p, K, T, Ng. Nu:
1. (T F S + (Additive enor due to Laplace noise).
2. e -TF(m)) = o(1/K), and G(rgeehu) F(T.)
= 1 ((1/K). (Multiplicative error due to not
including points within of q).

---

3. (Clommnol)) S In-1+p+o(), (Additive envor due including points not within of q).
Then, if ons is the response when querying fixed a on dataset X, with probability at least 2/3. ans between
(1 .log neto(())
1
(1-) (2 (1-oo))-iinBB((ar)---
and
= (=- g noto(i)
1
(1+ |X B2(q: cr)l +
In other words, we solve the (c, - neighbor counting problem with probability at least 2/3, up to multiplicative = o(1 factor and an additive O (²= log -n(to))) factor.
In Subsection 3.4, we will show how to set T, K, n4: T/ so that the three conditions above hold.
Proof. Our error comes from two sources. The first is the Truncated Laplace noise that we add, which we add in IV. locations to compute the answer to query q. This adds an additive noise of at most O log l) in expectation, as |c. - XX n P.ll s O -log })) with probability 1.
To bound V/ note that it simply equals the sum of the probabilities that q E P. for each leaf v, which is 7 times the probability that P. for fixed This probability is just F(n,)* since each Gaussian along the path to e is independent. Hence, the first source error has magnitude at most O ( log } (T *) S (
log n)to(1)) in expectation.
Hence, if we let ans be the response we would have received if we did not add Laplace noise (i.e., if we used & instead of c.),, then Eijans anal] I ( -log & n)+o(1)), so |ans ans <
O ( log } nato(l)) with probability at least 0.9 by Markov's inequality.
The second source of error is that @ns counts the number of points in X that are in P. for some v E V,, whereas we actually want to count the number of points X that are within distance r of (tolerating the inclusion of points up to distance of q). Hence, we need to make sure of two things, corresponding to not underestimating or overestimating, respectively:
1. Most points in X within distance r of are mapped to some P. where v E Vg-
2. Few points in X that are not within distance cr of q are mapped to some P. where v E Vg-
This way. we will show that with high probability,
(1 - (1-0(1))-1x B2(g.r) ans < IXnBBllgee + O (netoci)).
which is sufficient.
For any point of distance from g. we compute the probability that E Pd for some v E Vg- Let's start by assuming K 1, i.e., we have a depth-1 tree with leaves labeled 1, ..... T. In this case there are two possibilities for failure: either is not mapped to any P; for < sist T, or prpie is mapped to some P: but g is not sent there. Suppose p is mapped
P1: this means (g1. p) 2 nu-
Conditioned on this event, the probability that (g1. 9) 2 n4 is precisely P(gr, g) 2 (gl. 2 na) P(a. 222 2nw.
G(s.m.-n..) Suppose p is mapped to P, for i 2 2. Then, the probability F(n.)
P((s).)) 2nd]
that (g:, 4) 2 Mg is Pkg. q) 2 ng.(...) 2 Tu, (9), p) < nu Mu < i]. But even if q are fixed, then are independent of ((g, (g..9)). Hence, we may remove the
the values of (g,.P) p) for j
conditioning on (0).P) < Vj < to again say that the conditional probability is G(a.me.Ta))
Pina) Hence, the probability that p E P. for e Vg. conditioned on p being in some P., is Gla.Ma-Nuu) The F(m))
probability that s E P. for any is (1 - F( so the overall probability that p E P, for v E Vg- for K =1,1 is
(1- (1- (I-(1-F(m)))))) G(s, Mg: nu) F(1)))
Note that 1 - e TT((na) <1 -1 (1- =((n)) < 1.
8

---

For general depths, note that the Gaussians selected at each level are independent of the previous levels. Hence, the success probability simply raises the power of K, or equals
- (1-(1F(())))) K (GlssTe
ng: F(TT)
K
Note that 2 (1-E (Ptnn) 2 1- K. --TF(n)) Hence, the probability that a point p of distance
from q is mapped to some P. where Vg is between (1 K.e e TF(aa)) (G(.))a)))) G(s.Ng=Nia) F(n.)
(
and
F(
Because G(s, 7g. 7a) is an increasing function in s, the probability at any point of distance $
from q is not included in the count ans is at least (1 (1- K eee-eeFFet -F()))) [GrrsgooTio)
(())
F(nu)
as we are assuming that e -T- o(1/K) K) and G(r-ngauu) = - o(1/K). Thus, by Markov's inequality, with probability at least 0.9, ans 2 (1 - ((1) |X n B2(q, r)l. Next, the probability
F(h..)
that any point of distance 2 from g is included in the count ans is at most Gler-Mg-
F(
which we assume is most -l1+++())) Because there are at most n points, by Markov's inequality, ams I X n B2(g, cr) n1+((1) with probability at least 0.9.
Li
Runtime: While we have written the algorithm to create a sized tree, we can speed up the implementation by only including the necessary parts of the data structure.
We can bound the runtime as follows. Naively, for preprocessing. it takes space and time O(TK d) to construct the tree and generate and store the Gaussians. Next, for each point if p E Po, it takes up to O d) time to determine which child of v is that p will be sent to. Since p is sent to only one node in each partition, this takes total time O(K- - d) per point, which means O(n K T d) total time to partition the points in X. To improve the preprocessing time, we do not generate the full tree: rather, only generate node of the tree (with corresponding Gaussian g.) if we need to check whether some data point E X is sent to the node, which means we can improve the preprocessing time to On K T d), without the extra term of O d). Note that if some leaf node e was not created in our modified implementation, then no point would have been sent to some partition piece
Pe, which means X Pal + TLap(1, 2. 2) S 2 log (1 + ='/=-1 +1+++)))
So, we would have set ea to be 0 anyway, which means that this modification does not affect any of the responses to queries.
To answer query q, if g E P. (where is possibly not leaf node) it takes O(T-d) time to determine all of the children of that q will be sent to. In expectation, 9 is sent to (Tn)) nodes at level t, which means at level + 1 we need to check up to (TF()))) T nodes in expectation. (If node is not created in our implementation, we do not have to check it, since we know c. = 0 for any leaf u that is descendant of w.) Therefore, the total time it takes determine all leaf nodes q is sent to, in
expectation, is O d Σk- (TF()))) T = O(TF(())) K K T d). Finally, we can add co over all leaf nodes that q is sent to, which takes an additional (((FF(n))) time in expectation. Hence, we have the following lemma.
Lemma 3.4 (Runtime). The total preprocessing time of the data structure is O(n K-T T d), and the expected time needed to answer each query is (((FF(()) K K-T-
3.4 Parameter Settings and Finishing the Accuracy/Runtine Analysis
In this section, we set parameters properly so that Lemmas 3.3 and 3.4 match the goals of Theorem 1.1. We recall that c 1 is fixed constant representing the approximation ratio. We assume that
d = (logn) and r = θ 1
For fixed and r as set above, we set the parameters as (log (10g
follows:
K := In n.
7/u
Inn
for some constant À = X(c), that we will set later.

---

1/ = a()) 1/2 - 23(r) VIn K. Recall that a(r) = =1 1/2 and B(r) /1-a(r)) T :- 10 (/F(nn).
First, we must show that our parameter choices imply that the algorithm accurate. We prove the following lemma, for which the proof is deferred to Appendix A.
Lemma 3.5 (Aceuracy, completed). For an appropriate choice of X(c) = 2y/e, all three conditions 4.a
24I
Lemma 3.3 hold, with p = +c'+1)² = ( Hence, Lemma 3.3 holds without the conditions, for
46
(c++1)2
Finally, we show that the runtime is good, under our parameter choices.
Lemma 3.6 (Runtime, completed). For the parameters we have defined, assuming O (Togmjizz
the total preprocessing time is n (ool)) d and the expected time to answer each query is nl+o(1)
for p c 1)
4
Proof. The preprocessing time is O( --
- d). We know that T 1n and that F(a.) F( ((n.). e/i//2 < (logn)0() cllma////0 By our settings of = @(llggn) 1)1 and K = v In n, and since À is a constant, this equals (1 m)*(*) n2)1), Hence, 1/ (n)) n1(1), and since K O(ylogn)) the total preprocessing time is n +++(1) d.
The time to answer each query is (T))) K T d). By Lemma 3.5, we know that (T,))) nota(1) Moreover, know that K (logn) 0(1) and we already saw that T= = 10 In (/F(n)) = (1)),, Hence, the time to answer each query is noto(1)
Lemmas 3.2, 3.5, and 3.6 will end up being sufficient to prove Theorem 1.1 if we assume the data lies on d = (log (logn) ( -dm--dimnsi unit sphere, and if r O(log n/) To finish the analysis, we must show that this assumption can be made without loss of generality, which will follow from an embedding argument of [BRS11]. We defer this argument, and the proof of the remainder of Theorem 1.1, to Appendix A.2.
Remark. We note that the data structure can be implemented so that extra space is only O(nd). Instead of generating and storing the Gaussians Iu independently, we note that in each level each group of 7 siblings can reuse exactly the same random set of 7 Gaussians. The analysis goes through mutatis mutandis independence between different branches is not needed.
Pl was supported by the NSF TRIPODS program (award DMSS-022448). Simons Investigator Award, and GIST-MIT Research Collaboration grant.
Acknowledgements:
SN is supported by a NSF Graduate Fellowship (Grant No. 1745302) and a Google PhD Fellowship. AA supported in part by NSF (CCF2008733) and ONR (N00014-22-1-2711)
References
[Abo18] John M Abowd. The us census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2867-2867, 2018.
[A106] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. pages 459-468, 2006.
[ALRW17] Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten. Optimal hashing-based time-space trade-offs for approximate near neighbors. In Philip N. Klein, editor, Proceedings of the Twenty-Fighe Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 47-66. SIAM, 2017.
[BEM+17] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Scefeld.
10

---

Prochlo: Strong privacy for analytics in the crowd. In Proceedings of 26th symposium on operating systems principles, pages 441-459 2017.
[BNSV15] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 634-649, IEEE, 2015.
[BRSI1] Yair Bartal, Ben Recht, and Leonard J. Schulman. Dimensionality reduction: Beyond the linnson-inddestraus.. bound. In Proceedings of the Twenty-Secone Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA). pages 868- 368-887. SIAM, 2011.
[Chr17] Tobias Christiani. A framework for similarity search with space-time tradeoffs using locality-sensitive filtering. In Proceedings of the Twenty-Eighttl Annual ACM-SIAM Symposium on Discrete Algorithms, pages 31-46. SIAM, 2017.
[CLO1] Bernard Chazelle and Alexey Lvov. The discrepancy of boxes in higher dimension. Discret. Comput. Geom., 1194):519-524, 2001.
[CPS+ 12) Graham Cormode, Cecilia Procopiuc, Divesh Srivastava, Entong Shen, and Ting Yu. Dif- ferentially private spatial decompositions. In 2012 IEEE 28th International Conference on Data Engineering, pages 20-31. IEEE, 2012.
[CS20] Benjamin Coleman and Anshumali Shrivastava. A one-pass private sketch for most machine learning tasks. arXiv preprint arXiv:2006.09352, 2020.
[CSS11] T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24, 2011.
[DKM 06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology- EpppologgyEEURORRYYY 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pages 486-503, Springer, 2006.
[DKY17] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. Advances in Neural Information Processing Systems, 30, 2017.
[DMNS06) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryp- tography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[DMNS16] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Journal of Privacy and Confidentialiry, 733):17-1, 2016.
[DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium Theory of computing, pages 715-724, 2010.
[DNRR15] Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N Rothblum. Pure differential pri- vacy for rectangle queries via private partitions. In Advances in 2015: 21 International Conference Information Security, Auckland, New Zealand, November 29-December's 3, 2015, Pro- ceedings, Part II, pages 735-751. Springer, 2015.
the Theory and Application of Cryptology and
[DR 14] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differrntial privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211 1070 2014.
[EPK14] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggre- gatable privacy-preserving ordinal response. Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054-1067, 2014.
11

---

[G 16] Andy Greenberg et al. Apple's "differential privacy" is about collecting your data-but not your data. Wired, June, 13:1, 2016.
[GDGK20] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Tight analysis of privacy and utility tradeoff in approximate differential privacy. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108 of Proceedings of Machine Learning Research, pages 89-99. PMLR, 2020.
[HKRI2] Justin Hsu, Sanjeev Khanna, and Aaron Roth. Distributed private heavy hitters. In Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012. Warwick, UK, July 9-13, 2012, Proceedings, Part I 39, pages 461 461-472. Springer, 2012.
[HR10] Moritz Hardt and Guy N Rothblum. A multiplicative weights mechanism for privacy- preserving data analysis. In 2010 IEEE 51st annual symposium on foundations of computer science, pages 61-70. IEEE, 2010.
[HRMS09) Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan Suciu. Boosting the accuracy of offferentially-privaal histograms through consistency. arXiv preprint arXiv:0904.089 0942, 2009.
[HY21] Ziyue Huang and Ke Yi. Approximate range counting under differential privacy. In 37th International Symposium Computational Geometry (SoCG 2021). Schloss Dagstull-Leibnizzzeennne für Informatik, 2021.
[IM98] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium Theory of computing, pages 604-613, 1998.
[Kap15] Michael Kapralov. Smooth tradeoff's between insert and query complexity in nearest neighbor search. pages 329-342, New York, NY, USA, 2015. ACM.
[LHMW14] Chao Li, Michael Hay, Gerome Miklau, and Yue Wang. A data-and workload-aware algorithm for range queries under differential privacy. arXiv preprint arXiv: wxXiv:1410.0265. 2014.
[LJ Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe Ish: efficient indexing for high-dimensional similarity search. VLDB, 2007.
[LN14] Huy Le Nguyen. Algorithms for high dimensional data. PhD thesis, Princeton University, 2014.
[Ma199] Jifí Matoušek. Geometric discrepancy: An illustrated guide. 1999.
[MN04] Manor Mendel and Assaf Naor. Euclidean quotients of finite metric spaces. Advances in Mathematics, 189(2)4451-44, 2004.
[MN12] S. Muthukrishnan and Aleksandar Nikolov. Optimal private halfspace counting via discrepancy. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC), pages 1285-1292. ACM, 2012.
[NTZ13] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential pri- vacy: the sparse and approximate cases. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 351-360 2013.
[Pan06] Rina Panigrahy. Entropy based nearest neighbor search in high dimensions. In Proceed- ings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 1186-1 100--1995. 2006.
[QYLI3a] Wahbeh Qardaji. Weining Yang, and Ninghui Li. Differentially private grids for geospatial data. In 2013 IEEE 29th international conference on data engineering (ICDE), pages 757-768. IEEE, 2013.
[QYL13b] Wahbeh Qardaji, Weining Yang, and Ninghui Li. Understanding hierarchical methods for differentially private histograms. Proceedings of the VLDB Endowment, 6( 6(14):1954- 1965, 2013.
12

---

[Sha14] Stephen Shankland. How google tricks itself to protect chrome user privacy. CNET, October, 2014.
[Vad17] Salil Vadhan. The complexity of differential privacy, Tutorials on the Foundations of Cryptography Dedicated to Oded Goldreich, pages 347-450, 2017.
[WNM23] Tal Wagner, Yonatan Naamad, and Nina Mishra. Fast private kernel density estimation via locality sensitive quantization. 2023.
[XWG10] Xiaokui Xiao, Guozhang Wang, and Johannes Gehrke. Differential privacy via wavelet transforms. IEEE Transactions on knowledge and data engineering, 1200)11200-1214 2010.
[XXX16] Jun Zhang, Xiaokui Xiao, and Xing Xie. Privtree: A differentially private algorithm for hierarchical decompositions. Proceedings of the 2016 international conference on management of data, pages 155-170, 2016.
13

---

A Omitted Proofs from Section 3
A.1 Completion of Accuracy Analysis
Here, we complete the accuracy analysis by proving Theorem 3.5.
Proof of Theorem 3.5. To bound (T =(,,)) note that (10 In K)*K I n by our setting of VIn n. Therefore, it suffices to show that (F(ng)/ F(Tm)) K I nPto(1). However, by Proposition
3.1, we can upper bound F(ng)/ ((())) S O(h.) e n2//2. But we know that T/u, S (log ()og))0(), which implies that ( S no(2), Hence, it suffices to bound (e(n2- 22/// Indeed, we can write
1i = n/2 - -(a(r) Tha 23(r) vln < (1 - a(r))) nh + 4c(r))(r)) K. 77
< x² Inn
Inn In
41
K
K
< x² Inn
(1 + o(1))
K
Above, the third line follows from the fact that 1 - a(r)² fourth line follows from our definition of K. Therefore,
r² and a(r) ((r) s B()) s r, and the
(T F(a))) S nn(() exp
1
In
(1 -1=
2
K
X²
= =n(()) exp
Inn (1 + +((1))
2
= =220/2))
Next, note that e TF(m)) 10 = K- o(1/K), since K w(1.
G(r.n.ma) Next, we bound G(rsn.nuu) Since G(r, Mg. m7)) Fl 9) 2 My and (g. p) 2 nul for ||p 4|12 = r, F((.))
we can rewrite this as F(h)) = [P( 9) 2 11 Vgl p) 2 nu] for |lp - 4/le = r. Since p, g are unit vectors, we can write q a(r) p + B(r) p', where p' is unit vector orthogonal to p. Hence, if we let Y = (g.p) and = {g. pg), then Y, Z are independent standard Gaussians and our goal is to bound PP(((r) Y + ((r) . 7 2 nY 2 nu]. But, = =a(r) - 7u 2.(rr) vIn K, which means if 2 > -2 then Y 2 the automatically implies a(r) Y + -(r) 2 2 1h- Therefore, our probability is at least (Z > -2vmn 1 IP > 2/ín K) 1 110(1//g) o(1/K),
since P(Z 2 2/1n K)- = O(1K32).
Finally, we must bound (Geerin. K F(
) Note that GlermnnTh.) = P(a. g) 2 nol (g, 2 na for F(mn))
lle - g|l2 = er, which means = a(cr) p + B(er) v/. Again, letting = (g. p) and Z (g,8", wish to bound
G(cr, Nay Ngy nu)
P [a(cr) Y +
-o(or)-+B((rrr B(er) 2 2 a(r) Tu 2,(r)) vIn K Y nm
(1)
F(T,)
We can rewrite this as
(a(r) u(cr)) 1/- - 23(r) vIn K a(er). (Y - -h)) mh) B(cr)
TP
7 >
y > nl
(2)
B(cr)
If we write W = =Y Bue note that the PDF of W is 1 V2x
.e- (W+nu) The probability that W 2 0
between Q 1 /2 and é - /2, which means
(Th um
PPW 2 w/
W W 2 0)
22 / /mm) - n S (1ha) e w 12-22- 5((w) -e nu
14

---

Next, a simple calculation tells us that
1 (er)
(ccr)
1
-1=
3(cr)
or (rr
Cr
and
A/v 2r K(1 + (1))
(a(r) - a(cr)) 9/, - 28(r) v vn K
2
K
B(or)
cr(1 + o(11)
Inn (22-1)A (1 (1
cr(1 + o(1)
In
(c2- 1)A + o(1))
K
2c
Let
B(er)
r(1 + o[]).
Then, we can therefore upper bound (2) as at most
ca((rr)
W
Inn
(c2-1) 1)A (1 (1-
-()())) W 2
P
Z +
(3)
Cr
K
2c
The CDF of W ep' conditioned on W 2 is bounded above by O(cr' mh) e e-or' m < (log n) 0())
SSw where S = c. _. X IIn n/K. addition, we write pz to represent the PDF of (which is a standard Gaussian) and T = /mnn/K (c² 12c/ (1 o(1)). Note that S > T, since it
suffices for c >
2c d²1 (1 + o1)). which is true for any constant c. Then, we have that (3) is at most
2 w W 2 0) pz ( - w)dw < (logn)0()
S.w e -e (T---=>>/2 duo + { e -1f w) / 12 dw -2 12-9/22----10 (1-2-(-TT)---- ww dw
cr
s (logn)00
(
-T 12 m² /2 dw
< (logn) 0(1)
- -
e=2212
(log 0(1) . -T
The third line uses the fact that (S T)w 2 when w (since $ > T') and that Tw S when w S 0 (since 7' is positive as we assume 2 1). Therefore,
G(er,Tg: Bu) F(m)))
< (logn) 011) ( --11/12) < <n
To finish, we will want to set X = p and (c-=1)²>² 86
p. Solving gives us A
2v/2c 6541
and
4
P
tc=+
A.2 Embedding into the Euclidean sphere
In the previous sections, assumed that the data lied reasonably low-dimensional Euclidean sphere, and that r was some reasonably small (but not too small) parameter. In this section, we explain why this assumption can be made without loss of generality, by using previous work of [BRS11] which allows us to embed the data into a Euclidean sphere.
Lemma A.1. [BRSII, Lemma 6, rephrased] Fix integers d, d' Z 1 and a parumeter 0 < <
There exists a randomized map θ .R.d - Sd'-1, where 5dd represents the unit sphere in Rdd that can be computed in time ((d d') for any point x E IRd, with the following properties for any K, E Rdd.
1. (0(x) e( s (1 +1) || - y1l2 with,failure probability at most exp (oz²).2
"The original claim also takes some parameters ...... Øp: we will set D) = d' /2 and every = 1. It is clear that the final function e defined in [BRS [1] has norm 1 in this case.
15

---

2. 1f ull2 S V then |1((z) - e 2 (1 - 7)- || - -yl2 with failure probability at -)
most exp 3Dn²
3. If | 1-- y112 2 vT, then [10()) 2 3 with probability at most exp
Dig 128
We will set d' = log
where we recall that equals the number of data points and equals the number of queries. Then, if we generate the randomized map @ ahead of time, with high probability the conditions in Lemma A.I hold for all n data points and any fixed query point. (In the final algorithm, we repeat the embedding Ollog m) times to amplify the success probability).
Corollary A.2. Suppose that (er)² S 3. and d' C. logn for some sufficiently large constant C. 7
Then, with least 0.99 probability over the randomized map ④ R - S -0 f all X and any fixed query y, || - yll2 S r implies [10(x) - @(v)l & (1 + +7) r and | ull2 2 cr implies [10(()) x)) (y)ll2 (1 - -) cr.
Proof. We assume that & was chosen so that for every E X and for the fixed y, the three claims in Lemma A.I all hold.
Fix some pair (x. y), where x E X,y E Q. First, if || - vll2 I r, then since r < / [((z) @ l2 S (1->)-|(--bb vll2 2 (1 (1-7)-cr. Otherwise, || ||0~yll2 2 v7, then [|0(x) (1))l 2 v 2 c.r 0
|| vll2 (1+7) .r. Next, if e-r $ || po--up yll2 S /7. then O(y)ll 2
We can now finish the proof of Theorem 1.1.
1+7 Proof. We will prove that we can solve the (c. 1-7 I+. -near neighbor counting with differential
privacy, where r = (log 1)) and = (log n)
1 1/8 over Euclidean space. By scaling, this
automatically implies the same result for any choice of r, and replaced with <(1+>) c(1 o(1))
We will run O(log m) independent copies of the data structure and algorithm, where each individual data structure satisfies (c', my ollog m))
-DP. By basic composition, this implies (c, 6)- DP overall. For each query, we output the median of the responses of each data structure, which by a Chernoff bound will significantly decrease the failure probability.
8
For each copy of the data structure, we first preprocess the data X E Rd by using the random map θ from Lemma A.1 to map each point E X to (zz), which takes O(nd d') time. Next, we create the data structure on O(X), which is on a d' = =0 logg = (log n) dimeesiinali
sphere. To answer any query E Rd. we compute ((q) in Odd d') time, and answer the query ((4) using the data structure created on ( By Corollary A.2, with 0.99 probability, any accurate answer for (c, -near neighbor counting on 5dd for a fixed query O(q) is an accurate answer for [er)/(17] T = (c- 1+2 T- -near neighbor counting problem for y over Rd Moreover, the embedding θ is oblivious to the data, which means privacy is preserved.
Now, we have embedded the data and queries onto the unit sphere 5d' for d' = (logn) 0(1), in O(nd d') (rad) preprocessing time. We may now create the data structure (Algorithm 1) and answer each query (Algorithm on sdd-1, We recall that, to improve the failure probability that every query is answered with high probability, and we will take the median over Ollg m) independent copies of the data structure, for each query. By Lemmas 3.2 and 3.6, the privacy and runtime conditions of Theorem 1.1 are all satisfied. Moreover, by Lemma 3.5, with probability at least 2/3 0.01 2 0.6, for each query g. each copy of the data structure is accurate, replacing the additive error 1 log 8 ==(((() with log m log log m n++o(1) By Chernoff bound, the overall algorithm (taking the median of Olog m) copies) is accurate on each
5 replaced (c, with (E', 8') (oTl m] Tllog my )
8
IIn the original paper [BRS11] [] they only prove this result for ||. - vll2 2 ||æ vlla 7, at the cost of reducing the failure probability from exponential in - to exponential in -D -.
. the same proof can extend to
16

---

query with probability at least 0.99 probability. This concludes the proof.
100m so it is accurate on all queries simultaneously with at least
B
Lower Bound
In this section, we prove Theorem 1.2.
Given points 21,...; 2n E f0, 133, and a series of queries Bı...., Bnn represented by axis- parallel boxes, we create the matrix Ar, to be the indicator of B; containing 2j. We define the red-blue discrepancy to be m=1,1(- ||Ax]|ac.
First, we have the following result due to Chazelle and Lvov [CLO1].
Theorem B.1. [CLO1] For sufficiently large n and C log n for a large constant C, there exists set of n points : {0, 1] and boxes B1, B1...., BB such that the matrix (Aag) E RRxx has red-blue discrepancy n n1( 20(4).
Now, we switch to the result of Muthukrishnan and Nikolov [MN12]. They have a slighly more general definition of discrepancy, of disc,.o - (A) = minge[[-1o..) -|lel 2a-d ||Ar]]pp so the above result written lower bound on disc(A) == 1 Now, we describe their theorem.
Theorem B.2. [MN12] For all x E {0, 13", there exist constants 6, such that no mechanism
.M = [Mn] that satisfies
Vo E 10,1)" (I.M)(()) Awlloo <
disc 2 2/3
is (c,5)-DP, where two data points x, x' {0, 1)"h are adjacent if they differ exactly in one coordinate location.
Given these lemmas, we ready prove our main lower bound, Theorem 1.2.
and d C' Cloog n for some constant C. By using Theorem of distinct points in 10, and a fixed set of boxes B1...., Bu, that generate matrix with discrepancy disc( (A) nP, where p 0 is fixed constant. For any x E {0, 1]", we define the dataset D, will be the subset of the public set where dimensional vector that precisely tells us the number of points in Da are in each box. In addition, if æ, x'' are adjacent in {0, 13", then Dr, Drr are adjacent datasets. Next for any axis scis-parallel box B,, we create a query point gi E {0. 1]dd as follows. In the kth coordinate dimension, if B; intersects either both neither of the planes 5h = 0 and 3y = 1, we set (i = 1/2. Otherwise, if B, only intersects the plane Ia O, we set l..k 1/2. Finally, if B; only intersects the plane 2y 1, we qi,k 1f8,=3//4 3/2.
Proof of Theorem 1.2. We set
B.I, we can construct a public set (zı,..., -n
24 E D2 if and only if x; 1. Then, Az would be an m
Suppose that A is an (c, 6)DP algorithm acting on subsets S of {0, ld of size at most n, that returns an estimate to I (x, 1)] for all queries qt Since every qi has half-integral coordinates, and every data point has integral coordinates, we have that (go 1) Bx 1/2) B (4, 3/2 a) for any > O, and these all equal B,. So, for any subset S C {0. 1)"
B (g., 1)1 |Sn (g. 1/2) |S B 3/2 a) = Bz).
Suppose that for any C (0, of size most n, with probability least 2/3, the output of A(S) for each query differs by at most T from |S B,l. Then, we can consider the algorithm M that acts on an element in (0, 1)", where M(x) = A(D.). Since A is (e, 6)-DP this implies that M is also (e, dD-P, with respect to adjacent elements in (0. 1)". Moreover, (A x); E, AijTr
Hj Aij = 23 1)1
D 0 Bel. Hence, by Theorem B.2, there must exist {0, 13" such that
disc(A) = (IMMo) AxIloo < disc(A)
2
[IA(D.) - Dr n bo
2
3
so T
disc(A) This completes the proof as disc(A) nP.
17

---

C
Extensions
l balls. is easy extend our algorithms to ranges that balls in the l norm. This relies on the well-known fact that the & norm embeds (almost) isometrically into a negative-tyle type metric, i.e., into squared Euclidean metric (Lz)². We use the following constructive version of this fact, from [LN14, Theorem 1 116] based on [MN04].
Theorem C.1 ([LN14]'), Let 1 S < 2. Let X C Hd be point set with Ey Ey-aspect ratio c. There is mapping f X + Rd for d' d poly 4, log d, 1/e) such for every v. y X,
o vll - ll((z) - f(w)l S (1+ + 1| yllp
The above theorem, applied for p 1, reduces upproximate range queries for & balls with approx- imation factor e approximate range queries for (f2)² balls with approximation factor e/(1 + e) and d replaced by d'. The latter problem is equivalent to approximate range queries for f2 balls with approximation factor ve/(1 c). The final bound follows by following this sequence of reductions.
Pure Differential Privacy. The only reason that our algorithm requires approximate differential privacy is that
truncated Laplace noise in line 19 of Algorithm 1. We use truncated Laplace noise so that if any leaf node is empty, then the noisy count will be 0 with probability 1. To make the algorithm pure-DP, we modify line 19 add Lap(2/e) noise to the count G., and in lines 20-21, replace Go with 0 whenever the noised count is at most 10 K log T. For the parameters in subsection 3.4, this is at most (log (01))
The difficulty, however, is that we need to speed up the runtime from TK as done in the runtime analysis in subsection 3.3. Specifically, we need ensure that few nodes are created (i.e., have C. 0): prove that, in expectation, this holds. In addition, we need to determine which nodes will have 6, * efficiently. If so, we only need to create these nodes in the preprocessing, which completes the proof.
First, we determine which nodes every data point p E X is sent to, in the same fashion as in runtime analysis in subsection 3.3. Suppose there are n' S n nonempty regions: then there are N = T n' empty regions. For each node e, we wish to sample e, ~ Lap(2/e) as the noise, and if G, > 10 K Klog T, we keep the node and store G,. Otherwise, we reset eo back to 0, and do not need to store v.
We note that the probability of any fixed c, > A. log Tis 1 ee (e/2)) K/og///))))//TT = e-5K logT /22 T-5K /2. Let := T-5K /2. We first consider the problem of sampling from Bin a), which represents the number of empty regions that will have e, O. Note that P(Bin(N, a) > 0)
5k
1 - 1-(1 (1-T -1-17-5//22)
< T-4K By using a repeated squaring approach, we can compute this probability exactly in poly log(T*)= = poly log n time. Then, we can flip a coin with this probability, and with at most / failure probability, the Binomial equals O. Otherwise, need to compute the distribution Bin(N, a) conditioned on it being at least 1. However, we can compute each term (M)a -a) P(Bin(N,, a)) r) time at most O(N2), which thus means we can compute every IP(Bin(N, a) = r) in time ( Hence, in the T-4K < N probability event still draw from the conditional distribution in time O(N3). Hence, in
that Bin a) > O. expected time poly log n, we can draw from a.).
0. because every c. (for empty regions v) has the same distribution, we can create the full tree, and then uniformly choose the subset of regions which will have noisy count at least 10. K log T. This takes time at most 72K We then have to compute each co Lap(2/c) for the r choices of v where c, > K log However, by using the well-known memoryless property of exponential distributions, the distribution of each c. is just 10 K log T + Expo(2/e).
In the case that Bin NN .x)
< Hence, we can compute the full data structure in time O(Tak), in this setting. This, however, only happens with at most -K probability.
*The statement [LN14] for (0)) but applies to any > The statement given here by setting R 1/9 in [LN14, Theorem 116] and scaling the minimal distance in the given metric to 1.
18

---

Alternatvell, if = O, we can avoid computing any ce when e is empty. The rest of the analysis in this case proceeds identically subsection 3.3. Finally, in either case, the time answer each query, in expectation, is still the same as in subsection 3.3.
Finally, we need verify the accuracy of the algorithm. In expectation, each co is off by at most O log K/c)= = (log n) )0(1))/)))))))) with 0 only happens when cv < O(T log K/c). The analysis of Lemma 3.3 proceeds identically, except that the first source of error replaces the log J term with a T log K = [logn)o() O(11) term.
the noise adds an expected ((1/c) error, and the replacing of cs
Finally, the embedding of arbitrary Euclidean data into the Euclidean sphere, as in Appendix A.2, proceeds the same way. Overall, Theorem 1.1 still holds when 8 = O, except that the runtime of both the preprocessing and answering each query is in expectation, and the additive error removes the log(log m/ term. (Indeed, the additional (log n) 01() factors in the runtime and additive error can be absorbed into the (1 term).
Large 6. We remark that our analysis extends to e < (20(1) in straightfoward manner. We remark that in practice, because the probability ratio in differential privacy depends on e", it is highly impractical use any significantly larger than 2(log n)), and therefore we believe that it is not interesting to analyze an algorithm beyond e S no(11)
To see why, note that for S S. (1),), any (1/2,6)-DP algorithm is automatically (e, 8).P. (This also holds in the = 0 case.) Note that the runtime bounds do not depend on e, and the accuracy bounds are proportional to 1/c the additive error. Therefore, if we allow the n(ta(1) term in the additive error have slightly larger o(1) in the exponent (i.e., up o())(1) /e), the claim still holds until e I (1) for any (11)
Adaptive Queries. Here, we explain how we are able to improve Theorem 1.1 to handle adaptive queries.
We assume we are promised that all data points are in RR, Rld, where R > r is some parameter. Let T represent the set of points (.i,...: Fa) where every |æ;| < 2R and r; is integral multiple of r/d. Note that [T| S Odd R/r)" ((dlog(dR//)).
Now, consider having M Od (og(d//r)) independent copies of the data structure, where each data structure initialized with ( (M++ &r J-P. To answer each query, each data structure computes its
approximation, and the overall data structure outputs the mean of the M responses. By standard
Chernoff bound, and the accuracy bounds of Theorem 1.1, the output will between (1 (1))(1) |X
(2 logglog m n and (1+o(1))- 2X (g, +n log(log m-M/5)) m
c/M
c/Af
with e (MM failure probability. In other words, the failure probability is e -Q(MM (assuming non- adaptive queries) and the additive error multiplies by most O(M log M). Moreover, each data structure is < 5 -DD,, so the overall algorithm, by basic composition, is (c, 5D-DP, Finally, the N
runtime will only increase by a factor of M (both for preprocessing and answering queries), since we have repeat the process for M data structures.
Now, we explain how we can deal with arbitrary adaptive queries. We can assume WLOG that every query is in the range [-2R, 2R] else the algorithm can simply output 0 without sacrificing either privacy or accuracy. Next, we can assume WLOG that every query is in T, because any query is within r/ r/vd of some point q' T, and answering the query on q' will be accurate up to an additive error of f//vd= = o(r). Therefore, as long as the data structure is accurate for all of the queries in T, this is sufficient.
Thus, for each q E T, the overall data structure will answer accurately with failure probability -((M) For M = O(d log log(d//r)) we have that |T| I eM(M), so by union bound, the data structure will answer any query q E T accurately. Therefore, even adaptive queries can be answered accurately, since even any adaptive query can be assumed WLOG to be in T.
19


Reviews:
[{"review_id": "ZVmgJDo2rR", "reviewer": "Reviewer_TS42", "summary": "In this work, the authors propose a differentially private data structure to approximately count the number of data points from within a dataset that lie within a certain small radius of a query point. \n\nThe preliminary data structure, intended for datasets that lie on a unit sphere, recursively splits the region into small caps. This is represented using a T-ary tree of height K. The leaf nodes of this tree maintain counts of all the points that lie within their corresponding regions. Privacy is obtained by perturbing these points using a truncated Laplacian mechanism. \n\nThe proofs follow from simple Gaussian concentration bounds and standard Laplacian mechanism. ", "questions": "- Can you convert any data-independent LSH with LSH constant \\rho to construct an approximate near neighbor counting using a similar tree structure in a black-box fashion? For instance, each internal node will correspond to all the points from the parent node that fall within a certain region. The error estimates will be analyzed in a similar fashion and will be guaranteed by the LSH parameters. \nThe insight comes from the \\rho used in the theorem statement whose value is exactly the optimal LSH constant for data-independent schemes. \n\n- How about data-dependent LSH? The construction of Andoni & Razenshteyn provides a better LSH constant and does a recursive splitting that looks similar to the one used in this work. ", "limitations": "Yes. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The problem is relevant and interesting. \n- The solution is simple and elegant and circumvents the drawbacks of prior works. \n- The authors provide a novel insight for using Locality sensitive hashing schemes for approximate counting.\n- The presentation is very clear and concise. ", "weaknesses": "- The improved results only hold for small values of r which is fixed in advance and is not a part of the input. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W: The improved results only hold for small values of r which is fixed in advance and is not a part of the input.\n\nA: It is true that our algorithm assumes that r is fixed. However, it does not need an assumption that r is small, see Appendix A.2. \n\n\nQ1: Can you convert any data-independent LSH with LSH constant \\rho to construct an approximate near neighbor counting using a similar tree structure in a black-box fashion? For instance, each internal node will correspond to all the points from the parent node that fall within a certain region. The error estimates will be analyzed in a similar fashion and will be guaranteed by the LSH parameters. The insight comes from the \\rho used in the theorem statement whose value is exactly the optimal LSH constant for data-independent schemes. \n\nA: The answer depends on whether privacy is considered. Without the privacy constraint, it is indeed possible to transform any LSH scheme for ANN search into ANN counting data structure. But once we consider the privacy constraint, there does not seem to be a natural way to do so. Specifically, our algorithm builds a decision tree that partitions that space/dataset into buckets, where the query looks up a subset of buckets. Constructing such a structure for an arbitrary LSH family is, to our knowledge, an open problem.\n\n\nQ2: How about data-dependent LSH? The construction of Andoni & Razenshteyn provides a better LSH constant and does a recursive splitting that looks similar to the one used in this work.\n\nA: Even though data-dependent LSH indeed gives better exponents, it seems particularly challenging to leverage it in a differentially private algorithm.  One challenge is that the space partitions intrinsically depend on the dataset, and hence it may be hard to control the privacy leakage here. Another challenge is that all known data-dependent LSH schemes are not pure space partitions --- a crucial condition we use to obtain the 1+o(1) multiplicative approximation factor --- and would instead give a super-constant factor.\n\n"}, {"review_id": "waYVWUwQyo", "reviewer": "Reviewer_3KJE", "summary": "This paper provides a new polytime algorithm for differentially private approximate near neighbor counting---that is, privately counting the number of points inside l2 balls of fixed radius r, or more precisely a relaxation that may answer any value between the number of datapoints in B(x,r) and the number of datapoints in B(x, c*r) for parameter c. \n\nExisting algorithms incur either additive error that is at least a fixed polynomial in the number of points n or additive error that is logarithmic in n but grows exponentially in the dimension d. The algorithm in this paper incurs additive error that is n^(O(1/c^2)) where c is the parameter above, which can be made an arbitrarily small polynomial in n and has no dependence on d, at the cost of also introducing a small multiplicative error term.\n\n(As a side result, the paper also provides a lower bound showing that for L-infinity balls, it is not possible to have additive error n^(o(1)) for constant c. It poses the more immediately relevant lower bound question for L2 balls as an open question.)", "questions": "1) Does the algorithm extend to other norm balls or other natural families of queries?\n\n2) Is there hope of removing the multiplicative approximation factor? Or else reason to believe that it is necessary?\n\n3) Do you think the analysis could go through for adaptive queries as well, or is it clear that the restriction to non-adaptive queries is necessary?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This is a nice result that improves on the additive accuracy of known results when both n and d are large. The algorithm is natural and interesting, and the paper is well-written and enjoyable.", "weaknesses": "It's not clear whether the multiplicative approximation factor is necessary to get a good additive dependence on both n and d. (It's perfectly reasonable to trade off a small multiplicative factor for a better additive term, so this is a bit of a nitpick. However, it does mean that the result is incomparable rather than strictly better compared to prior work even in the regime when n and d are both large.)  \n\nRelatedly, the lower bound (in addition to being for l_\\infty rather than l_2) does not take into account the multiplicative approximation, so it's not clear whether it's possible to obtain additive error n^{o(1)} for constant c if we also allow a multiplicative error. \n\nMinor comments:\nThe abstract should mention the multiplicative aspect of the approximation.\n42: Maybe say explicitly \\ell_2 ball here, not just ball.\n69: The accuracy guarantee should only hold with high probability for the m queries q_1, ..., q_m, not for every q\\in \\mathbb{R}^d.\n128: I'm not positive, but I think one of the interval query results of BNSV15 has been improved in subsequent work to reduce the gap between the upper and lower bounds.\n200: It's technically not a partition, since some points are not sent to any child.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1: It's not clear whether the multiplicative approximation factor is necessary to get a good additive dependence on both n and d. ... Relatedly, the lower bound (in addition to being for l_\\infty rather than l_2) does not take into account the multiplicative approximation.\n\nA: Indeed, we do not know the answer to this question.  The cardinality multiplicative factor is quite small (1+o(1)), but getting an algorithm that removes this factor (or lower bound showing it is necessary) is an interesting open question. \n\n\nQ1: Does the algorithm extend to other norm balls or other natural families of queries?\n\nA: The algorithm should extend easily to L1 balls, with somewhat worse performance bounds. This is because the L1 norm can be embedded into the L_2 norm squared, which (for range queries) is equivalent to the L_2 norm, though the approximation factor c becomes c^2. We will verify this, and if correct, include this observation in the final version.\n\n\nQ3: Do you think the analysis could go through for adaptive queries as well, or is it clear that the restriction to non-adaptive queries is necessary?\n\nA: We believe that it should be possible to extend the analysis to adaptive queries, at the cost of multiplying the additive error and runtime by a factor roughly d. The idea is that it should be possible to round every query point to an r-net, and then we just need an algorithm able to answer any query among (1/\\r)^O(d) queries accurately with failure probability (1/\\r)^{-O(d)}, so that by a union bound all queries are answered correctly. Such a data structure can be constructed by replicating the data structure in the paper d log(1/r) times. Since we need many replicas, each copy needs privacy with parameter eps replaced by eps/d, which multiplies the error/runtime by a factor of poly(d). We will verify this, and if correct, include this observation in the final version.\n"}, {"review_id": "fae2gmoYrF", "reviewer": "Reviewer_1btN", "summary": "\nThe papers shows how to use a variant of LSH to approximately count the neighbors in an r-ball (r fixed apriori). It shows how to obtain a differentially private LSH sketch. It analyzes the algorithm’s theoretical properties.\n", "questions": "1. The data structure created appears to be a (completely) random forest. What are the relationships between this work and differentially private random forests? \n\n2. Where do the 0.9 probability using Markov’s and 99% probability using Chernoff’s come from? I don’t see any other constants chosen that ensure these probabilities are reached.\n\n3. The extension to data not on a sphere is completely punted to the appendix. Can you give some insight on how this works, under what conditions it works, and what the impact to privacy is in the main text?\n\n4. The overview says that you “force” the LSH algorithm to create proper partitions. But where do you do this? Is it from the tree structure with depth? (as opposed to a stump-like structure) And doesn’t a single projection in LSH partition points into buckets so you can do fast lookups? Or by partition do you mean some fine partitioning?\n\n5.Can the structure answer a knn like query? I.e. What is the minimum radius r which contains k neighbors?\n", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "\nThe technical contributions look solid and the analyses seem correct, e.g. using a weaker Markov inequality to handle non-independence of points. \n\nIt shows how to avoid an exponential dependence on the dimension. \n\nThe algorithm itself is fairly clear. \n\nThe paper makes an interesting claim that their method also leads to the most space efficient approximate nearest neighbor search.\n", "weaknesses": "The presentation leaves a great deal to be desired. After the introduction, the exposition generally seems hastily arranged. Much of it is spent on the detailed analysis without offering much insight into either the algorithm or a high level overview of the proof strategy. The analysis skips details and crams equations into paragraphs which makes it harder to read. Since the proof is not short and many of the proofs are already in the appendix, it’d make sense to only outline the proof.\n\nThere is zero empirical validation. The result and algorithm are purely theoretical contributions.\n\nThere doesn’t seem to be any exposition supporting the claim that the paper yields the most space efficient known approx nearest neighbor search.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1: The presentation leaves a great deal to be desired. \n\nA: Apologies if the presentation was unclear. We will implement the reviewer’s suggestions in the final version of the paper. \n\nW3: There doesn’t seem to be any exposition supporting the claim that the paper yields the most space efficient known approx nearest neighbor search.\n\nA: We assume that the reviewer refers to the sentence “This is of separate interest, as this yields the most efficient algorithm for approximate nearest neighbor search with space O(nd), improving over [Kap15]”.  [Kap15] obtained a data structure with O(nd) space and query time dn^rho for rho=4/(c^2+1). Note that this gives a non-trivial query time only for c>\\sqrt(3). In contrast, our data structure obtains query time with rho=4c^2/(c^2+1)^2 which is smaller than 1 for all c>1.\n\nQ1: The data structure created appears to be a (completely) random forest. What are the relationships between this work and differentially private random forests?\n\nA: Thank you for an interesting suggestion. We are not experts on differentially private random forests, but after a cursory examination of the literature we believe that random forests are typically data-dependent,  which makes it  hard to guarantee privacy for range queries. (For the same reason, in our paper we are using data-independent instead of data-dependent LSH, despite the fact that the latter has slightly better bounds.). If the reviewer has concrete suggestions for random forest papers we should compare our methods to, we will perform a more in-depth analysis. \n\nQ2: Where do the 0.9 probability using Markov’s and 99% probability using Chernoff’s come from? I don’t see any other constants chosen that ensure these probabilities are reached.\n\nA: We use 0.9 and 99% only to simplify the presentation. These probabilities can be made arbitrarily close to 1 by adjusting the big-Oh constant in the appropriate parameters (the error bound for Markov and the number of repetitions for Chernoff).\n\nQ3: The extension to data not on a sphere is completely punted to the appendix. Can you give some insight on how this works, under what conditions it works, and what the impact to privacy is in the main text?\n\nA: We moved this entirely to the appendix as it is essentially a corollary of Bartal, Recht, and Schulman [BRS11], as we note in lines 338-341. We convert solving the nearest neighbor problem on the sphere with radius r into solving the problem in Euclidean space (not on the sphere) with the same radius. The high level idea of the BRS11’s result is to provide an efficient map from Euclidean space onto the unit sphere, which ensures close points stay close and far points stay far. We use this result as a black box, and this reduces solving the problem on Euclidean space to solving it on the sphere, which is our main algorithm. There is a slight distortion (which BRS11 rigorously quantifies), but it is insignificant for our purposes. Because we perform the private computation after performing this embedding first, we do not sacrifice privacy.\n\nQ4: The overview says that you “force” the LSH algorithm to create proper partitions. But where do you do this? \n\nA:  The specific place in Algorithm 1 where this is done is line 17. Breaking out of the “for i” loop ensures that we map each point p to only one child of the node v. \n\nQ5: Can the structure answer a knn like query? \n\nWe believe that given our data structure, one can use a similar approach to [HY21], and approximately retrieve the distance to the k-nn. In particular, given the parameter k, the goal is to retrieve r such that $r_k \\leq r \\leq (1+\\alpha) r_{k(1+o(1))+2t}$ where $r_i$ is used to denote the smallest radius around $q$ such that the ball $B(q,r_i)$ contains at least $i$ points. The approach of [HY21] is to roughly perform a binary search to approximately find the right radius at which there are at least k points. Please refer to Lemma 13 and Theorem 14 of [HY'21]. \n\nWe note, however, that there are two differences in our case:\n\n*  [HY21] assumes that the data points are from the discrete cube [u]^d and thus the minimum and maximum radius are bounded by 1 and $(\\sqrt d)u$. Our algorithm does not have this restriction and therefore, in order to answer k-nn type queries, one needs to further assume a bounded aspect ratio. Given that the minimum distance to any point is 1 and the maximum distance is $\\sqrt d u$, the algorithm of [HY21] queries the data structure $g = log_{1+\\alpha} (\\sqrt d u)$ many times to find the right radius at which there are at least k points included in the data structure.\n\n* However in our case, our algorithm works for a fixed r, and thus we now need to maintain g different data structures. Thus we need to use stronger privacy parameters in each data structure so that using composition theorems the overall privacy is preserved. This is as opposed to [HY21] where they did not need a separate data structure for different values of r and could reuse their data structure to answer queries for all values of r.\n\nWe will verify this, and if correct, include this observation in the final version.\n"}, {"review_id": "Ix9a6ZhPkN", "reviewer": "Reviewer_2zYg", "summary": "This paper studies the problem of answering approximate range queries privately. The paper presents a data structure to answer queries privately that helps avoid dimension dependence in the additive error for utility but incurs a multiplicative factor. The paper also showcases how to efficiently implement the data structure.", "questions": "Q1: Though $\\varepsilon < 1$ is preferable for privacy, is there a barrier in extending Theorem 1.1 to case when $\\varepsilon$ is $> 1$? \n\nQ2: How does the bound in Theorem 1.1 compare to other approaches for the case of $c=1$? ", "limitations": "Discussed in weakness section. Since work is of theoretical nature, negative societal impact is not apparent.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well structured, easy to follow with adequate discussion and comparison with prior work. \n\nThe approach introduced provides a trade-off between additive error incurred and approximation factor for the query, which to the best of my knowledge is a novel contribution. The lower bound is for a restrictive case but understanding this dependence is a nice open problem.\n", "weaknesses": "The privacy guarantee is limited to $(\\varepsilon, \\delta)$-DP and not pure differential privacy. Some discussion on limitation or approach for extension to pure differential privacy might be helpful.\n\nAlso, it is not clear if the multiplicative factor in utility is necessary or inherent to this approach. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1: The privacy guarantee is limited to (ε,δ)-DP and not pure differential privacy. Some discussion needed.\n\nA: We could in fact obtain pure DP, although in this case the algorithm would suffer from a small probability of having large runtime. We focused on approximate DP for simplicity. To convert our algorithm into a pure DP algorithm, in lines 19-21 of the data structure, we add regular Laplace noise with parameter eps/2 (not truncated) to ensure pure DP, and replace c_v with 0 if it does not exceed roughly 1/eps * n^{o(1)} for some sufficiently large n^{o(1)} parameter. (The \\Delta in line 20 is a typo and should be 1, we will fix( it.) The idea is that when the true count of a region is 0, its noisy count will not exceed the threshold with very high probability, but there is some small probability that it does exceed the threshold. We can compute the probability \\zeta that none of the truly empty regions exceeds the threshold after adding noise by simulating a Binomial distribution. In the high probability event that this holds, we do not need to store any of the leaves. Otherwise, there is a small probability that we will store some (or even all) of the leaves and their noisy counts, which makes both the runtime and accuracy much worse. However, in expectation, the runtime and accuracy are still as stated. We will update the paper to discuss this more rigorously.\n\nW2: Not clear if the multiplicative factor in utility is necessary or inherent to this approach.\n\nA: The cardinality multiplicative factor is quite small (1+o(1)), but getting an algorithm that removes this factor (or lower bound showing its necessary) is an interesting open question.\n\nQ1: Though ε<1 is preferable for privacy, is there a barrier in extending Theorem 1.1 to case when ε is >1\n\nA: There does not seem to be any barrier, although for a somewhat technical reason. Specifically, if eps > 1, we can of course get the same bounds as when eps = 0.5. Furthermore, as long as eps = n^{o(1)}, we still get the same theorem, because in the expression n^{\\rho+o(1)} the o(1) term becomes larger but remains o(1).  If eps is larger than n^{o(1)} the privacy guarantees are so weak that it is unclear whether the guarantees are meaningful. Still, the theorem might hold nevertheless. We will investigate this and discuss it in the final version of the paper. \n\nQ2: How does the bound in Theorem 1.1 compare to other approaches for the case of c=1\n\nA: There are generic techniques that work for arbitrary ranges (including Euclidean balls in high dimension) and achieve \\sqrt{n} additive error, such as the paper [HR10] which we cite on line 124. In our setting, one can think of the Q and U terms being exponential in the dimension, though in our setting the dimension can be assumed as logarithmic in n by standard dimension reduction procedures. Hence, their bound is roughly proportional to sqrt{n}. To the best of our knowledge, no other results are known for high-dimensional Euclidean space. \n\nOur bound is only n for c = 1, as we mainly focused on getting the right dependence for larger approximation constants c. We will discuss the comparison of [HR10] with our work in more detail, and if it is possible to combine our techniques with [HR10] to get improved results for smaller c, we will include this in our final version of the paper.\n"}]

Author rebuttal:
We thank all reviewers for their useful comments and feedback. We will fix the typos and presentation issues in the final version of the paper. In what follows we address the issues identified by the reviewers as weaknesses and/or listed as questions.

Meta-review: This paper studies approximate Near neighbor counting with differential privacy. The reviewers all agreed that the paper is interesting, and presents a natural and elegant solution. Any reviewer concerns were largely addressed in the discussion phase, and I would encourage the authors to update the paper based on the feedback, and the rebuttal. I am happy to recommend acceptance.
Decision: Accept (spotlight)