We take a first step towards a rigorous asymptotic analysis of graph-based approaches for finding (approximate) nearest neighbors in high-dimensional spaces, by analyzing the complexity of (randomized) greedy walks on the approximate near neighbor graph. For random data sets of size n = 2 o(d) on the d-dimensional Euclidean unit sphere, using near neighbor graphs we can provably solve the approximate nearest neighbor problem with approximation factor c > 1 in query time n ρq+o(1) and space n 1+ρs+o(1) , for arbitrary ρ q , ρ s ≥ 0 satisfying Graph-based near neighbor searching is especially competitive with hash-based methods for small c and near-linear memory, and in this regime the asymptotic scaling of a greedy graph-based search matches the recent optimal hash-based trade-offs of Andoni-Laarhoven-RazenshteynWaingarten [6]. We further study how the trade-offs scale when the data set is of size n = 2 Θ(d) , and analyze asymptotic complexities when applying these results to lattice sieving. Keywords and phrases (approximate) nearest neighbor problem, near neighbor graphs, localitysensitive hashing, locality-sensitive filters, similarity search Digital Object Identifier 10.4230/LIPIcs.TBD.2018.1 Nearest neighbor searching. A key computational problem in various areas of research, such as machine learning, pattern recognition, data compression, and decoding [17, 27, 28, 41, 34, 49], is the nearest neighbor problem: given a d-dimensional data set D ⊂ R d of cardinality n, design a data structure and preprocess D in an efficient way such that, when later given a query vector q ∈ R d , we can quickly find the nearest point to q in D (e.g. under the Euclidean metric). Since the exact (worst-case) version of this problem suffers from the "curse of dimensionality" [31], a common relaxation of this problem is the approximate nearest neighbor (ANN) problem: given that the exact nearest neighbor in the data set D lies at distance at most r from q, design an efficient algorithm that finds an element p ∈ D at distance at most c · r from q, for a given approximation factor c > 1. We will refer to this problem as (c, r)-ANN. Since a naive linear search trivially leads to an O(d · n) time algorithm for solving both the exact and approximate near neighbor problems, the goal is to design a data structure for which queries can be accurately answered in time n ρ+o(1) with ρ < 1. Here we will only consider scenarios where d scales with n -for fixed d, it is well-known that one can achieve arbitrarily small query exponents ρ = o(1) [9]. We further assume w.l.o.g. that n ≥ 2 O(d/ log d) -in case d is larger, we can first perform a random projection to reduce the effective dimensionality of the data set, while maintaining inter-point distances [32]. [31, 24, 3, 5]. Using hash functions with the property that nearby vectors are more likely to be mapped to the same hash value, one builds several hash tables with buckets containing vectors with the same hash value. Queries q are then processed by computing h(q), looking up vectors p ∈ D with the same hash value h(p) = h(q), and considering these vectors as candidate near neighbors, for each of the precomputed hash tables. Although a large number of randomized hash tables is often required to obtain a good recall rate, doing these look-ups in all the hash tables is often still considerably faster than a linear search through the list. Whereas LSH requires each point to be mapped to exactly one hash bucket in each hash table, the recent locality-sensitive filtering (LSF) [13, 6, 22] relaxes this condition: for each hash filter and each point in the data set, we independently decide whether we add this point to this filter bucket or not. This may mean that some points are added to more filters than others, and filters do not necessarily form a partitioning of the space. Queries are answered by considering filters matching the query, and going through all vectors in these buckets. For the special case of the approximate nearest neighbor problem where the data set lies on the sphere, many efficient partition-based methods are known based on using random hyperplanes [20], regular polytopes [50, 4, 33, 37], and spherical caps [3, 5, 13, 35, 6]. For random data sets of size n = 2 o(d) , both cross-polytope LSH [4] and spherical LSF [13] achieve the optimal asymptotic scaling of the query complexity for hash-based methods. Spherical LSF further offers optimal time-space trade-offs between the query and update/space complexities [6], while cross-polytope LSH seems to perform better in practice [4, 48, 10]. No optimality results are known for data sets of size n = 2 Θ(d) , but spherical LSF provably outperforms cross-polytope LSH in some regimes [13]. A different approach to the near neighbor problem involves constructing nearest neighbor graphs, where vertices correspond to points p ∈ D of the data set, and an edge between two vertices indicates that these points are approximate near neighbors [19, 29, 43, 46, 21, 23, 26, 30, 51]. Given a query q, one starts at an arbitrary node p ∈ D, and repeatedly attempts to find vertices p , connected to p in the graph through an edge, which are closer to q than the current candidate near neighbor p. When this process terminates, the resulting vector is either a local or a global minimum, i.e. a false positive or the true nearest neighbor to q. If the graph is sufficiently well-connected, we may hope to solve the (A)NN problem with high probability in one iteration -otherwise we might start over with a new random p ∈ D, and hope for success in a reasonable number of attempts. Compared to LSH and LSF, which often require storing quite some auxiliary data describing the hash tables/filters, and for which the cost of computing hashes or finding appropriate filters is commonly non-negligible, the nearest neighbor graph approach has much less overhead: for each vector p ∈ D, one only has to store its nearest neighbors in a list, and look-ups require no additional computations besides comparisons between the query q and data points p ∈ D in these lists to find nearer neighbors. In practice, graph-based approaches may therefore be more efficient than hash-based methods even if asymptotic analyses suggest otherwise, purely due to the low overhead of graph-based methods. Besides the standard nearest neighbor graph approach of connecting each vertex to its nearest neighbors [26, 25], various heuristic graph-based methods are further known based on adding connections in the graph between points which are not necessaily near neighbors [47, 40, 18]. This might for instance involve including several long-range, deep links in the graph between distant points, to guarantee that every pair of nodes is connected Thijs Laarhoven 1:3 through a short path [40]. Using hierarchical graphs [39, 18] where vertices are partitioned in several layers further seems to aid the performance of graph-based methods, although again these improvements appear to be purely heuristic. Comparison of different methods. To find out which method for finding nearest neighbors in high-dimensional spaces is objectively the best, an obvious approach would be to implement these methods, test them against realistic data sets, and compare their concrete performance. Various libraries with implementations of near neighbor methods are openly available online [16, 48, 44, 25, 18], and recently Aumüller-Bernhardsson-Faithfull presented a thorough comparison of different methods for nearest neighbor searching on various commonly used data sets and distance metrics [15, 10]. Their final conclusions include that the LSH-based FALCONN and the graph-based NMSLib and KGraph currently seem to be the most competitive methods for their considered data sets. Practical comparisons clearly have various drawbacks, as the practical performance often depends on many additional variables, such as specific properties of the data set and the level of optimization of the implementation -better results on certain data sets may not always translate well to other data sets with further optimized implementations. Moreover, some methods may scale better as the dimensionality and size of the data set increases, and it is hard to accurately predict asymptotic behavior from practical experiments. A second approach for comparing different methods would be to look at their theoretical, proven asymptotic performance as the size of the data set n and the dimension d tend to infinity. Tight bounds on the performance would allow us to extrapolate to arbitrary data sets, but for many algorithms obtaining such tight asymptotic bounds appears challenging. Although for partition-based methods, by now the asymptotic performance seems to be reasonably well understood, graph-based algorithms are mostly based on unproven heuristics, and are not as well understood theoretically. This is particularly disconcerting due to the efficiency of certain graph-based approaches, and so a natural question is: how well do graph-based approaches hold up against partition-based methods in high dimensions? Is it just the low overhead of graph-based methods that allows them to compete with hash-based approaches? Or will these graph-based methods remain competitive even for huge data sets? Heuristic methods made theoretical. We further remark that in the past, theoretical analyses of heuristic near neighbor methods have not only contributed to a better understanding of these methods, but also to make these methods more practical. Cross-polytope LSH, which is used in FALCONN [48], was originally proposed as a fast heuristic method with no proven asymptotic guarantees [50]; only later was it discovered that this method is theoretically superior to other methods as well [4, 33], and can be made even more practical. Recently also for hypercube LSH [50] improved theoretical guarantees were obtained [37], and the heuristic LSH forest approach [12] was also "made theoretical" with provable performance guarantees in high dimensions [8]. The goals of a theoretical analysis of graph-based methods are therefore twofold: to understand their asymptotic performance better, and to find ways to further improve these methods in practice. We take a first step towards a better theoretical understanding of graph-based approaches for the (approximate) nearest neighbor problem, by rigorously analyzing the asymptotic performance of the basic greedy nearest neighbor graph approach. We show that for random data sets on the Euclidean unit sphere and for arbitrary approximation factors c > 1, this Graph-based time-space trade-offs for approximate near neighbors method provably achieves asymptotic query exponents ρ < 1. We further show how to obtain efficient time-space trade-offs, by making the related near neighbor graph either more connected (more space, better query time) or less connected (less space, worse query time). Sparse data sets. In the case the data set on the unit sphere 1 has size n = 2 o(d) , and an unusually near neighbor lies at distance r = √ 2/c, the trade-offs we obtain for finding such a close vector to a random query vector are governed by the following relation. Theorem 1 (Time-space trade-offs for sparse data). For c > 1 and ρ q , ρ s ≥ 0 satisfying there exists a graph-based (c, r)-ANN data structure for data sets of size n = 2 o(d) on the sphere using space n 1+ρs+o(1) and query time n ρq+o(1) . Minimizing the query complexity in this asymptotic analysis corresponds to setting ρ s = 1 2 , in which case ρ q = c 2 /(2c 2 − 1). Note that, unlike in various hash-based constructions, there is a natural limit to the maximum space complexity of graph-based approaches: we cannot store more than n neighbors per vertex. Our analysis however suggests that when doing a greedy search in the graph, storing more than √ n neighbors per vertex does not further improve the query complexity, compared to starting over at a random new vertex. To compare the above trade-offs with hash-based results, recall that in [6] the authors obtained hash-based time-space trade-offs defined by the following inequality: Although in most cases the optimal 2 hash-based trade-offs from (3) are strictly superior to the graph-based trade-offs from Theorem (1), we remark that in the regime of small approximation factors c ≈ 1 and near-linear space ρ s ≈ 0, i.e. when there is no unusually near neighbor and we wish to use only slightly more space than is required for storing the input list, both inequalities above translate to: Here o(1) vanishes as ρ s → 0 and c → 1. So for truly random instances without any planted, unusually near neighbors, and when using a limited amount of memory, graph-based methods are asymptotically equally powerful for finding (approximate) nearest neighbors as optimal hash-based methods. In other words, in this regime graph-based approaches will remain competitive with hash-based methods even when the data sets become very large, and the dimensionality further increases. On the negative side, our analysis suggests that when there is an unusually near (planted) neighbor to the query, or when we are able to use much more space than the amount required to store the data set, the best known hash-based approaches are superior to the basic graph-based method analyzed in this paper. This could be caused either by our analysis not being tight, the considered algorithm not being as optimized, or due to graph-based 1 Note that the near neighbor problem on the Euclidean unit sphere is of particular interest due to the reduction from the near neighbor problem in all of R d (under the 2-norm) to solving the spherical case [7]. Furthermore, using standard reductions the results for the 2-norm translate to results for R d with the 1-norm as well. 2 Within a certain probing model, the hash-based trade-offs from (3) were proven to be optimal in [6]. approaches simply not being able to profit as much from such unusual circumstances. Note again that hash-based approaches are able to effectively use very large amounts of space, with a large number of fine-grained hash tables/partitions, whereas graph-based methods seem limited by using at most n 2 space. We therefore conjecture that the worse asymptotic performance for "unusual" problem instances is inherent to graph-based methods. Dense data sets. For settings where the data set consists of n = 2 Θ(d) points drawn uniformly at random from the unit sphere, the asymptotic performance of near neighbor searching depends not only on the distance to the (planted) nearest neighbor, but also on the density of the data set, i.e. the exact relation between d and n. Motivated by concrete data sets commonly used in practice, we concretely analyze the case (log n)/d ≈ 1/5 and show that the resulting trade-offs for the exact nearest neighbor problem without planted neighbors are significantly better than hyperplane LSH [20]; comparable to or better than cross-polytope LSH [4, 48] and spherical cap LSH [5]; but slightly worse than spherical LSF [13, 6]. The superior asymptotic performance compared to FALCONN for realistic dense data sets suggests that graph-based approaches may remain competitive with the most practical hash-based approaches, even when the dimensionality further increases. Various open problems remain to obtain a better theoretical (and practical) understanding of different near neighbor techniques, in particular related to graph-based approaches. We state some remaining open problems below: Although our analysis for "small steps" (see Appendix A) is tight, we assumed that afterwards we either immediately find the planted nearest neighbor as one of the neighbors in the graph, or we fail and start over from a new random node. This seems rather pessimistic, and perhaps the complexities can be further improved with a tighter analysis, without changing the underlying algorithm or graph construction. Other heuristic nearest neighbor graph approaches appear to perform even better in practice, and an open problem is to rigorously analyze those and see whether they translate to improved asymptotics as well. A practical drawback of using nearest neighbor graphs is that updating the data structure (in particular: inserting new data points) can be rather costly, especially in comparison with hash-based constructions. To make the data structure both efficient and dynamic, one would ideally obtain better bounds on the insertion complexity as well. In hash-based literature, the case of sparse data sets has arguably almost been "solved" with upper bounds matching lower bounds (within a certain model). Is it possible to find similar lower bounds for graph-based near neighbor searching? Hash-based and graph-based approaches could be considered complementary solutions to the same problem, as worst-case problem instances for one approach are best-case instances for the other. Can both techniques be combined, so that perhaps even better worst-case guarantees can be obtained for high-dimensional data sets? Outline. The remainder of this paper is organized as follows. In Section 2, we introduce preliminary results and notation. Section 3 describes problem instances considered in this paper. Section 4 analyzes the complexities of finding near neighbors with a greedy graph search, and Sections 5 and 6 consider asymptotics for sparse and dense data sets, respectively. The appendices contain proofs and discuss the application to lattice sieving. Graph-based time-space trade-offs for approximate near neighbors 2 Preliminaries Let · denote the Euclidean norm, and let ·, · denote the standard dot product. We write for the Euclidean unit sphere in R d . We write X ∼ χ(X ) to denote that the random variable X is sampled from the probability distribution χ over the set X , and we write U(X ) for the uniform distribution over X . Given a vector x (written in boldface), we further write x i = x, e i for the ith coordinate of x. We denote directed graphs by G = (V, A) where V denotes the set of vertices, and A ⊆ V × V denotes the set of directed arcs. A directed graph is called symmetric if Symmetric directed graphs can also be viewed as undirected graphs G = (V, E) where edges are unordered subsets of V of size 2. Let C x,α = {u ∈ S d−1 : u, x ≥ α} denote the spherical cap centered at x ∈ S d−1 of "height" α ∈ (0, 1), and let C(α) denote its volume relative to the entire unit sphere. Let W x,α,y,β = C x,α ∩ C y,β with x, y ∈ S d−1 and α, β ∈ (0, 1) denote the intersection of two spherical caps, and let its volume relative to the volume of the unit sphere be denoted W (α, β, γ), where γ = x, y is the cosine of the angle between x and y. We will also call the latter objects wedges. The volumes of these objects correspond to probabilities on the sphere as follows: The asymptotic relative volumes of spherical caps and wedges can be estimated as follows, as previously shown in e.g. [13, 6]. Lemma 2 (Volume of a spherical cap). Let α ∈ (0, 1). Then: Lemma 3 (Volume of a wedge). Let α, β, γ ∈ (0, 1). Then: For the wedge, the volume can alternatively be described (up to polynomial factors in d) as the volume of a spherical cap with height δ = α 2 +β 2 −2αβγ 1−γ 2 . In Figure 1 , this δ corresponds to the smallest distance from points in W x,α,y,β to the origin, i.e. the distance from the intersection of the blue and red lines in this projection of the sphere to the origin. In case γ ≥ α β with α ≤ β, this distance from the origin becomes δ = β and therefore In that case, one essentially has C x,α ∩ C y,β ≈ C y,β . We will be using various properties of these wedges, and we state some of them below. For α, β, γ ∈ (0, 1) with γ < min{  Proof. For 1. the result follows by taking derivatives w.r.t. α, β, γ of the "asymptotic part" of W (i.e. ignoring the d Θ(1) term), and observing that these derivatives are always negative, negative, and positive respectively. For 2. we take the derivative w.r.t. β of W (α, β, β) and observe that this derivative is always negative. The following lemma further describes that if we add a small amount of "slack" to one of the variables, then the volume of the resulting wedge will still be very similar to the volume of the wedge with the original parameters -if the slack is small, then we only lose at most a polynomial factor in the volume. Proof. This follows from writing out the left hand sides, pulling out the factors W (α, β, γ), and noting that the remaining factor (1 ± ε d ) d for some expression ε d is at most polynomial in d, due to the conditions on γ and α, β, γ being constant in d. For the graph-based approach in this paper, where points are connected to their nearest neighbor and we perform a walk on this graph starting from a random node, it is impossible to solve worst-case instances of (approximate) nearest neighbor searching. Proposition 6 (Worst-case data sets). For near neighbor graph approaches, where (i) each vertex is only connected to a number of its nearest neighbors, and (ii) queries are answered by performing a greedy search on this graph to obtain better estimates, it is impossible to solve worst-case (approximate) near neighbor instances in sublinear time. Graph-based time-space trade-offs for approximate near neighbors Proof. As a potential worst-case problem instance to such a strategy, consider a query q ≈ e 1 , a planted nearest neighbor p * ≈ e 1 close to the query, and let all other points p ∈ D \ {p * } satisfy p ≈ −e 1 . Then the preprocessed near neighbor graph will consist of a large connected component containing the points D \ {p * }, and an isolated vertex p * , which may have outgoing edges, but has no mutual friends. With probability 1 − 1/n, starting at a random vertex and performing a walk on this (directed) graph will therefore not yield the true nearest neighbor p * , while all other vertices are only approximate solutions with very high approximation factors; by essentially setting p * = q, we can guarantee that even no reasonable approximate solution will be found. Although it may be possible to tweak the algorithm and/or the underlying graph so that even such worst-case instances can still be solved efficiently, we will therefore focus on average-case, random instances defined below. Throughout, we will assume that points p ∈ D are independently and uniformly distributed on the unit sphere, except for (potentially) a planted nearest neighbor p * ∈ D which lies very close to the query vector q. Alternatively, this can be interpreted as taking a uniformly random p * ∼ U(D), and choosing the query vector as q = p * + e for a short error vector e. Given such a problem instance, we wish to recover p * with non-negligible probability. Note that the near neighbor problem on the Euclidean unit sphere, as considered here, is of special interest as such a solution allows one to the Euclidean near neighbor problem in all of R d using techniques of Andoni-Razenshteyn [7]. Furthermore, it is well-known that using standard reductions, the results for the 2 -norm translate to results for R d with the 1 -norm as well. Efficient algorithms for the unit sphere therefore translate to solutions for many other problems as well. For q ∼ U(D), and data sets following a uniformly random distribution, with overwhelming probability the (non-planted) second nearest neighbor p ∈ D \ {p * } to q has inner product p, q = µ(1 + o(1)) and lies at distance q − p = 2(1 − µ)(1 + o(1)) from q, with µ satisfying: The natural scenario to consider for random ANN instances is then to let c · r = µ, so that the single planted nearest neighbor lies at distance r = µ/c from the target, and so that this planted near neighbor lies a factor c closer to q than all other points in the data set. These problem instances were also studied in for example [4, 6]. Sparse data sets. We will refer to data sets of size n = 2 o(d) (in other words: d = ω(log n)) as sparse data sets. For these instances, the expected (non-planted) nearest neighbor distance is µ = √ 2 + o(1), and the planted nearest neighbor which we wish to recover therefore lies at distance r = √ 2/c (1 + o(1)) from the target. Note that the case n = 2 o(d/ log d) can always be reduced to n = 2 Θ(d/ log d) through a random projection onto a lower-dimensional space, approximately maintaining all pairwise distances between points in the data set [32]. Dense data sets. We will refer to data sets of size n = 2 Θ(d) (d = Θ(log n)) as dense data sets. In this case, with overwhelming probability the nearest neighbor to a randomly chosen query point q on the sphere will lie at distance c · r = µ < √ 2 from q, and for (c, r)-ANN the planted nearest neighbor would therefore lie at distance r = µ/c. For the limiting case of c → 1, we wish to recover a vector at distance µ. Note that the "curse of dimensionality" [31] does not necessarily apply to average-case dense data sets -finding exact nearest neighbors for random dense data sets can often be done in sub-linear time [35, 13]. Graph-based near neighbor searching The nearest neighbor graph and corresponding near neighbor search algorithm we will analyze are very similar to a greedy search in the k-nearest neighbor graph, i.e. very similar to the approach of KGraph. Recall that the directed k-nearest neighbor graph G = (V, A) has vertex set V = D, and an arc runs from p to p iff p belongs to the k closest points to p in D. Given a query q, searching for a nearest vector in this graph is commonly done as outlined in Algorithm 1, with ε = 0, and with B(p) denoting the set of neighbors to p in this graph. Note that for large k = n Θ(1) , this graph is almost symmetric. The condition of belonging to the k nearest neighbors is however somewhat impractical to work with analytically, and so we will use the following slightly different graph (and search algorithm) instead. Definition 7 (The α-near neighbor graph). Let α ∈ (0, 1), and let D ⊂ S d−1 . We define the α-near neighbor graph as the undirected graph G = (V, E) with vertex set V = D, and with an edge between p, p ∈ E if and only if p, p ≥ α. The parameter α roughly corresponds to (a function of) k: large α correspond to small k, and small α to large k. Asymptotically, the approximate relation between k and α can be stated through the following simple relation k ≈ n · C(α). The main difference is that rather than fixing k and varying the required distance between points for an edge, we fix a bound on the distance between two connected points in the graph, and therefore we will have slight variations in the number of neighbors k from vertex to vertex. Notice the similarity with spherical cap LSH [5] and in particular spherical LSF [13, 6]: we essentially use n random spherical filters centered around our data points, and we add vectors to filter buckets the same way as in spherical LSF: if the inner product with the filter vector p is sufficiently large, we add the point to this bucket B(p). However, in the spirit of graph-based approaches we search for a path on the nearest neighbor graph that ends at the nearest neighbor as in Algorithm 1, rather than checking a number of filters close to the query point to see if the nearest neighbor is contained in any of those. To process a query q, we first sample a uniformly random point p ∼ U(D). Then we go through its neighbors B(p) to see if any of these vectors p ∈ B(p) are closer to q than p. If so, we use this as our new p ← p , and we again see if any of its neighbors are closer to q. We repeat this procedure until no more vectors in B(p) are closer to q than p itself, in which case p is our estimate for the real nearest neighbor p * to q. This may (p = p * ) or may not (p = p * ) actually be the true nearest neighbor to q, and to obtain a higher success rate we repeat the process several times, each time starting from a random point p ∼ U(D). While the focus is on minimizing the query time, Algorithms 2-3 also demonstrate how to do updates to this data structure, when vectors are inserted in D or removed from D. These parts of the algorithm may well be improved upon, and an important open question is to make updates (in particular insertions) as efficient as partition-based methods, such as in [6]. To obtain provable asymptotic complexities for this approach for the (approximate) nearest neighbor problem, we will prove the following results in Appendix A for some value γ max : • Small steps: If p ∈ D satisfies p, q γ max , then with non-negligible probability d we will find a slightly nearer neighbor p ∈ B(p) to q. • Giant leap: If p ∈ D satisfies p, q ≈ γ max , the probability of immediately finding the exact nearest neighbor p * in the bucket B(p) is larger than some given bound. Graph-based time-space trade-offs for approximate near neighbors if not progress then Algorithms for querying the α-near neighbor graph with a query point q, and for inserting/deleting points from this data structure. Here γ * is the (expected) inner product between q and its true nearest neighbor. Initializing the data structure is done by choosing α ∈ (0, 1) and for instance calling Insert(p) for all p ∈ D to construct the graph adjacency buckets B(p). The point p ∈ D denotes the current near neighbor estimate for the query q, and we want to make progress either by finding a slightly nearer neighbor p ∈ B(p) when p is far away from q (left), or finding the exact nearest neighbor p * ∈ B(p) to the query q when p is already quite close to q (right). The threshold separating these two cases is γmax. • Small steps (left). If the current near neighbor p has inner product p, q = γ γmax with q, then we expect that several points p ∈ D \ {p * } still exist which lie (slightly) closer to q than p, and we hope at least one of them is an α-near neighbor to p as well. Since a nearer neighbor in B(p) to q by definition lies in W p,α,q, p,q (the intersection of the solid spherical caps), and the data set is assumed to be uniformly random on the sphere, the probability of finding at least one such nearer neighbor is proportional to n · W (α, γ, γ). • Giant leap (right). Once we find a near neighbor p to q with inner product p, q ≈ γmax, we would like to show that in the next step, we will find p * ∈ B(p) with a certain (small) probability. Assuming p * is uniformly distributed on Cq,γ * , this corresponds to the probability that p * ∈ Wp,γ max,q,γ * (the intersection of the solid spherical caps), conditioned on the event p * ∈ Cq,γ * (the rightmost spherical cap). This probability is therefore proportional to W (α, γ * , γmax)/C(γ * ). • Randomization: Since "giant leaps" may often fail, we argue that starting over at random nodes a sufficiently large number of times leads to a constant success probability. We prove that the number of vertices in each bucket, and on each walk through the graph, can be bounded by small multiples of their expected values. • Query complexity: Using these results, we derive bounds on the time complexity for answering queries, with and without starting over at random nodes in the graph. • Space complexity: Similarly, since the number of edges in the graph can be bounded appropriately, we obtain tight bounds on the required space complexity.  5 Asymptotics for sparse data sets Due to space limitations, the derivation of the asymptotics on the various costs of graph-based near neighbor searching for large d have been moved to Appendix B. Its derivation mainly consists of carefully writing out the costs stated in the previous theorem, and doing series Theorem 9 (Complexities for sparse data). Let n = 1/C(µ) = 2 o(d) and let α = κ · µ. Let γ * = 1 − 1/c 2 denote the inner product between the query and the (planted) nearest neighbor. Using the α-NNG with α = κ·µ with κ ∈ ( (γ * ) 2 /(1 + (γ * ) 2 ), 1), with high probability we can solve the sparse near neighbor problem in several iterations with the following complexities: Denoting the query time complexity by Time = n ρq+o(1) and the space complexity by Space = n 1+ρs+o(1) , the trade-off between these costs can be expressed using the following inequality: As described in the introduction, for c ≈ 1 and ρ s → 0, the above condition on ρ q scales as ρ q ≥ 1 + 4(c − 1) 2 + O((c − 1) 4 ), which is equivalent to the scaling near c = 1 for the optimal partition-based near neighbor method of [6]. For larger c and when using more space, this Graph-based time-space trade-offs for approximate near neighbors trade-off is not better than the best hash-based methods -by substituting ρ s (1 − ρ s ) ≤ 1 2 , we obtain the necessary (but not sufficient) condition ρ q ≥ c 2 /(2c 2 − 1), which shows that the query complexity never reduces beyond √ n, even for large c. This inability to "profit" from large approximation factors may be inherent to graph-based approaches, or at least to the greedy graph-based approach considered in this paper. For the "balanced" trade-off of ρ q = ρ s = ρ, the condition on the exponents translates to: For small c ≈ 1, this leads to the asymptotic scaling ρ = 1 − 4(c − 1) 2 + O((c − 1) 3 ), which is slightly worse than the optimal hash-based trade-offs of [5, 6]  Asymptotics for dense data sets For data sets of size n = 2 Θ(d) , the asymptotics from the previous section do not apply; these assumed that µ = √ 1 − n −2/d = o(1). In some applications the relation d = Θ(log n) is more accurate, and arguably even if e.g. d = Θ(log n log log n) grows faster than log n, asymptotics for the sparse regime may be rather optimistic; log log n terms are then considered "large", even though for realistic parameters log log n may just as well be considered constant. In Appendix C, we performed a case study for an application where µ = √ 1 − n −2/d = 1 2 , so that n ≈ 2 d/5 . This example is motivated by algorithms for solving hard lattice problems and cryptanalyzing lattice-based cryptosystems, which have previously been improved using other (hash-based) near neighbor methods [34, 14, 13]. Comparable results may hold for other applications as well; the GloVe data set [45] contains n = 1.2M ≈ 2 20 vectors in d = 100 dimensions, which corresponds to n ≈ 2 d/5 , while the SIFT features data set [2] has n = 1M vectors in d = 128 dimensions, corresponding to n ≈ 2 0.35d . The conclusions regarding the comparison of graph-based near neighbor searching techniques with hash-based methods (in Appendix C) may therefore apply to other data sets and applications as well. Note that since the precise trade-offs depend on many parameters (see Theorem 1), we do not state a main result here, and refer the reader to Appendix C for one specific case analysis for lattice sieving. For arbitrary densities and target angles, this is a matter of writing out the expressions from Theorem 1 and looking at the asymptotic scaling of the various costs.
The only theoretical paper we aware of is REF considering the sparse regime d log n. The current paper, while using a similar setting, differs in several important aspects.