While the problem of approximate nearest neighbor search has been well-studied for Euclidean space and @math , few non-trivial algorithms are known for @math when ( @math ). In this paper, we revisit this fundamental problem and present approximate nearest-neighbor search algorithms which give the first non-trivial approximation factor guarantees in this setting.
For Euclidean space, Chan @cite_15 gave a deterministic construction which gives an @math -ANN, in time @math and using polynomial space (see also @cite_7 ). For @math , Neylon @cite_16 gave an @math -ANN structure which runs in @math time and uses @math space.
@cite_15 @cite_16 @cite_7
2508919161 2012238497 2163938320 2107342718
[See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the @math -Approximate Near Neighbor Search problem. For the @math -dimensional Euclidean space and @math -point datasets, we develop a data structure with space @math and query time @math for every @math such that: This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor @math , improving upon [Kapralov, PODS 2015]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [Becker, Ducas, Gama, Laarhoven, SODA 2016] and data-dependent hashing [Andoni, Indyk, Nguyen, Razenshteyn, SODA 2014] [Andoni, Razenshteyn, STOC 2015]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole above trade-off in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match the above trade-off for @math , improving upon the best known lower bounds from [Panigrahy, Talwar, Wieder, FOCS 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes. We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into ℝ d , where d is fixed (and small). For d = 1, it was known that approximating the minimum distortion with a factor better than roughly n 1 12 is NP-hard. From this result we derive inapproximability with a factor roughly n 1 (22d-10) for every fixed d ≥ 2, by a conceptually very simple reduction. However, the proof of correctness involves a nontrivial result in geometric topology (whose current proof is based on ideas due to Jussi Vaisala), For d > 3, we obtain a stronger inapproximability result by a different reduction: assuming P≠NP, no polynomial-time algorithm can distinguish between spaces embeddable in ℝ d with constant distortion from spaces requiring distortion at least n c d , for a constant c > 0. The exponent c d has the correct order of magnitude, since every n-point metric space can be embedded in ℝ d with distortion O(n 2 d log 3 2 n) and such an embedding can be constructed in polynomial time by random projection. For d = 2, we give an example of a metric space that requires a large distortion for embedding in ℝ 2 , while all not too large subspaces of it embed almost isometrically. Given a set U with n elements and a family of subsets S 2^U we show how to count the number of k-partitions S_1 ? ? ? S_k = U into subsets S_i S in time 2^ n n^ O(1) . The only assumption on S is that it can be enumerated in time 2^ n n^ O(1) . In effect we get exact algorithms in time 2^ n n^ O(1) for several well-studied partition problems including Domatic Number, Chromatic Number, Bounded Component Spanning Forest, Partition into Hamiltonian Subgraphs, and Bin Packing. If only polynomial space is available, our algorithms run in time 3^ n n^ O(1) if membership in S can be decided in polynomial time. For Chromatic Number, we present a version that runs in time O(2.2461^n ) and polynomial space. For Domatic Number, we present a version that runs in time O(2.8718^n ). Finally, we present a family of polynomial space approximation algorithms that find a number between ( G ) and ( 1 + ) ( G ) in time O(1.2209^n + 2.2461^ e^ - n ). We define a natural notion of efficiency for approximate nearest-neighbor (ANN) search in general n-point metric spaces, namely the existence of a randomized algorithm which answers (1 + e)-ANN queries in polylog(n) time using only polynomial space. We then study which families of metric spaces admit efficient ANN schemes in the black-box model, where only oracle access to the distance function is given, and any query consistent with the triangle inequality may be asked.For e < 2 5, we offer a complete answer to this problem. Using the notion of metric dimension defined in [A. Gupta, et al, Bounded geometries, fractals, and low-distortion embeddings, in: 44th Annu. IEEE Symp. on Foundations of Computer Science, 2003, pp. 534-543] (a la [P. Assouad, Plongements lipschitziens dans Rn, Bull. Soc. Math. France 111 (4) (1983) 429-448]), we show that a metric space X admits an efficient (1+e)-ANN scheme for any e < 2 5 if and only if dim(X) = O(log log n). For coarser approximations, clearly the upper bound continues to hold, but there is a threshold at which our lower bound breaks down--this is precisely when points in the "ambient space" may begin to affect the complexity of "hard" subspaces S ⊆ X. Indeed, we give examples which show that dim(X) does not characterize the black-box complexity of ANN above the threshold.Our scheme for ANN in low-dimensional metric spaces is the first to yield efficient algorithms without relying on any additional assumptions on the input. In previous approaches (e.g., [K.L. Clarkson, Nearest neighbor queries in metric spaces, Discrete Comput. Geom. 22(1) (1999) 63-93; D. Karger, M. Ruhl, Finding nearest neighbors in growth-restricted metrics, in: 34th Annu. ACM Symp. on the Theory of Computing, 2002, pp. 63-66; R. Krauthgamer, J.R. Lee, Navigating nets: simple algorithms for proximity search, in: 15th Annu. ACM-SIAM Symp. on Discrete Algorithms, 2004, pp. 791-801; K. Hildrum, et al, A note on finding nearest neighbors in growth-restricted metrics, in: Proc. of the 15th Annu. ACM-SIAM Symp. on Discrete Algorithms, 2004, pp. 560-561]), even spaces with dim(X) = O(1) sometimes required Ω(n) query times.