Source-linked AI summary
Approximate Nearest Neighbor Search in High Dimensions
Alexandr Andoni, Piotr Indyk, Ilya Razenshteyn
TL;DR
Nearest-neighbor search seeks fast, space-efficient retrieval in high-dimensional metric spaces, where exact methods can incur severe dimension dependence. This survey organizes approximate methods around a reduction to approximate near neighbor, covering polynomial-dimension structures and related geometric results. It also records strong high-dimensional barriers, including deterministic and space-partition limitations.
Problem
Nearest-neighbor search must reduce query work and memory below brute-force and exhaustive-precomputation approaches, especially when n and d are large.
Method
The survey studies a second wave of approximate nearest neighbor structures, reducing the problem to approximate near neighbor and then constructing data structures for that decision version.
Results
For every c > 1, the survey gives a (c, r)-ANN structure in Euclidean space with space n^(1+ρ) + O(nd) and query time n^ρ + d n^o(1).
Takeaways & Limitations
Approximation supports data structures with query-time and space bounds polynomial in dimension, while the survey also connects these constructions to geometric functional analysis and combinatorial geometry.
Takeaways & Limitations
Only one polynomial-size deterministic approximate near neighbor structure with constant approximation factor is known, and several related problem variants are outside the survey’s scope.
Abstract
from arXiv · showhide
The nearest neighbor problem is defined as follows: Given a set $P$ of $n$ points in some metric space $(X,D)$, build a data structure that, given any point $q$, returns a point in $P$ that is closest to $q$ (its "nearest neighbor" in $P$). The data structure stores additional information about the set $P$, which is then used to find the nearest neighbor without computing all distances between $q$ and $P$. The problem has a wide range of applications in machine learning, computer vision, databases and other fields. To reduce the time needed to find nearest neighbors and the amount of memory used by the data structure, one can formulate the {\em approximate} nearest neighbor problem, where the the goal is to return any point $p' \in P$ such that the distance from $q$ to $p'$ is at most $c \cdot \min_{p \in P} D(q,p)$, for some $c \geq 1$. Over the last two decades, many efficient solutions to this problem were developed. In this article we survey these developments, as well as their connections to questions in geometric functional analysis and combinatorial geometry.
1 Introduction
Nearest-neighbor search balances query time and memory, motivating approximate answers and data structures with polynomial dependence on dimension. The survey focuses on reducing approximate nearest neighbor search to approximate near neighbor and constructing structures for that decision problem.
- Motivation: Nearest-neighbor data structures avoid computing all n query-to-point distances by storing additional information about P.A brute-force query requires at least n distance computations, while precomputing every binary-space query requires 2^d memory.
- Motivation: The central design tradeoff is between query time and the memory space used by the data structure.Construction time is another parameter, but the discussion primarily focuses on query time and space.
- High-dimensional limits: High-dimensional exact structures can require n^O(d) space, and Voronoi decompositions may have complexity n^Ω(d).The survey also notes evidence that efficiently constructing query times of the form n^(1−α)d^O(1) may be difficult.
- Approximation: Approximate nearest neighbor permits returning a point within factor c ≥ 1 of the true nearest-neighbor distance, enabling better data structures when c > 1.Earlier solutions improved the tradeoff but retained exponential dependencies on dimension.
- Survey scope: The survey’s second wave targets approximate nearest neighbor structures whose query-time and space bounds are polynomial in dimension d.These structures first reduce approximate nearest neighbor to approximate near neighbor, then construct a data structure for the decision version.
- Definitions: Approximate near neighbor uses a scale r: when P intersects B(q, r), the structure returns any point of P within B(q, cr).The problem is parameterized by approximation factor c > 1 and scale parameter r > 0.
2 Data-independent approach
Data-independent approximate near-neighbor structures reduce high-dimensional search through oblivious dimension reduction or randomized space partitions. Dimension reduction makes exponential-in-dimension structures polynomial in n, while locality-sensitive hashing yields near-optimal exponents for Hamming and Euclidean spaces.
- Overview: Data-independent structures use query memory accesses determined by q and construction randomness, not by the dataset P.The survey develops oblivious dimension reduction and randomized space partitions as the two main approaches.
- Oblivious dimension reduction: Dimension reduction targets k = O(log n), so exponential dependence on k becomes polynomial dependence on n.For ℓ2, randomized maps preserve distances within a 1 + ε factor with constant probability, and the maps are oblivious to P.
- Oblivious dimension reduction: Q = O(d · log n/ε^2) and S = n^O(log(1/ε)/ε^2) + O(d(n + k)) for (1 + O(ε), r)-ANN in ℓ2.The construction has build time O(S + ndk).
- Oblivious dimension reduction: In Hamming space, randomized GF(2) projections give (1 + O(ε), r)-ANN using n^O(1/ε^2) + O(d(n + k)) space and O(d · log n/ε^2) query time.The projection uses k = O(log(n)/ε^2), and computing the reduced query takes O(dk) time.
- Randomized space partitions: LSH converts collision probabilities p1 and p2 into ANN exponent ρ = log(1/p1) / log(1/p2), with query and space bounds determined by this exponent.The construction uses multiple dictionary structures and optimizes the number of repetitions and reduced dimension.
- Randomized space partitions: The best known LSH exponents approach 1/c for Hamming and 1/c^2 for Euclidean space, matching lower bounds up to lower-order terms.The Euclidean result also extends from Hamming space because binary-vector ℓ1 and squared ℓ2 distances coincide.
- Randomized space partitions: LSH lower bounds require conditions such as p2 ≥ 2^-o(d); without them, ρ = 0 is possible only with query time at least exponential in d.This exposes a trade-off between a formally excellent exponent and the high-dimensional runtime that LSH is intended to avoid.
3 (More) Deterministic algorithms
Deterministic approximate near-neighbor algorithms address false negatives but remain substantially more limited than randomized methods. Known constructions use deterministic embeddings, expanders, coding, and block partitioning, with polynomial guarantees available only in restricted settings.
- Motivation: Randomized data structures may return nothing even when B(q, r) contains a dataset point, whereas deterministic algorithms can provide stronger guarantees.This false-negative issue motivates the deterministic-algorithm section.
- From randomized to deterministic guarantees: A finite metric can amplify randomized structures across O(log |X|) independent copies to answer all queries simultaneously with probability at least 2/3.The amplification multiplies both space and query time by O(log |X|), and construction still has nonzero failure probability.
- Deterministic Hamming-space algorithms: Expander-based mappings preserve small Hamming distances from above while separating pairs at distance at least r by at least (1 − α)∆r.The mapping concatenates input symbols across graph neighborhoods.
- Deterministic Hamming-space algorithms: Deterministic constructions can combine expander mappings with error-correcting codes and coordinate blocks, but the block property may fail when one point is a query.The block-search component uses exhaustive storage with n^1/ε^O(1) space per block.
- No-false-negative variants: Only one polynomial-size deterministic approximate near-neighbor structure with constant approximation is known; ANNWFN offers an intermediary guarantee by allowing ⊥ with bounded probability.The ANNWFN definition permits ⊥ with probability at most δ when the radius-r ball is nonempty.
- No-false-negative variants: For Hamming space, no-false-negative algorithms improved from roughly dn^1.38/c to roughly dn^1/c, the optimal runtime exponent.These methods combine densification, block partitioning, and locality-sensitive filtering.
4 Data-dependent approach
Data-dependent partitions improve approximate nearest-neighbor bounds beyond data-independent methods, while the survey also establishes trade-offs and near-optimality results under restricted partition models.
- Motivation: Data-independent methods face exponent barriers, motivating partitions tailored to the dataset even though improvements also hold for arbitrary datasets.The cited discussion gives lower bounds for LSH exponents and describes data-dependent partitions as a way to improve them.
- Theorem 4.1: For every c > 1, Theorem 4.1 gives space n1+ρ + O(nd) and query time nρ + dno(1), improving the c = 2 query exponent from n1/4+o(1) to n1/7+o(1).The theorem’s exponent is presented as ρ = 1/(2c^2−1) + o(1), with less memory in the c = 2 comparison.
- Construction: The construction reduces to the unit sphere, develops a Gaussian-threshold data-independent LSH building block, and recursively processes dense clusters and partitioned remainder sets.Dimension and spherical reductions incur negligible approximation loss; the final structure uses data-dependent partitions.
- Time–space trade-off: Theorem 4.2 provides a space/query-time trade-off, including for c = 2 the pairs n1+o(1), n7/16+o(1); n8/7+o(1), n1/7+o(1); and n16/9+o(1), no(1).The theorem states space n1+ρs+o(1) + O(nd) and query time nρq+o(1) + dno(1).
- Impossibility results: Within a restricted framework of data-dependent random space partitions, ρ = 1/(2c^2−1) − o(1) is a lower bound, making Theorem 4.1 essentially optimal.The restriction uses partition families with description complexity n1−Ω(1), rather than directly enforcing low query-time complexity.
- ANN for ℓ∞: For ℓ∞, a deterministic structure achieves approximation c = O(log log d), space O(dn1+ε), and query time O(d log n).Its recursive construction handles dense balls, good coordinates, and thresholds through separate partitioning cases.
5 Closest pair
The closest pair problem is treated as an offline analogue of approximate nearest neighbor, with reductions and matrix-multiplication techniques yielding improved runtimes for small approximation factors.
- Problem definition: Closest pair asks for the minimum-distance pair among n input points, while its approximate decision version seeks a pair within cr when a pair within r exists.The randomized definition requires success probability at least 2/3.
- Reduction from ANN: An approximate nearest-neighbor structure solves approximate close pair by randomly splitting the dataset, building on one half, querying the other, and repeating three times.One run succeeds with probability at least 1/2 · 2/3, and three repetitions reach probability 2/3.
- Main result: For ℓ2 and c = 1 + ε, Theorem 5.2 solves approximate close pair in O(n2−Ω(ε1/3/ log(1/ε)) + dn) time with constant probability.This improves the ε-dependence over the direct ANN reduction for small ε.
- Matrix multiplication: Fast matrix multiplication is the main technical ingredient, computing an n × m by m × n product in O(n2 log2 n) time when m ≤ n0.172.The matrix product is used after transforming or grouping point vectors so that a special pair can be identified.
- Embedding techniques: Tensoring amplifies inner products through ⟨x⊗k, y⊗k⟩ = (⟨x, y⟩)k, but can create vectors too high-dimensional to write down efficiently.Dimension reduction is used to preserve inner products, though additional implementation details remain necessary.
- Polynomial embeddings: Randomized polynomials replace tensoring with asymmetric embeddings whose polynomial is small on non-special inner products and large on sufficiently larger ones.Theorem 5.4 provides degree O(ε−1/3 log s) with separate probability guarantees across three inner-product ranges.
6 Extensions
The survey extends approximate nearest neighbor data structures through embeddings into standard normed spaces and reductions across direct sums. These techniques support efficient ANN structures for broader metric and norm classes, while target dimension and embedding efficiency remain important constraints.
- Embedding reductions: Bi-Lipschitz embeddings transfer a (c, r)-ANN structure to a (cD, r′)-ANN structure, with distortion D governing the approximation loss.The query procedure must evaluate the embedding, so its computational efficiency affects resulting space and query time.
- Deterministic embeddings: Finite metrics embed isometrically into ℓ∞, while d-dimensional normed spaces embed linearly into ℓ∞ with distortion 1 + ε and target dimension O(d/ε).These embeddings are generally inefficient for ANN because their target dimensions are too high, leading to exponential dependence on d.
- Deterministic embeddings: For 1 < p ≤2, ℓp embeds linearly into ℓ1 with distortion 1 + ε and dimension O(d/ε^2), making ANN over ℓp no harder than ANN over ℓ1.Other embeddings cover Wasserstein-1 metrics, Levenshtein distance, and finite metrics, with the stated distortions and target dimensions.
- Deterministic embeddings: For 1 ≤ p < 2, an efficient finite-dimensional embedding into ℓ2 converts approximation c into c2/p for ℓp ANN.The resulting ℓp structure has bounds analogous to the cited ℓ2 result, with c2 replaced by cp.
- Randomized embeddings and direct sums: Randomized embeddings and direct-sum reductions extend ANN structures to Orlicz, top-k, symmetric, and other norm classes.General symmetric norms obtain approximation (log log n)O(1), while ℓp and Schatten-p norms achieve approximation O(p).
- Applications and bounds: For general d-dimensional norms, combining an ℓ∞ embedding with an efficient ℓ2 ANN structure gives approximation O(d/ε) with space dO(1) · n1+ε and query time dO(1) · nε.For ℓp norms, later extensions improve the approximation to O(p); Schatten-p norms likewise obtain O(p), versus a previous polynomial dependence on matrix size.