The nearest neighbor search problem is defined as follows: given a set X of n points in a ddimensional space, build a data structure that, given any query point y, returns the point in X closest to y. For efficiency reasons, the problem is often relaxed to approximate nearest neighbor search, where the goal is to find a point x ∈ X whose distance to y is at most c min x∈X x -y for some approximation factor c > 1. Both problems have found numerous applications in machine learning, computer vision, information retrieval and other areas. In machine learning in particular, nearest neighbor classifiers are popular baseline methods whose classification error often comes close to that of the best known techniques (Efros (2017)).
Developing fast approximate nearest neighbor search algorithms have been a subject of extensive research efforts over the last last two decades, see e.g., Shakhnarovich et al. (2006); Andoni and Indyk (2017) for an overview. More recently, there has been increased focus on designing nearest neighbor methods that use a limited amount of space. This is motivated by the need to fit the data set in the main memory (Johnson et al. (2017b,a)) or an Internet of Things device (Gupta et al. (2017)). Furthermore, even a simple linear scan over the data is more time-efficient if the data is compressed. The data set compression is most often achieved by developing compact representations of data that approximately preserve the distances between the points (see Wang et al. (2016) for a survey). Such representations are smaller than the original (uncompressed) representation of the data set, while approximately preserving the distances between points.
Most of the approaches in the literature are only validated empirically. The currently best known theoretical tradeoffs between the representation size and the approximation quality are summarized in Table 1, together with their functionalities and constraints.
Comments No compression d log n Johnson and Lindenstrauss (1984)
-2 log 2 (n) Estimates distances between any y and all x ∈ X Kushilevitz et al. ( 2000)
-2 log(n) log(R) Estimates distances between any y and all x ∈ X, assuming x -y ∈ [r, Rr] Indyk and Wagner (2017)
-2 log(n) log(1/ ) Estimates distances between all x, y ∈ X, does not provably support out-of-sample queries This paper -2 log(n) log(1/ ) Returns an approximate nearest neighbor of y in X Table 1: Comparison of Euclidean metric sketches with distortion 1 ± . We assume that all point coordinates are represented using log Φ bits, or alternatively that each coordinate is an integer in the range {-Φ . . . Φ}. For the sake of exposition, the results depicted in the table assume Φ = n O(1) . Furthermore, the compression algorithm can be randomized, and the compressed representation must enable approximating distances up to a factor of 1 ± with probability 1/n O(1) .
Unfortunately, in the context of approximate nearest neighbor search, the above representations lead to sub-optimal results. The result from the last row of the table (from Indyk and Wagner (2017)) cannot be used to obtain provable bounds for nearest neighbor search, because the distance preservation guarantees hold only for pairs of points in the pointset X. 1 The second-to-last result (from Kushilevitz et al. (2000)) only estimates distances in a certain range; extending this approach to all distances would multiply the storage by a factor of log Φ. Finally, the representations obtained via a direct application of randomized dimensionality reduction (Johnson and Lindenstrauss (1984)) are also larger than the bound from Indyk and Wagner (2017) by almost a factor of log Φ.
In this paper we show that it is possible to overcome the limitations of the previous results and design a compact representation that supports (1 + )-approximate nearest neighbor search, with a space bound essentially matching that of Indyk and Wagner (2017). This constitutes the first reduction in the space complexity of approximate nearest neighbor below the "Johnson-Lindenstrauss bound". Specifically, we show the following. Suppose that we want the data structure to answer q approximate nearest neighbor queries in a d-dimensional dataset of size n, in which coordinates are represented by log Φ bits each. All q queries must be answered correctly with probability 1 -δ. (See Section 2 for the formal problem definition).
Theorem 1.1 For the all-nearest-neighbors problem, there is a sketch of size
The proof is given in Section 4. We also give a lower bound of Ω(n log(n)/ 2 ) for q = 1 and δ = 1/n O(1) (Section B), which shows that the first term in the above theorem is almost tight. Interestingly, the representation by itself does not return the (approximate) distance between the query point and the returned neighbor. Thus, we also consider the problem of estimating distances from a query point to all data points. In this setting, a result of Molinaro et al. (2013) shows that the Johnson-Lindenstrauss space bound is optimal when the number of queries is equal to the number of data points. However, in many settings, the number of queries is often substantially smaller than the dataset size. We give nearly tight upper and lower bounds (up to a factor of log(1/ )) for this problem, showing it is possible to smoothly interpolate between Indyk and Wagner (2017), which does not support out-of-sample distance queries, and the Johnson-Lindenstrauss bound.
Specifically, we show the following. Suppose that we want the data structure to estimate all cross-distances between a set of q queries and all points in X, all of which must be estimated correctly with probability 1 -δ (see Section 2 for the formal problem definition).
Theorem 1.2 For the all-cross-distances problem, there is a sketch of size
Note that the dependence per point on Φ is logarithmic, as opposed to doubly logarithmic in Theorem 1.1. We show this dependence is necessary, as per the following theorem.
Theorem 1.3 Suppose that d 1-ρ ≥ -2 log(nq/δ), Φ ≥ 1/ , and 1/n 0.5-ρ ≤ ≤ 0 for some constants ρ, ρ > 0 and a sufficiently small constant 0 . Then, for the all-cross-distances problem, any sketch must use at least
The proofs are given in Section 5 and Appendix C, respectively.
Practical variant Indyk et al. (2017) presented a simplified version of Indyk and Wagner (2017), which has slightly weaker size guarantees, but on the other hand is practical to implement and was shown to work well empirically. However, it did not provably support out-of-sample queries.
Our techniques in this paper can be adapted to their algorithm and endow it with such provable guarantees, while retaining its simplicity and practicality. We elaborate on this in Appendix D.
The starting point of our representation is the compressed tree data structure from Indyk and Wagner (2017). The structure is obtained by constructing a hierarchical clustering of the data set, forming a tree of clusters. The position of each point corresponding to a node in the tree is then represented by storing a (quantized) displacement vector between the point and its "ancestor" in the tree. The resulting tree is further compressed by identifying and post-processing "long" paths in the tree. The intuition is that a subtree at the bottom of such a path corresponds to a cluster of points that is "sufficiently separated" from the rest of the points (see Figure 1). This means that the data structure does not need to know the exact position of this cluster in order to estimate the distances between the points in the cluster and the rest of the data set. Thus the data structure replaces each long path by a quantized displacement vector, where the quantization error does not depend on the length of the path. This ensures that the tree does not have long paths, which bounds its total size. Unfortunately, this reasoning breaks down if one of the points is not known in advance, as it is the case for the approximate nearest neighbor problem. In particular, if the query point y lies in the vicinity of the separated cluster, then small perturbations to the cluster position can dramatically affect which points in the cluster are closest to y (see Figure 2 for an illustration).
In this paper we overcome this issue by maintaining extra information about the geometry of the point set. First, for each long path, we store not only the quantized displacement vector (which preserves the "global" position of the subtree with respect to the rest of the tree) but also the suffix of the path. Intuitively, this allows us to recover both the most significant bits and the least significant bits of points in the subtree corresponding to the "separated" clusters, which allows us to avoid cases as depicted in Figure 2. However, this intuition breaks down when the diameter of the cluster is much larger than the amount of "separation". Thus we also need to store extra information about the position of the subtree points. This is accomplished by storing a hashed representation of a representative point of the subtree (called "the center"). We note that this modification makes our data structure inherently randomized; in contrast, the data structure of Indyk and Wagner (2017) was deterministic.
Given the above information, the approximate nearest neighbor search is performed top down, as follows. In each step, we recover and enumerate points in the current subtree, some of which could be centers of "separated" clusters as described above. The "correct" center, guaranteed to contain an approximate nearest neighbor of the query point, is identified by its hashed value (if no hash match is found, then any center is equally good). Note that our data structure does not allow us to compute all distances from the query point y to all points in X (in fact, as mentioned earlier, this task is not possible to achieve within the desired space bound). Instead, it stores just enough information to ensure that the procedure never selects a "wrong" subtree to iterate on.
Lastly, suppose we also wish to estimate all distances from y to X. To this end, we augment each subtree with the distance sketches due to Kushilevitz et al. (2000) and Johnson and Lindenstrauss (1984). The former allows us to identify the cluster of all approximate nearest neighbors of y (whereas the above algorithm was only guaranteed to return one approximate nearest neighbor). The latter stores the approximate distance from that cluster. These are the smallest distances from y to X, which are the most challenging to estimate; the remaining distances can be estimated based on the hierarchical partition into well-separated clusters, which is already present in the sketch.
We formalize the problems in terms of one-way communication complexity. The setting is as follows. Alice has n data points, X = {x 1 , . . . , x n } ⊂ {-Φ . . . Φ} d , while Bob has q query points, Y = {y 1 , . . . , y q } ⊂ {-Φ . . . Φ} d , where 1 ≤ q ≤ n. Distances are Euclidean, and we can assume w.l.o.g. that d ≤ n.foot_2 Let , δ ∈ (0, 1) be given parameters. In the one-way communication model, Alice computes a compact representation (called a sketch) of her data points and sends it to Bob, who then needs to report the output. We define two problems in this model (with private randomness), each parameterized by n, q, d, Φ, , δ:foot_3
Problem 1 -All-nearest-neighbors: Bob needs to report a (1 + )-approximate nearest neighbor in X for all his points simultaneously, with probability 1 -δ. That is, for every j ∈ [q], Bob reports an index i j ∈ [n] such that
Our upper bound for this problem is stated in Theorem 1.1.
Problem 2 -All-cross-distancess: Bob needs to estimate all distances x i -y j up to distortion (1 ± ) simultaneously, with probability 1 -δ. That is, for every i ∈ [n] and j ∈ [q], Bob reports an estimate E(i, j) such that
Our upper and lower bounds for this problem are stated in Theorems 1.2 and 1.3.
In this section we describe the basic data structure (generated by Alice) used for all of our results.
The data structure augments the representation from Indyk and Wagner (2017), which we will now reproduce. For the sake of readability, the notions from the latter paper (tree construction via hierarchical clustering, centers, ingresses and surrogates) are interleaved with the new ideas introduced in this paper (top-out compression, grid quantization and surrogate hashing). Proofs in this section are deferred to Appendix A.
The sketch consists of an annotated hierarchical clustering tree, which we now describe with our modified "top-out compression" step.
We construct the inter-link hierarchical clustering tree of X: In the bottom level (numbered 0) every point is a singleton cluster, and level > 0 is formed from level -1 by recursively merging any two clusters whose distance is at most 2 , until no two such clusters are present. We repeat this until level log(2 √ dΦ) , even if all points in X are already joined in one cluster at a lower level. The following observation is immediate.
Notation Let T * denote the tree. For every tree node v, we denote its level by (v), its associated cluster by C(v) ⊂ X, and its cluster diameter by ∆(v). For a point x i ∈ X, let leaf(x i ) denote the tree leaf whose associated cluster is {x i }.
The degree of a node in T * is its number of children. A 1-path with k edges in T * is a downward path u 0 , u 1 , . . . , u k , such that (i) each of the nodes u 0 , . . . , u k-1 has degree 1, (ii) u k has degree either 0 or more than 1, (iii) if u 0 is not the root of T * , then its ancestor has degree more than 1.
For every node v denote Λ(v) := log(∆(v)/(2 (v) )). If v is the bottom of a 1-path with more than Λ(v) edges, we replace all but the bottom Λ(v) edges with a long edge, and annotate it by the length of the path it represents. More precisely, if the downward 1-path is u 0 , . . . , u k = v and k > Λ(v), then we connect u 0 directly to u k-Λ(v) by the long edge, and the nodes u 1 , . . . , u k-Λ(v)-1 are removed from the tree, and the long edge is annotated with length k -Λ(v).
The compressed tree has O(n log(1/ )) nodes.
We henceforth refer only to the compressed tree, and denote it by T . However, for every node v in T , (v) continues to denote its level before compression (i.e., the level where the long edges are counted according to their lengths). We partition T into subtrees by removing the long edges. Let F (T ) denote the set of subtrees.
Lemma 3.3 Let v be the bottom node of a long edge, and x, x ∈ C(v). Then x -x ≤ 2 (v) . Lemma 3.4 Let u be a leaf of a subtree in F (T ), and x, x ∈ C(u). Then x -x ≤ 2 (u) .
The purpose of annotating the tree is to be able to recover a list of surrogates for every point in X. A surrogate is a point whose location approximates x. Since we will need to compare x to a new query point, which is unknown during sketching, we define the surrogates to encompass a certain amount information about the absolute point location, by hashing a coarsened grid quantization of a representative point in each subtree.
Centers With every tree node v we associate an index c(v) ∈ [n] such that x c(v) ∈ C(v), and we call x c(v) the center of C(v). The centers are chosen bottom-up in T as follows. For a leaf v, C(v) contains a single point x i ∈ X, and we set c(v) = i. For a non-leaf v with children u
Ingresses Fix a subtree T ∈ F (T ). To every node u in T , except the root, we will now assign an ingress node, denoted in(u). Intuitively this is a node in the same subtree whose center is close to u, and the purpose is to store the location of u by its quantized displacement from that center (whose location will have been already stored, by induction).
We will now assign ingresses to all children of a given node v. (Doing this for every v in T defines ingresses for all nodes in T except its root.) Let u 1 , . . . , u k be the children of v, and w.l.o.g. c(v) = c(u 1 ). Consider the graph H v whose nodes are u 1 , . . . , u k , and u i , u j are neighbors if there are points x ∈ C(u i ) and x ∈ C(u j ) such that x -x ≤ 2 (v) . By the tree construction, H v is connected. We fix an arbitrary spanning tree τ (v) of H v which is rooted at u 1 .
For u 1 we set in(u 1 ) := v. For u i with i > 1, let u j be its (unique) direct ancestor in the tree τ (v). Let x ∈ C(u j ) be the closest point to C(u i ) in C(u j ). Note that in T there is a downward path from u j to leaf(x). Let u x be the bottom node in that path that belongs to T . (Equivalently, u x is the bottom node on that downward path that is reachable from u without traversing a long edge.) We set in(u i ) := u x .
Grid net quantization Assume w.l.o.g. that Φ is a power of 2. We define a hierarchy of grids aligned with {-Φ . . . Φ} d as follows. We begin with the single hypercube whose corners are (±Φ, . . . , ±Φ) d . We generate the next grid by halving along each dimension, and so on. For every γ > 0, let N γ be the coarsest grid generated, whose cell side is at most γ/ √ d. Note that every cell in N γ has diameter at most γ. For a point x ∈ R d , we denote by N γ [x] the closest corner of the grid cell containing it.
We will rely on the following fact about the intersection size of a grid and a ball; see, for example, Har-Peled et al. (2012).
Claim 3.5 For every γ > 0, the number of points in N γ at distance at most 2γ from any given point, is at most O(1) d .
Surrogates Fix a subtree T ∈ F (T ). With every node v in T we will now associate a surrogate s * (v) ∈ R d . Define the following for every node v in T :
otherwise.
The surrogates are defined by induction on the ingresses. Induction base: For the root v of T we set s * (v
Induction step: For a non-root v we denote the quantized displacement of c(v) from its ingress by η
Hash functions For every level in the tree, we pick a hash function H : N 2 → [m], from a universal family (Carter and Wegman (1979)), where
The O(1) term is the same constant from Claim 3.5 above. For every subtree root v, we store its hashed surrogate
). We also store the description of each hash function H for every level .
The sketch contains the tree T , with each node v annotated by its center c(v), ingress in(u), precision γ(v) and quantized displacement η(v) (if applicable). For subtree roots we store their hashed surrogate, and for long edges we store their length. We also store the hash functions {H }.
Lemma 3.7 The total sketch size is
As a preprocessing step, Alice can reduce the dimension of her points to O( -2 log(qn/δ)) by a Johnson-Lindenstrauss projection. She then augments the sketch with the projection, in order for Bob to be able to project his points as well. By Kane et al. (2011), the projection can be stored with O(log d + log(q/δ) • log log((q/δ)/ )) bits. This yields the sketch size stated in Theorem 1.1.
Remark Both the hash functions and the projection map can be sampled using public randomness. If one is only interested in the communication complexity, one can use the general reduction from public to private randomness due to Newman (1991), which replaces the public coins by augmenting O(log(ndΦ)) bits to the sketch (since Alice's input has size O(ndΦ) bits). The bound in Theorem 1.1 then improves to O n log n•log(1/ ) 2 + log log Φ + log q δ + log Φ bits, and the bound in Theorem 1.2 improves to O n 2 log n • log(1/ ) + log(dΦ) log q δ bits. However, that reduction is non-constructive; we state our bounds so as to describe explicit sketches.
We now describe our approximate nearest neighbor search query procedure, and prove Theorem 1.1. Suppose Bob wants to report a (1 + )-approximate nearest neighbor in X for a point y ∈ Y .
1. Start at the subtree T ∈ F (T ) that contains the root of T .
2. Recover all surrogates {s * (v) : v ∈ T }, by the subroutine below.
3. Let v be the leaf of T that minimizes y -s * (v) .
4. If v is the head of a long edge, recurse on the subtree under that long edge. Otherwise v is a leaf in T , and in that case return c(v).
Subroutine Recover Surrogates: This is a subroutine that attempts to recover all surrogates {s * (v) : v ∈ T } in a given subtree T ∈ F (T ), using both Alice's sketch and Bob's point y.
Observe that to this end, the only information missing from the sketch is the root surrogate s * (r), which served as the induction base for defining the rest of the surrogates. The induction steps are fully defined by (v), in(v), γ(v), and η(v), which are stored in the sketch for every node v = r in the subtree. The missing root surrogate was defined as s * (r) = N 2 (r) [x c(r) ]. Instead, the sketch stores its hashed value H (r) (N 2 (r) [x c(r) ]) and the hash function H (r) . 4The subroutine attempts to reverse the hash. It enumerates over all points p ∈ N 2 (r) such that p -y ≤ 2 • 2 (r) . For each p it computes H (r) (p). If H (r) (x c(r) ) = H (r) (p) then it sets s * (r) = p and recovers all surrogates accordingly. If either no p, or more than one p, satisfy H (r) (x c(r) ) = H (r) (p), then it proceeds with s * (r) set to an arbitrary point (say, the origin in R d ).
Analysis. Let r 0 , r 1 , . . . be the roots of the subtrees traversed on the algorithm. Note that they reside on a downward path in T .
Let t be the smallest such that r t satisfies x c(rt) -y > 2 (rt) . (The algorithm does not identify t, but we will use it for the analysis.) Lemma 4.2 With probability 1 -δ/q, for every i = 0, . . . , t -1 simultaneously, the subroutine recovers s * (r i ) correctly as N 2 (r) [x c(r) ]. (Consequently, all surrogates in the subtree rooted by r i are also recovered correctly.)
Proof Fix a subtree T ∈ F (T ) rooted in r, that satisfies y -x c(r) ≤ 2 (r) . Since x c(r)s * (r) ≤ 2 (r) (by Lemma 3.6), we have y -s * (r) ≤ 2 • 2 (r) . Hence the surrogate recovery subroutine tries s * (r) as one of the hash pre-image candidates, and will identify that H (r) (s * (r)) matches the hash stored in the sketch. Furthermore, by Claim 3.5, the number of candidates is at most O(1) d . Since the range of
• q/δ, then with probability 1 -δ/(q log(2 √ dΦ)) there are no collisions, and s * (r) is recovered correctly. The lemma follows by taking a union bound over the first t subtrees traversed by the algorithm, i.e. those rooted by r i for i = 0, 1, . . . , t -1. Noting that t is upper-bounded by the number of levels in the tree, log(2 √ dΦ), we get that all the s * (r i )'s are recovered correctly simultaneously with probability 1 -δ/q.
From now on we assume that the event in Lemma 4.2 succeeds, meaning in steps 0, 1, . . . , t -1, the algorithm recovers all surrogates correctly. We henceforth prove that under this event, the algorithm returns a (1 + )-approximate nearest neighbor of y. In what follows, let x * ∈ X be a fixed true nearest neighbor of y in X.
Lemma 4.3 Let T ∈ F (T ) be a subtree rooted in r, such that x * ∈ C(r). Let v a leaf of T that minimizes y -s * (v) . Then either x * ∈ C(v), or every z ∈ C(v) is a (1 + O( ))-approximate nearest neighbor of y.
Proof Suppose w.l.o.g. by scaling that < 1/6. If x * ∈ C(v) then we are done. Assume now that x * ∈ C(u) for a leaf u = v of T . Let := max{ (v), (u)}. We start by showing that y -x * > 1 4 • 2 . Assume by contradiction this is not the case. Since u is a subtree leaf and x * ∈ C(u), we have x * -x c(u) ≤ 2 by Lemma 3.4. We also have x c(u) -s * (u) ≤ 2 by Lemma 3.6. Together, y -s * (u) ≤ ( 1 4 + 2 )2 . On the other hand, by the triangle inequality, y -s * (v) ≥ x * -x c(v) -y -x * -x c(v) -s * (v) . Noting that x * -x c(v) ≥ 2 (by Lemma 3.1, since x * and x c(v) are separated at level ), y -x * ≤ 1 4 • 2 (by the contradiction hypothesis) and x c(v) -s * (v) ≤ 2 (by Lemma 3.6), we get y -s
. This contradicts the choice of v.
The lemma now follows because for every z ∈ C(v),
where ( 1) and ( 3) are by the triangle inequality, ( 2) is since y -s * (v) ≤ y -s * (u) by choice of v, (4) is by Lemmas 3.4 and 3.6, and ( 5) is since we have shown that y -x * > 1 4 • 2 . Therefore z is a (1 + 16 )-approximate nearest neighbor of y.
Proof of Theorem 1.1. We may assume w.l.o.g. that is smaller than a sufficiently small constant. Suppose that the event in Lemma 4.2 holds, hence all surrogates in the subtrees rooted by r 0 , r 1 , . . . , r t-1 are recovered correctly. We consider two cases. In the first case, x * / ∈ C(r t ). Let i ∈ {1, . . . , t} be the smallest such that x * / ∈ C(r i ). By applying Lemma 4.3 on r i-1 , we have that every point in C(r i ) is a (1 + O( ))-approximate nearest neighbor of y. After reaching r i , the algorithm would return the center of some leaf reachable from r i , and it would be a correct output.
In the second case, x * ∈ C(r t ). We will show that every point in C(r t ) is a (1 + O( ))approximate nearest neighbor of y, so once again, once the algorithm arrives at r t it can return anything. By Lemma 3.3, every x ∈ C(r t ) satisfies
x -x * ≤ 2 (rt) .
(6)
In particular, x c(rt) -x * ≤ 2 (rt) . By definition of t we have x c(rt) -y > 2 (rt) . Combining the two yields y - rt) . Combining this with eq. ( 6), we find that every x ∈ C(r t ) satisfies x -x * ≤ 1-y -x * , and hence y -x ≤ (1 + 2 ) y -x * (for ≤ 1/2). Hence x is a (1 + 2 )-nearest neighbor of y.
The proof assumes the event in Lemma 4.2, which occurs with probability 1 -δ/q. By a union bound, the simultaneous success probability of the q query points of Bob is 1 -δ as required.
We now prove theorem 1.2. To this end, we augment the basic sketch from Section 3 with additional information, relying on the following distance sketches due to Achlioptas (2001) (following Johnson and Lindenstrauss (1984)) and Kushilevitz et al. (2000). Lemma 5.2 (Kushilevitz et al. (2000)) Let R > 0 be fixed and let , δ > 0. There is a randomized map sk R of vectors in R d into O( -2 log(1/δ )) bits, with the following guarantee. For every x, y ∈ R d , given sk R (x) and sk R (y), one can output the following with probability 1 -δ :
We augment the basic sketch from Section 3 as follows. We sample a matrix M from Lemma 5.1, with δ = δ/q. In addition, for every level in the tree T , we sample a map sk 2 from Lemma 5.2, with δ = δ/(q log(2 √ dΦ)). For every subtree root r in T , we store M x c(r) and sk 2 (r) (x c(r) ) in the sketch. Let us calculate the added size to the sketch:
Since there are O(n) subtree roots (cf. Lemma 3.7), storing M x c(r) for every r adds O(nd dΦ) = O( -2 n log(q/δ) log(dΦ)) bits to the sketch. In addition we store the matrix M , which takes O(d d) bits to store, which is dominated by the previous term.
• By Lemma 5.2, each sk 2 (r) (x c(r) ) adds O( -2 log(q log(2 √ dΦ)/δ)) bits to the sketch, and as above there are O(n) of these. In addition we store the map sk 2 (r) for every . Each map takes poly(d, log Φ, log(q/δ), 1/ ) bits to store.
In total, we get the sketch size stated in Theorem 1.2. Next we show how to compute all distances from a new query point y.
Query algorithm. Given the sketch, an index k ∈ [n] of a point in X, and a new query point y, the algorithm needs to estimate y -x k up to 1 ± O( ) distortion. It proceeds as follows.
1. Perform the approximate nearest neighbor query algorithm from Section 4. Let r 0 , r 1 , . . . be the downward sequence of subtree roots traversed by it.
2. For each r j , estimate from the sketch whether y -x c(r j ) ≤ 2 (r j ) . This can be done by Lemma 5.2, since the sketch stores sk 2 (r j ) (x c(r j ) ) and also the map sk 2 (r j ) , with which we can compute sk 2 (r j ) (y).
3. Let t be the smallest j that satisfies y-x c(r j ) > 2 (r j ) according the estimates of Lemma 5.2. (This attempts to recover from the sketch the same t as defined in the analysis in Section 4.)
4. Let t k ∈ {0, . . . , t} be the maximal such that x k ∈ C(r t k ).
(In words, r t k is the root of the subtree in which x k and y "part ways".)
5. If t k = t, return M y -M x c(rt) . Note that M and M x c(rt) are stored in the sketch.
6. If t k < t, let v k be the bottom node on the downward path from r t k to leaf(x k ) that does not traverse a long edge. Return y -s * (v k ) .
Analysis. Fix a query point y. Define the "good event" A(y) as the intersection of the following:
1. For every subtree root r j traversed by the query algorithm above, the invocation of Lemma 5.2 on sk 2 (r j ) (x c(r j ) ) and sk 2 (r j ) (y) succeeds in deciding whether y -x c(r j ) ≤ 2 (r j ) . Specifically, this ensures that y -x c(r j ) ≤ 2 (r j ) for every j < t, and y -x c(rt) ≥ (1 -)2 (rt) .
Recalling that we invoked the lemma with δ = δ/(q log(2 √ dΦ)), we can take a union bound and succeed in all levels simultaneously with probability 1 -δ/q.
2. M y -M x c(rt) = (1 ± ) y -x c(rt) . By Lemma 5.1 this holds with probability 1 -δ/q.
Altogether, A(y) occurs with probability 1 -O(δ/q). Lemma 5.3 Conditioned on A(y) occuring, with probabiliy 1-δ/q, Lemma 4.2 holds. Namely, the query algorithm correctly recovers all surrogrates in the subtrees rooted by r j for j = 0, 1, . . . , t-1.
Proof The proof of Lemma 4.2 in Section 4 relied on having y -x c(r j ) ≤ 2 (r j ) for every j < t. Conditioning on A(y) ensures this holds.
Proof of Theorem 1.2. Let A * (y) denote the event in which both A(y) occurs and the conclusion of Lemma 4.2 occurs. By the above lemma, A * (y) happens with probability 1 -O(δ/q). From now on we will assume that A * (y) occurs, and conditioned on this, we will show that the distance from y to any data point can be deterministically estimated correctly. To this end, fix k ∈ [n] and suppose our goal is to estimate y -x k . Let t k and v k be as defined by the distance query algorithm above. We handle the two cases of the algorithm separately.
Case I: t k = t. This means x k ∈ C(r t ). By Lemma 3.3 we have x k -x c(rt) ≤ 2 (rt) . By the occurance of A * (y) we have y -x c(rt) > (1 -)2 (rt) . Together, y -
. This means that y -x c(rt) is a good estimate for y -x k . Since A * (y) occurs, it holds that M y -M x c(rt) = (1 ± ) y -x c(rt) , hence M y -M x c(rt) is also a good estimate for y -x k , and this is what the algorithm returns.
Case II: t k < t. Let T t k be the subtree rooted by r t k . By the occurance of A * (y), all surrogates in T t k are recovered correctly, and in particular s * (v k ) is recovered correctly. By Lemma 3.6 we have
, and by Lemma 3.4 (noting that
Let v be the leaf in T t k that minimizes y -s * (v) (over all leaves of T t k ). Equivalently, v is the top node of the long edge whose bottom node is r t k +1 . Let := max{ (v), (v k )}. By choice of t k we have v = v k , hence the centers of these two leaves are separated already at level , hence x c(v k ) -x c(v) ≥ 2 by Lemma 3.1. By two applications of Lemma 3.6 we have
, which was shown above, yields
Conclusion: Combining both cases, we have shown that for any query point y, all distances from y to X can be estimated correctly with probability 1 -O(δ/q). Taking a union bound over q queries, and scaling δ and appropriately by a constant, yields the theorem.
δ < 1/n 2 . By a union bound over all i, j ∈ [n] we can recover all of x 1 , . . . , x n simultaneously, and the theorem follows.
Definition C.3 (Augmented Indexing) In the Augmented Indexing problem AugInd(k, δ), Alice gets a vector A with k entries, whose elements are entries of a universe of size 20/δ. Bob gets an index i ∈ [k], an element e, and the elements A(i ) for every i < i. Bob needs to decide whether e = A(i), and succeed with probability 1 -δ.
Jayram and Woodruff (2013) give a one-way communication lower bound of Ω(k log(1/δ)) for this problem. The main component in Molinaro et al. (2013) is a modified one-way communication model, in which the protocol is allowed to abort with a substantially larger (constant) probability than it is allowed to err. We will refer to it simply as the abortion model and refer to Molinaro et al. (2013) for the exact definition (which we will not require). They prove the same lower bound for Augmented Indexing.
Lemma C.4 (informal) In the abortion model, the one-way communication complexity of AugInd(k, δ) is Ω(k log(1/δ)).
We start by defining a variant of augmented indexing that will be suitable for out purpose.
Definition C.5 In the Matrix Augmented Indexing problem M atAugInd(k, m, δ), Alice gets a matrix A of order k × m, whose entries are elements of a universe of size 1/δ. Bob gets indices i ∈ [k] and j ∈ [m], an element e, and the elements A(i, j ) for every j < j . Bob needs to decide whether e = A(i, j), and succeed with probability 1 -δ.
This problem is clearly at least as difficult as AugInd(km, δ) from Definition C.3, since in the latter Bob gets more information (namely, if we arrange the vector A in AugInd(km, δ) as a k × m matrix, then Bob gets all entries of A which lexicographically precede A(i, j)). We get the following immediate corollary from Lemma C.4. Corollary C.6 In the abortion model, the one-way communication complexity of M atAugInd(k, m, δ) is Ω(km log(1/δ)). Molinaro et al. (2013) reformulate Augmented Indexing so that Alice's input is a set instead of vector. Similary, we reformulate Matrix Augmented Indexing as follows.
Definition C.7 Let m > 0 and k > 0 be integers, and δ ∈ (0, 1). Partition the interval [m/δ] into m intervals I 1 , . . . , I m of size 1/δ each.
In the Augmented Set List problem AugSetList(k, m, δ), Alice gets a list of subsets S 1 , . . . , S k ⊂ [m/δ], such that each S i has size exactly m and contains exactly one element from each interval I 1 , . . . , I m . Bob gets an index i ∈ [k], an element e ∈ [m/δ] and a subset T of S i that contains exactly the elements of S i that are smaller than e. Bob needs to decide whether e ∈ S i , and succeed with probability at least 1 -δ.
The equivalence to Matrix Augmented Indexing is not hard to show; the details are similar to Molinaro et al. (2013) and we omit them here. By the equivalence, we get the following corollary from Corollary C.6. this pruning rule to the quadtree of Indyk et al. (2017) (instead of their "bottom-out" rule) is sufficient to obtain a sketch that provably supports out-of-sample approximate nearest neighbor queries. Thus, the sketching algorithm is nearly unchanged.
We remark that in Section 3 we introduced two additional modifications: grid-net quantization and surrogate hashing. These were required in order to prove Theorems 1.1 and 1.2, but in the framework of Indyk et al. (2017) they turn out to be unnecessary: grid-net quantization is already organically built into the quadtree approach of Indyk et al. (2017), and surrogate hashing only served to avoid a O(log log n) factor in the sketch size (see footnote 4), but in Indyk et al. (2017) this factor is tolerated anyway.
For completeness, let us briefly describe the sketching algorithm of Indyk et al. (2017) (the reader is referred to that paper for more formal details), with our modification. To this end, set Λ = log 16d 1.5 log Φ δ .
Suppose w.l.o.g. that Φ is a power of 2. The sketching algorithm proceeds in three steps:
1. Random shifted grids: Impose a randomly shifted enclosing hypercube on the data points X.
More precisely, choose a uniformly random shift σ ∈ {-Φ, . . . , Φ} d , and set the enclosing hypercube to be H
Since X ⊂ {-Φ, . . . , Φ} d , it is indeed enclosed by H. We then half H along every dimension to create a finer grid with 2 d cells, and proceed so (recursively halving every cell along every dimension) to create a hierarchy of nested grids, with log(4Φ) + Λ hierarchy levels. The top level is numbered Φ + 2, which is the log the side length of H, and the next levels are decrementing, so that the grid cells in level have side length 2 .
2. Quadtree construction: Construct the quadtree which is naturally associated with the nested grids: the root corresponds to H, its children correspond to the non-empty cells of the next grid in the hierarchy (a cell is non-empty if it contains a point in X), and so on. Each tree edge is annotated by a bitstring of length d, that marks whether the child cell coincides with the bottom half (bit 0) or the top half (bit 1) of the parent cell in each dimension.
3. Middle-out compression: For every path of degree-1 tree nodes whose length is more than 2Λ, we keep its top Λ and bottom Λ, and replace its remaining middle portion by a long edge. This removes the edge annotations of the middle section (this achieving compression). We label each long edge with the length of the path it replaces.
In the remainder of this section we prove the following.
Theorem D.1 The above algorithm, with the above setting of Λ, runs in time Õ(nd(log Φ + Λ)) and produces a sketch for the all-nearest-neighbors problem, whose size in bits is
The sketch size is the same as in Indyk et al. (2017), except that we keep at most 2Λ instead of Λ nodes per 1-path, which increases the sketch size by only a factor of 2.
We start with some useful properties of the above sketch, which are analogous to lemmas from in Section 3. In the notation below, for a node v in the quadtree, C(v) denotes the subset of points in X that are contained in the grid cell associated with v. As in Section 3, the quadtree is partitioned into a set F (T ) of subtrees by removing the long edges.
Lemma D.2 (analog of Lemma 3.1) For every point x ∈ X, with probability 1 -δ, the following holds. If z ∈ R d is any point outside the grid cell that contains x in level of the quadtree, then
Proof The setting of Λ is such that with probability 1 -δ, in every level of the quadtree, the grid cell that contains x also contains the ball at radius 8 -1 • 2 -Λ √ d around x. (This property is known as "padding".) The lemma is just a restatement of this property. See Lemma 1 and Equation (1) in Indyk et al. (2017) for details.
Lemma D.3 (analog of Lemmas 3.3, 3.4, 3.6) Let v be a node in the quadtree, and x, x ∈ R d points contained in the grid cell associated with v. Then x -x ≤ 2 (v) √ d.
Proof The grid cell associated with v is a hypercube with side 2 (v) and diameter 2 (v) √ d.
Before proceeding let us make the following point about the quadtree.
Claim D.4 For every leaf v of the quadtree, C(v) contains a single point of X, and v is the bottom of a 1-path of length at least Λ.
Proof Refining the quadtree grid hierarchy for log(4Φ) levels ensures that each grid cell contains at most one point from X, and refining for Λ additional levels ensures that each leaf is the bottom of a 1-path of length at least Λ.
Claim D.5 Every subtree leaf in the quadtree is the bottom of a 1-path of length at least Λ.
Proof If v is a leaf of the quadtree, this follows from Claim D.4. Otherwise this follows from middle-out compression.
Next we define centers and surrogates. Centers c(v) are chosen similarly to Section 3. The surrogate s * (v) of every tree node v is simply defined to be the "bottom-left" (i.e. minimal in all dimensions) corner of the grid cell associated with v.
Finally, we can describe the query algorithm and complete its analysis. Let y be a query point for which we need to report an approximate nearest neighbor from the sketch. The query algorithm is the same as in Section 4: starting with the subtree that contains the quadtree root, it recovers the surrogates in the current subtree and chooses the subtree v whose surrogate is the closest to y. If v is a quadtree leaf, its center is returned as the approximate nearest neighbor. Otherwise, the algorithm proceeds by recursion on the subtree under v.
The difference is in the way we recover the surrogates of a given subtree. In Section 4 this was done using the surrogate hashes. Here we will use a simpler, deterministic surrogate recovery subroutine. Let s * (H) ∈ R d the surrogate of the quadtree root. (We store this point explicitly in the sketch, and it will be convenient to think of it w.l.o.g. as the the origin in R d .) As observed in Indyk et al. (2017), for every tree node v, if we concatenate the bits annotating the edges on the path from the root to v, we get the binary expansion of the point s * (H) + s * (v). Therefore, we can recover s * (v) from the sketch, as long as the path from the root to v does not traverse a long edge.
If the path to v contains long edges (and thus missing bits in the binary expansion of s * (v)), the algorithm completes these bits from the binary expansion of y. Let r 0 , r 1 , . . . be the subtree roots traversed by the algorithm, and let T 0 , T 1 , . . . be the corresponding subtrees. Let t be the smallest such that the algorithm does not recover the surrogates in T t correctly (because the bits missing on the long edge connecting T t-1 to T t are not truly equal to those of y). As in Section 4, the query algorithm does not know t (it simply always assumes that the bits of y are the correct missing ones), but we will use it for analysis. Note that by definition of t, all surrogates in the subtrees rooted at r 0 , . . . , r t-1 are recovered correctly. Thus, the event from Lemma 4.2 holds deterministically.
Proof of Theorem D.1 Let x * ∈ X be a fixed true nearest neighbor of y in X (chosen arbitrarily if there is more than one). We shall assume that the event in Lemma D.2 occurs for x * . (11) where ( 7) and ( 9) are by the triangle inequality, ( 8) is since y -s * (v) ≤ y -s * (u) by choice of v, (10) is by applying Lemma D.3 to each of the last four summands, and ( 11) is since we have shown that y -x * > -1 2 √ d. Therefore z is a (1 + 4 )-approximate nearest neighbor of y.
Now we prove that the query algorithm returns an approximate nearest neighbor for y. We may assume w.l.o.g. that is smaller than a sufficiently small constant. We consider two cases. In the first case, x * / ∈ C(r t ). Let i ∈ {1, . . . , t} be the smallest such that x * / ∈ C(r i ). By applying Lemma D.6 on r i-1 , we have that every point in C(r i ) is a (1 + O( ))-approximate nearest neighbor of y. After reaching r i , the algorithm would return the center of some leaf reachable from r i , and it would be a correct output.
In the second case, x * ∈ C(r t ) contains a true nearest neighbor of y. We will show that every point in C(r t ) is a (1 + O( ))-approximate nearest neighbor of y, so once again, once the algorithm arrives at r t it can return anything. By definition of t, we know that y does not reside in the grid cell associated with r t . Since y does reside in that cell, we have y -x * ≥ 8 -1 2 (rt)-Λ √ d by Lemma D.2. On the other hand, by Claim D.5, r t is the bottom of a 1-path of length at least Λ, and therefore any two points in C(r t ) are contained in the same grid cell at level (r t ) -Λ, whose diameter is 2 (rt)-Λ √ d. In particular, for every x ∈ C(r t ) we have x -x * ≤ 2 (rt)-Λ √ d ≤ 1 8 y -x * . Altogether we get y -x ≤ y -x * + x * -x ≤ (1 + 1 8 ) y -x * , so x ∈ C(r t ) is a (1 + )-approximate nearest neighbor of y in X.
The proof assumes the event in Lemma D.2 holds for x * , which happens with probability 1 -δ. To handle q queries, we can scale δ down to δ/q and take a union bound over the q nearest neighbors of the q query points
c 2018 P. Indyk & T. Wagner.
We note, however, that a simplified version of this method, described inIndyk et al. (2017), was shown to have good empirical performance for nearest neighbor search.
Any N -point Euclidean metric can be embedded into N -1 dimensions.
Throughout we use [m] to denote {1, . . . , m}, for an integer m > 0.
Note that fully storing the root surrogates is prohibitive: N 2 (r) has Θ(2√dΦ/2 (r) ) d cells, hence storing a cell ID takes Ω(d log d) bits, and since there can be Ω(n) subtree roots, this would bring the total sketch size to Ω(nd log d).