Fast Distance Oracles for Any Symmetric Norm
Authors: Yichuan Deng
Zhao Song
OMRI WEINSTEIN
Ruizhe Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distance oracle
Sketching
Symmetric norm

Abstract: In the \emph{Distance Oracle} problem, the goal is to preprocess $n$ vectors $x_1, x_2, \cdots, x_n$ in a $d$-dimensional normed space $(\mathbb{X}^d, \| \cdot \|_l)$ into a cheap data structure, so that given a query vector $q \in \mathbb{X}^d$, all distances $\| q - x_i \|_l$ to the data points $\{x_i\}_{i\in [n]}$ can be quickly approximated (faster than the trivial $\sim nd$ query time). This primitive is a basic subroutine in machine learning, data mining and similarity search applications. In the case of $\ell_p$ norms, the problem is well understood, and optimal data structures are known for most values of $p$.  

Our main contribution is a fast $(1\pm \varepsilon)$ distance oracle for  \emph{any symmetric} norm $\|\cdot\|_l$. This class includes $\ell_p$ norms and Orlicz norms as special cases, as well as other norms used in practice, e.g. top-$k$ norms, max-mixture and sum-mixture of $\ell_p$ norms, small-support norms and the box-norm. We propose a novel data structure with  $\tilde{O}(n (d + \mathrm{mmc}(l)^2 ) )$ preprocessing time and space, and $t_q = \tilde{O}(d + n \cdot \mathrm{mmc}(l)^2)$ query time, where $\mathrm{mmc}(l)$ is a complexity-measure (modulus) of the symmetric norm under consideration. When $l = \ell_{p}$ , this runtime matches the aforementioned state-of-art oracles. 

Fast Distance Oracles for Any Symmetric Norm
Yichuan Deng
Zhao Song Adobe Research zsongRadobe.co com
University of Science and Technology of China ethandeng02gmmiil.cm
Omri Weinstein
Ruizhe Zhang
The Hebrew University and Columbia University ow2161@colmmiaa edu
The University of Texas at Austin ruizhelutexas.c edu
Abstract
In the Distance Oracle problem, the goal is to preprocess n vectors T1, T2, .... in d-dimensional metric space (X", ||x) into cheap data structure, that given query vector 9 E X and subset S [nz] of the input data points, all distances ||q - x; l|e for 2; E S can be quickly approximated (faster than the trivial d|Si query time). This primitive mining and similarity search applications. In the case of lp norms, the problem is well understood, and optimal data structures known for most values of p.
basic subroutine in machine learning, data
Our main contribution is fast (1 + E) distance oracle for any symmetric norm -I---- This class includes l, norms and Orlicz norms as special cases. well other norms used in practice, e.g. top-k norms, max-mixture and sum-mixture tp norms, small-support norms and the box-norm. We propose novel data structure with On(( + mm))()))) preprocessing time and space, and ty = Ö(d + |S| mmc( query time, for computing distances to a subset of data points, where mmc(!) l) is complexit--measee (concentration modulus) of the symmetric norm. When = Ep this runtime matches the aforementioned state-of-art oracles.
Introduction
Estimating and detecting similarities in datasets is fundamental problem in computer science, and a basic subroutine in most industry-scale ML applications, from optimization [CMF+20, CLP+20., XSS21] and reinforcement learning [SSX21], to discrepancy theory [SXZ22] and co- variance estimation [Val12, Alm19], Kernel SVMs [CS09, SSSSCI1], compression and clustering [IRW17, MMR22], to mention few. Such applications often need to quickly compute distances of online (test) points to subset of points in the input data set (e.g., the training data) for transfer- learning and classification. These applications have motivated the notion of distance oracles (DO) [Pel00, GPPR04, WP11]: In this problem, the goal is to preprocess dataset of input points X= (x), 22. ... 2.,) in some d-dimensional metric space, into small-space data structure which. given a query vector q and a subset S C [m). can quickly estimate all the distances d(g, xr;) of q S (note that the problem of estimating a single distance d .r.) is not interesting in Rd, as this can be trivially done in (d) time, which necessary merely read the query q). The most well-studied case (in both theory and practice) is when the metric space is in fact a normed space, i.c., the data points {z; ]e]] E Rdd are endowed with some predefined norm || Il. and the goal is to quickly estimate ||x, - 41 simultaneously for all i.e., in time & nd which the trivial query time. Distance oracles can therefore be viewed as generalizing matrix-vector multiplication: for the inner-product distance function (z,, q). the query asks to approximate X q nd time.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

For the most popular distance metrics the Euclidean distance (f2-norm) and Manhattan dis- tance (norm)- classic dimension-reduction (sketching) provide very efficient distance oracles (JL84, AC09, L.FFU13.. However, in many real-world problems, these metrics do not adequately capture similarities between data points, and long line of work has demonstrated that more com- plex (possibly learnable) metrics can lead to substantially better prediction and data compression 07J. In particular, many works over the last decade have been dedicated to extending various optimization problems beyond Euclidean/Manhatt
distances, for example in (kernel) linear regres- sion [SWY+t 19], approximate nearest neighbor [ANN* 17, ANN 18], sampling [LSV18], matrix column subset selection [SWZ19]] and statistical queries [LNRW19].
For bg norms, the DO problem is well-understood [KYJ,,, where the standard tool for construct- ing the data structure is via randomized linear sketching: The basic idea is to reduce the dimension (d) of the data points by applying some sketching matrix t E R.mx (m < d) to each data point x; and store the sketch Φx.; E Rm. For query point linearity then allows to estimate the distance from (1 - v.)). The seminal works of [JL88,, AMS99, CCF04, TZ12] developed polylogarihmic-sizz sketching methods for the fn-norm, which was extended, in a long line of work, to any Ep norm with p < 2 [Ind06, KNPW11, CN20J. For p > 2, the sketch-size (d) becomes polynomial, yet still sublinear in d [SSO2, BYJKS04).
In this work, we consider general symmetric norms, which generalize E, norms. More formally, a norm /: Rd + E is symmetric if, for all E H and every d x d permutation matrix P, satisfies ((rx) = ((x) and also (([=)) = ((x), where |x]] is the coordinate-wise absolute value of x (for broader introduction, see [Bha97] Chapter IV). Important special cases of symmetric norms are lp norms and Orlicz norms [ALS+ 18), which naturally arise in harmonic analysis and model data with sub-gaussian properties. Other practical examples of symmetric norms include top-k norms, max-mix of e, norms, sum-mix of e, norms, the s-sppprrt norm [AFS12] and the box-norm [MPS14].
Several recent works have studied dimension-reduuctin (sketching) for special cases of symmetric norms such as the Orlicz norm [BBC+ 17, SWY++ 19, ALS+18), for various numerical linear algebra primitives [SWZ19]. These sketching techniques are quite ad-hoc and are carefully tailored to the norm in question. It is therefore natural to ask whether symmetry alone is enough to guarantee dimensionalit--redueee for symmetric similarity search, in other words:
Is there an efficient (1 + di-ditannce oracle for general symmetric norms?
By "efficcentt, we mean small space and preprocessing time (ideally nd), fast query time (<< d|S] for a query (g.5 S S [n]) and ideally supporting dynamic updates to 2,'s s in Ö(d) time. Indeed, most ML applications involve rapidly-changing dynamic datasets, and it is becoming increasingly clear that static data structures do not adequately capture the requirements of real-world applications [JKDG08, CMF+ 20, CLP+20], As such, is desirable to design a dynamic distance oracle which has both small update time (l,,) for adding/removing a point x; E Rd, and small query time (l,)) for distance estimation. We remark that most known DOs are dynamic by nature (as they rely on linear sketching techniques). but for general metrics (c.g., graph shortest-path or the Ex norm) this is much less obvious, and indeed linearity of encoding/devoding will be a key challenge in our data structure (see next section). The problem is formally defined as follows:
Definition 1.1 (Symmetric-None Distance Oracles). Let || llaym be the symmetric norm. The Symmetric-none norm Distance Oracle is data structure that efficiently supports any sequence of the following operations:
12 ... ,nn In. C ER, E (0, 1),6 E 1)). The data structure takes n data points (21,22.... ... .n C IRd,, an accuracy parameter and a failure probability 8 as input.
UPDATEX(2 E IRd, i E [n]). Update the data structure with the i-th new data point 2.
ESTPAIR(i.) E [n]) Outputs a number pair such that (1 - e)]læ;; - Iyllaym S pair S (1 +)) 1| - x. llym with probability at least 8.
QUERY(q E Rd). Outputs a vector dst E R such that Vi E [n], (1 <)llq -zz//ll =zlleym S dst, < (1 <)llq z zelleym. with probability at least 8.
where ||æ]laym is the symmetric norm of the vector x.

---

This problem can be viewed as an online version of the (approximate) closest- problem [Val12]. which asks find the closest pair points among an offline batch of data points == 21...., In R. or equivalently, the smallest entry of the covariance matrix XX One major (theoretical) advantage of the offline case is that enables the use of fast maatiiimmutiilicationn (FMM) to speed-up the computation of the covariance matrix [Val12, AWY14, AWY18, Alm19] (i.e., sub- linear amortized per query). By contrast, in the online setting such speedups are conjectured to be impossible (HKNS15, LW17].
Notations. For any positive integer n, we use [n]] to denote (1. For any function f. use Óf) denote poly(log f). We Pr[-] to denote probability. We B[-] denote expectation. We use both I(.) and || llym to denote the symmetric norm. We use - to denote the entry-wise & norm. We define a tail notation which is very standard in sparse recover/compressed sensing literature. For any given vector x E Rd and an integer k, we use "[J or FTail(()) to denote
the vector that without (zeroing out) top-k largest entries (in absolute). For vector x, we use x to denote the transpose of x. For matrix A, we use A to denote the transpose of A. We use 1, denote a length-n vector where every entry We use O, denote length-n vector where every entry
1.1 Our Results
Two important complexity measures of (symmetric) norms, which capture their "intrinsic dimen- sionality"", are the concentration modulus (mc) and maximum modulus (mmc) parameters. We now define these quantities along the lines of [BBC* 17, SWY- 19].
Definition 1.2 (Modulus of concentration (mc)). Let X R" be uniformly distributed on S the Eg unit sphere. The median of symmetric norm I is the (unique) value Mi such that Pr [[(X) 2 Mj] 2 1/2 and Pr [[X)) S Mi] 2 1/2. Similarly, by denotes the maximum value of (()) over E 5n- We call the ratio
mc(l) = bi/M
the modulus of concentration of the norm I.
For every k E [n), the norm induces a norm (1) on R$ by setting
(k) ((1)) (2,1,,22,.. (2..,, == ((x1, 42, ....... Tk O, 0)..
where (I1, T2,, Tk. 0, , 0) E R
Definition 1.3 (Maximum modulus of concentration (mmc)). Define the maximum modulus of concentration of the norm l as
6y00
mme(I) == max mc()(k)) = max kE(n
kE(n) Ma0
Next, present few examples (in Table 1) for different norm I's mmc(I).
Norm
mmn(())
Ep < 2)
(
6p > 2)
(2d1/-11/m)
top-k norms
((Vd/k)
k-support norms and the box-norm
O d)
max-mix and sum-mix of f1 and l2
O(1) O
Orlicz norm
.
Table I: Examples of minel), where max-mix of é and E2 is defined as max | e||=|]]] } for real number c, sum-mix of & and Eg is defined as ||æ|| + c||x||1 1 for real number e, and Cg of Orlicz norm is defined as the number that for all 0 < x < G(y)/G(x) S Coly/z)²
We are now ready state main result:
3

---

Theorem 1.4 (Main result, informal version of Theorem D.1), Let I| be any symmetric norm on Rd. There is data structure for the online symmetric-norm Distance Oracle problem (Definition 1.1), which uses n(d + mmc(l)²) poly(1/e, lol(g/// space, supporting the following operations:
(N In C R (0,1),8 (0, 1)): Given nV data points
{a1, 22, ...,..) Ind Rd an accuracy parameter and failure probability 5 as input, the data structure preprocesses in time
a(d + mmc(1)²) logg///))))(
Note that mino)) is defined as Definition 1.3.
(pDATEX(2 E R ; i [n]):: Given an update vector E R2d and index E [n]. the data structure receives and as inputs, and updates the i-th data point 24 <- 2, in
d poly(1/e, logg//,
time.
QUERY(Q R [n]]: Given a query point q Rd and subset of the input points S S [n], the QUERY operation outputs a (1 + e)- multiplicative approximation to each distance from q to points in S, in time
(d + [S| mmc(1)?)
i.e. it provides of estimates {dst; his such that:
e S, e1 xilli dst; S (1 (1+ -
with probubility at least 6
ESTPAIR(i,] E [n]) Given indices i [n]]. the ESTPAIR operation takes i and as input and upproximately estimates the symmetric norm distances from i-th to the j-th point Ts, IR in time mmo(l)² polyyl/e, l,log/////// 6)) i.e. it provides an estimated distance pair such that:
(1 (1-c)ll=; zzIle S pair S (1 + +)]la; - 2z]1e
with probubility least 6.
Roadmap. In Section 2, we give an overview of the techniques that we mainly use in the work. In Section we give an introduction of the Sparse Recovery Data we use for sketching. In Section 4 we analyze the running time and space of our data structure with their proofs, respectively. In Section we show the correctness of our data structure and give its proof. Finally in Section 6 we conclude our work.
2 Technique Overview
Our distance oracle follows the other sublincar- time compressed sensing and sparse recovery problems [Pril HIKP12, LNNTI6, NS19, SSW722]. The main idea is to compress the data points into smaller dimension by computing. for each data point æ; Rdd, (randomized) linear sketch + 2; Rd with d' < d at preprocessing time, where e2;; is an unbiased estimator of ||<:|]| At query time, given a query point E IR,, we analogously compute its sketch by.. By linearity of Φ the distance between g and x; (i.e., E(g xx:)) can be trivially decoded from the sketch difference thg hr., As we shall see, this simple virtue of linearity is less obvious to retain when dealing with general symmetric norms.
approach, which was extensively used in many
Layer approximation Our algorithm uses the layer approximation method proposed by Indyk and Woodruff [TW05] and generalized to symmetric norms in [BBC+ 17, + 19]. Since symmetric norms are invariant under reordering of the coordinates, the main idea in [IWO5] is to construct "layer vector" follows: for vector v E IRd round (the absolute value of) each coordinate to the nearest power a for some fixed a I and i N, and then sort the coordinates in increasing order.

---

This ensures that the i-th layer contains all the coordinates E [d] satisfying: a=1 < </ay| S a'. In particular, the layer vector of has the form
((v) = (a
0, 0) E R
by times
b2 times
bp times
where by is the number of coordinates in layer-i. More importantly, since the norm is symmetric, the layer vector L(v) has succinet representation: (bx)
Then, it suffices to estimate b; for each i E [P], where the Indyk- Woodruff sketching technique can be used to approximate the vector. At the i-th layer, each coordinate of is sampled with probability P/b, and then the algorithm identifies the fz-heuvy-hitters of the sampled vector. [BBC+ 17] gave criterion for identifying the important layers, whose heavy-hitter coordinates in the corresponding sampled vectors, is enough to recover the entire symmetric norm ||v]|
Unfortunately, this technique for norm estimation does not readily translate to estimating distances efficiently:
Too many layers: In previous works, each data point x; is sub-sampled independently in
R layers, i.e, generates R subsets of coordinates .!..... S. C [d]. The sketch of the query point S(q) then needs to be compared to each S1x;) in every layer. Since there R R= (2() layers in [BBC+ 17] of size (2()) across all data points, the total time complexity will be at least ((nd), which is the trivial query time.
Non-linearity: The aforementioned sketching algorithms [BBC 17] involve nonlinear operations, and thus cannot be directly used for distance estimation.
Slow decoding: The aforementioned sketches take linear time to decode the distance from the sketch, which is too slow for our application.
To overcome these challenges, we use the following ideas:
Technique I: shared randomness To reduce the number of layers, we let all the data points use the same set of layers. That is, in the initialization of our algorithm,
independently sample R subsets 5 ...... S with different probabilities. Then, for each data point T;, we consider (zi)s: as the sub-sample for the j-th layer, and perform sketch on it. Hence, the number of different layer sets is reduced from nt to f, where f is the number of layers for each data point. We share the layers for all points to remove the factor. For query point q. we just need to compute the sketches for (g)st..... (q)g ga. And the distance between and F; can be decoded from (db2z)s: - +(4)ss he( We also prove that the shared randomness in all data points will not affect the correctness of layer approximation.
Technique H:: linearization We choose different sketching method called BATCHHFANYHITTTE (see Theorem D.3 for details) to generate and maintain the linear sketches, which allows us to decode the distance from sketch difference.
Technical III: locate-and verrffy decoding We design a locate-and-verify style decoding method to recover distance from sketch. In our data structure, we not only store the sketch of each sub-sample vector, but also the vector itself. Then, in decoding a sketch, we can first apply the efficient sparse- recovery algorithm identify the position of heavy-hitters. Next, we directly check the entries at those positions to verify that they are indeed "heavy" (comparing the values with some threshold), and drop the non-heavy indices. This verification step is a significant difference from the typical sparse recovery approaches, which employ complex (and time-consuming) subroutines to reconstruct the values of the heavy-hitter coordinates. Instead, our simple verification procedure eliminates all heavy-hitters, therefore dramatically reducing the running time of the second step, which can now be performed directly by reading-off the values from the memory.
the
With these three techniques, we obtain our sublinear-time time distance estimation algorithm. Our data structure first generate a bunch of randomly selected subsets of coordinates as the layer sets. Then, for each data point, we run the AATCHHEAVYHITER procedure to sketch the sub-sample vector in each layer'. In the query phase, we call the DECODE procedure of BATCHHEAVYHITTER for the
'The total sketch size of each data point is mmc(l)² poly log d. In the 4p norm case with p mmcc!) = d1/2-1/r (see Table 1) and sketch size is -2/p), matching the lower bound of Ep-settching. When p (0, 2). mme(!)- (()) and our sketch size is Ö(1). which is also optimal.
5

---

sketch differences between the query point and each data point and obtain the heavy hitters of each layer. We then select some "important layers" and use them approximately recover the layer vector L(g æi), which gives the estimated distance ||g vallssmm-
Finally, summarize the time and space costs of data structure. Let be the precision parameter and 6 be the failure probability parameter. Our data structure achieves Ö(n(d + (ume()))))-tinn for initialization, O(d)-time per data point update, and O(d + n mmc(()2))-tmm)) per query. As for space cost, our data structure uses the space of Ö(n(d + mmc(1)3)) in total. Note that mmc is defined as Defnition 1.3.
Sparse Recovery Data Structure
We design data structure named B BATCHHEAAVYHTTER to generate sketches and manage them. In our design, is a "linear sketch" data structure, and providing the following functions:
INIT(E E (0, 0.1), n, Create set of Random Hash functions and all the copies of sketches share the same hash functions. This step takes Tiiit (c, n, d) time.
ENCODR(i E [n], E R4 .d. This step takes Tencode(d) encodes z into i-th sketched location and store size Sspace linear sketch.
ENcODESINNGLFE E [n],j E [d], IR, d). This step takes Tencodesingle(d) updates one sparse vector 2j² E _ into i-th sketched location.
SUBTRACT(i,j. E [r]].. Update the sketch at i-th location by j-th sketch minus I-th sketch.
DECODE(i E [n], c E (0, 0.1), d). This step takes Tdecode d) such that it returns a set L S [d] of size L = O( ?) containing all e-heavy hitters i [n] under lp. Here say i is an e-heavy hitter under lg if | 2 e. || where [ denotes the vector æ with the largest k entries (in absolute value) set to zero. Note that the number of heavy hitters never exceeds 2/c².
With this data structure, we are able to generate the sketches for each point, and subtract each other with its function. And one can get the output of heavy hitters of each sketch stored in it with DECODE function. More details are deferred to Section D.2.
4 Running Time and Space of Our Algorithm
We first analyze the running time of different procedures of our data structure DISTANCEON- SYMMETRICNORM. See Algorithm 5, with the linear sketch technique, spend the time of Ö(n(d + mmc(()²) for preprocessing and generate the sketches stored in the data structure. When updating the data with Algorithm we spend (d) to update the sketch, And when query comes (Algorithm 7), we spend O(d + n mmc(()²)) to get the output distance estimation. The lemmas of running time and their proof are shown below in this section.
Lemma 4.1 (INIT time, informal). Given data points {I1, .2...., InD C IRd, accuracy parameter e E (0, 1), and a failure probability (0, 1) as input, the procedure INIT (Algorithm 5) runs in time (nn(d= - mmc(l)?) poly(1/e,)) (ol/////)og(dd/))))
Proof. The INIT time includes these parts:
Line takes O(RLU- -Tnit Ti,,(VB,n, d)) to initialize sketches
Line 17 to Line 19 take OLRULL) to generate the bmap;
Line 24 takes O(ndRUL. - Tencodessiggl (d)) generate sketches
By Theorems D.3, we have
Twit (VB,i 10000-111 log" d) O(n mmc(l)² log" (d)e

---

Algorithm 1 Data structure for symmetric norm estimation: members, init, informal version of Algorithm and Algorithm
1: data structure DISTANCEONSYMMMETRICNNGN
Theorem D.1
2: members
3: {ri} Rd
4: (Srtatreetm
A list of the BATCHHEAVYHITTER
5:
C [d]
6: end members
7:
8: public:
9: procedure INIT((21,... In C. R ( 8)
> Lemma 4.1
Initialize the sparse-recovery data structure {Srtu) 11: Create (bmap,,,wwf shared by all i e [n] for i E [m],_j E [d do
> (bmapr,t,u J is list of a layer set map
12:
if bmaap,....... []] then
14:
Sample Zi,j into each subvector Tr,0,,5
end if 16: end for
Encode (araatta into {Sr.uu)
18:
end procedure
end data structure
Algorithm 2 Data structure for symmetric norm estimation: query, informal version of Algorithm 7
1: data structure DISTANCHONSSAMMTRICYOK
2: public:
3: procedure QUERY(ę E I
Lemma 4.3, 5.1
4: Encode q into {Sr.,.u}
5: for i [n] do
6:
Subtract the sketch of z; and q. get the estimated heavy-hitters of q 2; 7: Decode the sketch and store returned estimation of heavy-hitters into Hr,,, for и E [U] do
8:
9:
if H,.. provide correct indices of heavy hitters then Select it as good set and store it in H₁
10:
end if 12: end for
Generate estimated layer sizes (ct (clleeTP)
dst, LAYER CEEEEETCORPPRRR ot . cpp.
15: Reset (Hr,,,) for next distance
end for return {dst; kejn)
17:
18:
end procedure
19:
end data structure
Tencodesingle (d) (dog
Adding them together we got the time of
ORLUTi (v B, n, d)) + O(RULL) + OUdRRLL T Tencodesingte(())
O(RLU / B3, d) + nd Temcodeeiigte((d)) +
-0(0~*ll(11/ log'(d) (d) log(d) log(dd) 15 log(nd)) mmo(l)? (d)e nog (d)))
Onn(d+ mme(l)²) poly(1/e log(nd/
where the first step follows from merging the terms, the second step follows from the definition of R, L,, U, Tencodesingle (d)), Tinit the third step follows from merging the terms.
Thus, complete the proof.

---

Lemma 4.2 (UPDATE time, informal). Given a new data point IR,, and an index where it should replace the original data point z, E R The procedure UPDATE (Algorithm 6) runs in time
O logg(//),
Proof. The UPDATE operation calls BATCHHEAVYHITTTER time of
for RLU times, so has the
O(RLU Tencode (d)) = O log(1/8) log log(d) log(dd . dllgg log(nd))
= ( =d(e='doog" (nd/6))
where the first step follows from the definition of R, L, U, Tencode (d), the second step follows from (d) (d) log(d) log(d /6) log (d) log(nd)
(o/(1/6) log"
= (log(1/0)) (log' (2 log + log(1/0)) log(nd)
(nloo"(nddd)) (nd/6)).
Thus, we complete the proof.
Here, we present QUERY for outputting all the distances. In Section E, we provide more general version, which can take any input set C [n]] and output distance for only them in a shorter time that proportional [S].
Lemma 4.3 (QUERY time, informal). Given query point q Rd. the procedure QUERY (Algo- rithm 7) runs time
O(dd + n mmc(1)²) poly(1/c log(nd/8)))
Proof. The QUERY operation has the following two parts:
Part 1: Line 5 takes O(RUU -Tencode) time to call ENCODE to generate sketches for g.
Part 2:
For every [n]]
Line 13 takes O(RLU -Tsubtract) time to compute sketch of the difference between and æ4, and store the sketch at index of n +
Line 14 takes ORRUU -Taecode) time to decode the BATCHHEAVYHITTER and get estimated heavy hitters of q
Line 16 to Line 24 takes O(RLU- 22/3) time to analyze the BATCHHEAVYHITTER and get the set of indices, where 2/9 the size of the
Line 30 takes OLLP 2/3) time compute size of the layer sets cut by a.
Line 32 Line 36 takes (PL) time to compute the estimation of each layer.
The total running time of this part is:
(O(RLU Tsubtract) O(RUU Tdecodd) + O(RLU 2/8) + OLLP 2/3) + O(LP)) On + Taecade 1- + P3-
time in total.
Taking these two parts together have the total running time of the QUERY procedure: O(RLU Tencode) + (RL (Tsubtract + Taecode + - PB-1))
-((RU (Tencode Tsubtract + Telcode 1 nLP3-1)
OO(c-*lgg (d//(d/)) log(nd) 2 (d) n,3 log (d))((d))))))))))))))) (d)) nc - 1ogg(d))8-1)
= -O(d+ + n mmc(!)?) (1/e log,///).) log(nd/0)))
where the first step follows from the property of big O notation, the second step follows from the definition of R. L. U, Teucode, Tencode, Tsubtract. Teecode (Theorem D.3). P., the third step follows from merging the terms.
Thus, we complete the proof.

---

Next, we analyze the space usage in our algorithm. We sketch the proof in below and delay the full proof into Section G.
Lemma 4.4 (Space complexity of data structure, informal version of Lemma G.I). Our data siructure (Algorithm and 2) uses space
(n + mmc(1)²). poly(L/e,,og(d/0))
Proof Sketch. First, we store the original data with space for O(nd).
Second, store the sub stream/sample of original data with
space for I = Ö(E "nd).
Third, data structure holds set (Sr, (r(R)))r each Sri, of size of Ö(n 3-1). We show that total space needed is
space for S S= 5(c mmc(1)²).
Forth, we hold a bit-map bmap of size O(RUUd), which uses the space of
space for bmap Od)-dd)
Fifth, in QUERY procedure, we generate a set of sets size of 0(3-1), so the whole set uses space of
each of the sets has
space for H =mc=-mmol(1)
By putting them together, the total space complexity is
space for + space for ह + space for + space for bmap + space for
O(nd) + Ō(E="nol nd) Ō(E -n mmc((1²) Ō(E *d) Ö( 99 mmc(()2)
Ö nn + )m)
5 Correctness of Our Algorithm
The correctness of our distance oracle is proved in the following lemma:
Lemma 5.1 (QUERY correctness). Given a query point q E Rd, the procedure QUERY (Algorithm 7) takes q inpul and approximately estimates {dstt (aste)eem)) the distance between g and every with the norm such that for every dst, with probability least 5, we have
(1 e) |/q xillsym dst; S + e) |1q llymm
Proof. Without loss of generality, we can consider fixed i e [n]. For simplicity, we denote x, by Let q- By Lemma C.3, it is approximated by its layer vector C(v), namely, || < (())llym I + (())
(1)
where || |laym is symmetric norm, denoted also by I(.).
We assume without loss of generality that 2 1/ (oly Our algorithm maintains data structure that eventually produces vector [v)), which created with the layer sizes C1 02,.....pp Cp, where c's denotes the estimated layer sizes output by out data structure, and the b's are the ground truth layer sizes. We will show that with high probability, (v) approximates [.C(v))lsym Specifically, to achieve (1 + aapproximation to [|u]|yym we set the approximation guarantee of the layer sets
(Definition C.I) to E : 0 (og(a)) and the importance guarantee to 30 = O mme((]] ing where mmc(!) is defined as Definition 1.3.

---

Observe that the number of non-empty layer sets P = Olog,, (d)) = (loog(d) Let Escceeed denote the event - E )b,. I c bg. By Lemma F.1, it happens with high probability Conditioned on this event.
Denote by (v) the vector generated with the layer sizes given by Line 35, and by (v) the vector C(v) after removing all buckets (Definition C.2) that are not f-contribuuing (Definition C.5), and define J' (v) similar to L (v), where we set B e/P O log(d)). Every 8-contributing layer is necessarily 9o-important (Definition C.1) by Lemma C.7 and Lemma C.8 and therefore satisfies
Ck (1 <1 bb (Lemma F.1). We bound the error of || (z) Ilaym by Lemma C.6, namely.
(1 -1-0(6 (vv)ll & (1 - O(log, d) (3)l llemm S (v) sym I [1)(y)) where the first step follows from the definition of the second step and the third step follow from Lemma C.6.
Then, have
1 (u)]laym
2 [ (u)llym
L [u)) CR, (1) (z, \Cn,
(v) (v) TR. (U)llaym
2 (1 - -) 1 Ilam
2 (1 - (())) lsym
(2)
where the first step follows from monotonicity (Lemma B.1), the second step follows from the definition of (v), the third step follows from Lemma C.4, and the fourth step follows from the definition of é and P.
Combining Eq. (1) and (2), we have
(1 (1-O(e)) ||lllam I [1) S ||lleym
(3)
which bounds the error of
as required. Note that, with Lemma C.6 we have (e)) [ $ [1
S [[J((v) llym
(4)
Combining the (3) and (4) we have
(1 (c)) ||llsmmm I (T() I (1+ O())) ||
Note that Esnrreed has failure probability of 6. Thus, we complete the proof.
6 Conclusion
Similarity search is the backbone of many large-scale applications in machine-learning, optimization, databases and computational geometry. Our work strengthens and unifies long line of work on metric embeddings and sketching. by presenting the first Distance Oracle for any symmetric norm, with nearly- query and update times. The generality of our data structure allows apply it as black-box for data-driven learned symmetric distance metrics [DKJ+0] 07] and in various optimization problems involving symmetric distances.
Our work raises several open questions for future study:
The efficiency of our data structure depends mmc(!), the concentration property of the symmetric norm. Is this dependence necessary?
Can we generalize
data structure certain asymmetric norms ?
Can we extend our symmetric-norm distance oracle to any (non-linear) metric space (i.e., graphs)?
We believe our work is also likely to influence other fundamental problems in high-dimensional optimization and search, e.g, kernel linear regression, geometric sampling and near-neighhor search.
Acknowledgments
RZ was supported by the University Graduate Continuing Fellowship from UT Austin.
10

---

References
[AC09] Nir Ailon and Bernard Chazelle. The fast johnson lindesrnlnndeesstauus transform and approxi- mate nearest neighbors. SIAM Journal computing, 39(1):30--322) 2009.
[AFS12] Andreas Argyriou, Rina Foygel, and Nathan Srebro. Sparse prediction with the k- support norm. Advances in Neural Information Processing Systems (NeurIPS), 25, 2012.
[Alm19] Josh Alman. An illuminating algorithm for the light bulb problem. In 2nd Symposium on Simplicity in Algoritims (SOSA). Schloss Dagstuhl-Leibiiz Lentrim fuer Informatik, 2019.
[ALS* 18] Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, and Ruiqi Zhong. Subspace embedding and linear regression with orlicz norm. In International Conference Machine Learning (ICML), pages 224-233. PMLR, 2018.
[AMS99] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1):137-147, 1999.
[ANN+ 17] Alexandr Andoni, Huy L Nguyen, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten. Approximate near neighbors for general symmetric norms. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 902-913, 2017.
[ANN+ 18] Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Wain- garten. Hölder homeomorphisms and approximate nearest neighbors. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 159-169. IEEE, 2018.
[AWY14] Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 218-230. SIAM, 2014.
[AWY18] Josh Alman, Joshua R Wang. and Huacheng Yu. Cell-probe lower bounds from on- line communication complexity. Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 1003-1012, 2018.
(BBC+17) Jarostaw Btasiok, Vladimir Braverman, Stephen R Chestnut, Robert Krauthgamer, and Lin F Yang. Streaming symmetric norms via measure concentration. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 716-729, 2017.
[Bha97] Rajendra Bhatia. Matrix analysis, volume 169 of. Graduate texts in mathematics, 1997.
[BYJKS04] Ziv Bar- Yossef, Thathachar S Jayram, Ravi Kumar, and D Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702-732, 2004.
[CCF04] Moses Charikar, Kevin C. Chen, and Martin Marach-Colton Finding frequent items in data streams. Theor. Comput. Sci., 312(1):3-15, 2004.
[Che52] Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, pages 493-507, 1952.
[CLP+20] Beidi Chen, Zichang Liu, Binghui Peng. Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re. Mongoose: A learnable Ish framework for efficient neural network training. In International Conference on Learning Representations (ICLR), 2020.
[CMF+20) Beidi Chen, Tharun Medini, James Farwell, Charlie Tai, Anshumali Shrivastava, et al. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. Proceedings of Machine Learning and Systems, 2:291-306, 2020.
11

---

[CN20] Yeshwanth Cherapanamjeri and Jelani Nelson. On adaptive distance estimation. In Advances Neural Information Processing Systems, 2020.
[CS09] Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. Advances in neural information processing systems, 22, 2009.
[DK++07] Jason V Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S Dhillon. Information- theoretic metric learning. In Proceedings of the 24th international conference on Machine learning, pages 209-216, 2007.
[GMS86] M Gromov, V Milman, and G Schechtman. Asymptotic theory of finite dimensional normed spaces, volume 1200 of lectures notes in mathematics, 1986.
[GPPR04] Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. Journal of Algorithms, 53(1):85-115 -12, 2004.
[HIKP12] Haitham Hassanich, Piotr Indyk. Dina Katabi, and Eric Price. Nearly optimal sparse fourier transform. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC), pages 563-578, 2012.
[HKNS15] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Sara- nurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 21-30, 2015.
[Ind06] Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM), 53())307-323,, 2006.
[IRW17] Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Practical data-dependent metric com- pression with provable guarantees. Advances in Neural Information Processing Systems, 30, 2017.
[IWO5] Piotr Indyk and David Woodruff. Optimal approximations of the frequency moments of data streams. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 202-208, 2005.
[JKDG08] Prateek Jain, Brian Kulis, Inderjit Dhillon, and Kristen Grauman. Online metric learning and fast similarity search. In NIPS, volume 8, pages 761-768. Citeseer, 2008.
[JL84] William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984.
[KNPW11] Daniel M Kane, Jelani Nelson, Bly Porat, and David P Woodruff. Fast moment estima- tion data streams in optimal space. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 745-754, 2011.
[KWW10] Daniel M Kane, Jelani Nelson, and David P Woodruff. On the exact space complexity of sketching and streaming small norms. In Proceedings of the twenty-first annual ACM-SIAM symposium Discrete Algorithms, pages 1161-1178. SIAM, 2010.
[LDFU13] Yichao Lu, Paramveer Dhillon, Dean P Foster, and Lyle Ungar. Faster ridge regression via the subsampled randomized hadamard transform. In Advances in neural information processing systems (NIPS), pages 369-377, 2013.
[LNNT16] Kasper Green Larsen, Jelani Nelson, Huy L Nguyên, and Mikkel Thorup. Heavy hitters via bluster-preserving clustering. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 61-70. IEEE, 2016.
[LNRW19] Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten. On mean estimation for general norms with statistical queries. In Conference on Learning Theory (COLT), pages 2158-2172. PMLR, 2019.
[LSV18] Yin Tat Lee, Zhao Song, and Santosh S Vempala. Algorithmic theory of odes and sampling from well-conditioned logconcave densities. arXiv preprint arXiv: 18/2,06243, 2018.
12

---

[LW17] Kasper Green Larsen and Ryan Williams. Faster online matrix- metrox-vector multiplication. In Proceedings of the Twenty-Eige Annual ACM-SIAM Symposium on Discrete Algo- rithms, pages 2182-2189. SIAM, 2017.
[MMR22] Konstantin Makarychev, Yury Makarychev, and llya Razenshteyn. Performance of johnson-lindeenstrass transform for k-means and k-medians clustering. SIAM Journal on Computing, (0):STOC19-269, 2022.
[MPS14] Andrew M McDonald, Massimiliano Pontil, and Dimitris Stamos. Spectral k-support norm regularization. Advances in neural information processing systems, 27, 2014.
[NS19] Vasileios Nakos and Zhao Song. Stronger 12/12 compressed sensing; without iterating. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 289-297, 2019.
[Pag13] Rasmus Pagh. Compressed matrix multiplication. ACM Transactions on Computation Theory (TOCT), 5(3):1-17, 2013.
[Pe100] David Peleg. Proximity-preserving labeling schemes. Journal of Graph Theory, 33(3):167-176, 2000.
[Pril1] Eric Price. Efficient sketches for the set query problem. In Proceedings of the Twenty- Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 41-56, 2011.
[SS02] Michael Saks and Xiaodong Sun. Space lower bounds for distance approximation in the data stream model. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 360-369, 2002.
[SSSSC11] Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro, and Andrew Cotter. Pegasos: Primal estimated sub-gradient solver for sym, Mathematical programming, 127(1):3-30, 2011.
[SSW722) Zhao Song, Baocheng Sun, Omri Weinstein, and Ruizhe Zhang. Sparse fourier transform over lattices: A unified approach to signal reconstruction. http:/aariv.orgaa///20000066666 2022.
[SSX21] Anshumali Shrivastava, Zhao Song, and Zhaozhuo Xu. Sublinear least-squares value iteration via locality sensitive hashing. arXiv preprint arXiv:2105.08288: 2021.
[SWY+19] 19] Zhao Song, Ruosong Wang, Lin Yang, Hongyang Zhang, and Peilin Zhong. Efficient symmetric norm regression via linear sketching. Advances in Neural Information Processing Systems, 32, 2019.
[SWZ19] Zhao Song, David Woodruff, and Peilin Zhong. Towards a zero-one law for column subset selection. Advances in Neural Information Processing Systems, 32, 2019.
[SX722] Zhao Song, Zhaozhuo Xu, and Lichen Zhang. Speeding up sparsification with inner product search data structures. arXiv preprint arXiv:2204.03229, 2022.
[TZ12] Mikkel Thorup and Yin Zhang. Tabulation-based 5-independent hashing with applica- tions linear probing and second moment estimation. SIAM J. Comput., 41(2):293-331, 2012.
[Val12] Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and juntas. 2012 JEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 11-20. IEEE, 2012.
[WP11] Oren Weimann and David Peleg. A note on exact distance labeling. Information processing letters, 111(14):71-667, 2011.
[XSS21] Zhaozhuo Xu, Zhao Song, and Anshumali Shrivastava. Breaking the linear iteration cost barrier for some well-known conditional gradient methods using maxip data-structures. Advances Neural Information Processing Systems (NeurIPS), 34, 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]. we discuss the theoretical guar- antee the accuracy-efficieng tradeoff of our algorithm in Section and Section E.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our theoretical work does not have explicitly negative societal impacts.
(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 set of assumptions of all theoretical results? [Yes], we explicitly stated the assumptions.
(b) Did you include complete proofs of all theoretical results? [Yes] please refer to Section 4, Section and supplementary materials.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(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]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(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't '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 or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "s2MZT6UvM6N", "reviewer": "Reviewer_oXwu", "summary": "The paper considers the distance oracle problem, where one has a database X of points, and given a query point, one must compute the approximate distances from the query to all points of some subset of X. The authors consider this problem in the very general setting of symmetric norms, norms where the ordering of the coordinates is unimportant, and taking absolute value of the coordinates does not alter the norm. Results are given in terms of the modulus of concentration of the norm.\n\nThere are several interesting techniques presented in the paper. The paper builds on the well-known \"layered approximation\" technique, but optimizes it for the current problem by reducing the number of layers, ensuring linearity, and reduces the decoding time. The overview of these techniques is informative.", "questions": "None", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The problem is interesting, as are the techniques employed and the achieved result.\n\nWeaknesses: Needs a few more rounds of proofreading, and the presentation needs to be improved. \n\nThere's too little detail in the body of the paper, and one has to look at the appendix to understand anything about the construction.\n\nThe problem statement is strange. Generally, distance oracles are defined on the input set X, to quickly return the distances between any two points in X (i.e. in less than d time). The problem being solved here is a different version of that, where this is a query point not in X, but the authors should not present this as the only (or in fact even the main) meaning of the term distance oracle. \n\nAnother issue is the repeating assumption that linearity is somehow central to the functioning of distance oracles. Perhaps it's essential to the current construction, but many oracles do not require linearity. I'm reminded of Indyk's hashing for lp using p-stables, where he takes the median over many computed distances. Oracles for non-vector spaces don't use linearity at all.\n\nMinor comments:\nThere are some informalities (\"cheap\", \"a bunch\") that are better avoided.\np2l52  norm norm\np2l65  n|S| shoud be d|S|\np2l72  \"need to design\" does not belong in a definition of a structure\np2l83  dst_i isn't defined yet\np3l105  How many 0's are there?\np3 table  for the k-support norm, shouldn't there be a dependence on k?\np4l119  it's a 1+epsilon approximation, not epsilon\np4l133  The problem under consideration (recovering the norm) should be mentioned in the beginning of the paragraph. \np5l11  What's t?\np6  Both algorithms have the same name", "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": "JXbQAzPsz9i", "reviewer": "Reviewer_p7qi", "summary": "The authors present a data structure, for a given set of $n$ vectors in a $d$-dimensional metric space and a query vector, that can quickly approximate the distances of the query vector and any vector of the data structure.\n\t\nThe data structure can manage any symmetric norm hence it is not only limited to $\\ell_p$ norms. For $\\ell_p$ norms the data structure is as efficient as standard oracles, but it can be applied to more norms.", "questions": "The authors should add more formal theorems, explanatory or guiding text passages and sketch some of the proofs a little more in detail.\n\nminor errors:\n- $\\ell \\ell$ 46 onward: the sentence is confusing;\n- $\\ell$ 128: ''Section 4 analyze ...'' should be something like ''\\textbf{In} Section 4 \\textbf{we} analyze ...''. Same goes for the following sentences in the roadmap.\n- $\\ell$ 128: \\st{Then ,}\\textbf{I}t\n- $\\ell$ 220: \\st{When it comes a data update}\\textbf{When updating the data with Algorithm 5} ...\n- $\\ell$ 229: take\\st{s}", "limitations": "No potentially negative societal impact in sight.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and structured. Giving an intuitive version of the main results and used techniques is also really helpful. The problem the authors tackle is interesting, although it is iterative (i.e. the cases in which their improvements apply are minor).\n\nThe result is iterative as mentioned, though it remains interesting. Instead of giving sketches the authors reference knowledge of the appendix. This is even done to main results, which are only formulated in an informal way. Sometimes the reader is left on their own with out any text guiding them through sections, which is irritating.", "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": "JDjim616G8e", "reviewer": "Reviewer_FHL4", "summary": "The paper provides a data structure based on matrix sketches and embeddings for the problem of estimating similarities, and computing distances. Specifically speaking, the proposed idea is to present a distance oracle that is represented by an efficient data structure.", "questions": "As mentioned before, my concern is regarding the running time stated in the paper. Can you explain why this is not a problem or suggest a way to reduce this running time to make it much more practical, considering that the similarity problem is highly important in machine learning and other fields as well.\n\nIn addition, can coresets fit the role of solving the objective of this paper? specifically dynamic coresets?", "limitations": "The proposed data structure takes time that might be astronomical for small error parameters $\\varepsilon$.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths:\n   1) The paper proposes a data structure based on a distance oracle for a family of norms, namely, symmetric norms.\n   2) The proposed data structure in the paper uses matrix sketches and embeddings to obtain theoretically faster running time than existing techniques.\n\n\n* Weaknesses:\n   1) The proposed data structure takes time that is at least $\\Omega\\left( \\varepsilon^{-9} \\right)$. Even for small error accuracies, e.g., $\\varepsilon = 0.001$, the running time tends to be astronomical.  \n   2) The writing of the paper is slightly hard to follow. Please add some paragraphs to ease the transitions, specifically around the algorithms stated in the main paper.\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": "8eCxxWO9jtL", "reviewer": "Reviewer_HT4N", "summary": "This paper addresses the problem of distance oracles for symmetric norms. In this context, the goal is to preprocess a dataset of $n$ input points $x_1,\\ldots,x_n$ in some metric space, into a small-space data structure so that given a query vector $q$ and a subset $S \\subseteq [n]$, one can quickly estimate all the distances $d(q, x_i)$. To this goal, the author(s) design a new data structure named to generate sketches and manage them. With this data structure, the author(s) obtain a sublinear-time distance estimation algorithm to solve DO. ", "questions": "Q1: $||{\\cdot}||_\\mbox{sym}$ denotes a fixed but arbitrary symmetric norm, correct? I think this should be said somewhere before referring to it as \"the\" symmetric form. \n\nQ2: On Line 83: What is $\\mbox{dst}_i$? It did not seem to have been defined. Same on Line 121. Did I miss the definition?\n\nQ3: On Line 152, it says \"$\\ell_2$ -heavy-hitters.\" What does this mean?\n\nQ4: On line 194 and 195, you mention $\\epsilon$ and $\\delta$ but they are not used in the following sentences. So would it be reasonable to not mention them in those lines to help the exposition?\n\nQ5: On Line 297, what is the order of the $\\setminus$ and the $\\cup$? Parenthesis would be helpful. \n\n\nMinor typos\n\nLine 1: Please use $\\ldots$ when listing elements and no $\\cdots$\n\nLine 8: In the abstract, there should be a \"-\" in \"(1 + $\\varepsilon$) distance\"\n\nLine 52: norm is repeated twice, \"norm norm\"\n\nLine 43: Add an extra space after the comma that follows the reference [BYJKS04]\n\nLine 63: Add : at the end of the line to make the rest a complete sentence\n\nLine 72: Do you mean \"a symmetric norm\" instead of \"the symmetric norm\" or \"a generic, but fixed, symmetric form\"?\n\nLine 92: use $\\ldots$ instead of $\\cdots$ in the definition of $[n]$.\n\nLine 100: Do you mean the $\\ell_2$-unit sphere?\n\nDefinition 1.2: Consider defining the median of a symmetric norm outside of Def. 1.2 (ideally before). This way, Def. 1.2 is only about mc\n\nLine 106: Add \"Maximum modulus of concentration\" to the definition to make it consistent with Def. 1.2\n\nLine 116: data is repeated twice\n\nLine 147: Use $\\ldots$ instead of $\\cdots$ in the definition of $\\mathcal{L}(v)$\n\nLine 160: all is repeated twice \"all all\"\n", "limitations": "The authors do address the limitations of their work in specific sections of the paper. I think they do a very good job in this case. \n\nThey don't address potential negative societal impact, but as they point out in the check-list, it is theoretical work and does not seem to have any explicit negative societal impact. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nI think the data structure they design for linear sketching is interesting in its own right and deserves further study. In their open questions, they point out that the efficiency of their data structure depends on the concentration property of the symmetric norm and whether or not said dependency is necessary. \n\nWeaknesses\nIt is not clear to me how significant it is from a practical point of view to solve DO problem for a generic symmetric norm. I realize the authors do mention that $\\ell_p$ norm are symmetric norms, and that the DO problem is understood in this case. However, in practice, do people use arbitrary symmetric norms for which the DO problem wasn't understood? The theoretical motivation is more clear to me, but not the practical motivation. \n\nThe paper was also a bit hard for me to read. $\\mbox{dst}_i$ did not seem to be defined anywhere, and even if it is obvious it should be defined for the sake of completeness. There are a couple of distracting typos (see the Questions sections) and overall the exposition is bit cumbersome for me to fully follow the relevance of the results of the paper.\n\nThere are also no experiments in the paper. Some of the theoretical guarantees in Section 4 could be moved to the appendices to make space for empirical evidence of the theoretical claims. ", "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