Among 399,000 word vectors of 100 dimensions, the vector of neighborhood has neighborhoods as its nearest neighbor, then neighbourhood, suburb, downtown and residential. Finding those five by comparing neighborhood with every stored vector takes 39.9 million multiplications. Can the nearest vectors be found without looking at nearly all of them? Exactly, and with memory near the size of the data, no method is known that does much better than the scan at this dimension; approximately, yes, and the rest of this unit is about how.
Nearest neighbor search takes a set of stored vectors and a query vector and returns the $k$ stored vectors closest to the query. This article sets up the problem for the whole vector search unit. It measures the full scan that every index must beat. It shows that the classical exact index, the k-d tree, examines 97% of the vectors on this data, and proves the theorem usually given as the reason. It then defines recall, the number by which the approximate indexes of the later articles are judged, and proves a lemma that lets the dimension itself be reduced.
Here is the route. First we fix the data and measure the full scan. Then we build a k-d tree, watch it work in two dimensions and fail in a hundred, and find the reason in the tree's depth. Next comes the concentration of distances: a theorem with a short proof, a simulation, and the measurement that real embeddings do not behave like the theorem's data. Then recall is defined. Finally the Johnson–Lindenstrauss lemma is stated and proved in full. The article assumes cosine similarity for the geometry of unit vectors and uses variances and Chebyshev's inequality from the statistics course. Every number is computed by tools/experiments/vectors/nearest-neighbor-search-in-high-dimensions.py. Later articles of the unit build on the definitions made here.
The data and the problem
The unit's running dataset is the set of GloVe word vectors trained on Wikipedia and Gigaword: 400,000 lowercase words, each a vector of 100 numbers (Pennington, Socher, and Manning, 2014). Word embeddings explains how such vectors are trained. For this unit they are simply a large set of real vectors with a visible meaning: near vectors are related words, so a wrong answer can be seen as well as counted.
The preparation is the same in every article of the unit.
- Every vector is scaled to length 1. For unit vectors the Euclidean distance, the cosine and the dot product give the same ranking, because $\lvert \vec x - \vec q \rvert^2 = 2 - 2\, \vec x \cdot \vec q$ (cosine similarity proves it). The unit therefore speaks of distances only. Similarity measures for embeddings treats vectors that are not normalized, where a search for the largest dot product must first be reduced to a search for the nearest vector.
- One thousand of the vectors, drawn at random with a fixed seed, are the queries. They are removed from the stored set, so no query finds itself.
- The other $N = 399{,}000$ vectors are the base vectors $\vec x_1, \dots, \vec x_N$, each in $\mathbb{R}^m$ with $m = 100$.
For a query $\vec q$ and a number $k$, the $k$ nearest neighbors are the $k$ base vectors with the smallest distances $\lvert \vec x_i - \vec q \rvert$. We write $N_k(\vec q)$ for that set. Ties are broken by the lower index; among the 100 nearest neighbors of the 1,000 queries no two distances are equal, so the rule is never used on this data. The script finds $N_{100}(\vec q)$ for every query by comparing it with every base vector in double precision. That list is the ground truth of the unit.
For neighborhood the truth begins as follows. The distance is Euclidean, between unit vectors, so 0 would be the same direction and $\sqrt 2 = 1.414$ a right angle.
| Rank | Word | Distance |
|---|---|---|
| 1 | neighborhoods | 0.582 |
| 2 | neighbourhood | 0.635 |
| 3 | suburb | 0.731 |
| 4 | downtown | 0.742 |
| 5 | residential | 0.754 |
| 10 | apartment | 0.798 |
Two smaller sets of real vectors accompany the GloVe set through the unit. They come from the sentence encoder of the previous unit, which maps a passage to a unit vector of 384 dimensions: the 11,264 passages of this site with 60 queries, and the 1,400 abstracts of the Cranfield collection with its 225 queries.
The full scan
The simplest algorithm computes the distance from the query to every base vector and keeps the $k$ smallest. For unit vectors each distance needs one dot product, which is $m$ multiplications and $m$ additions. The scan therefore costs $N m$ multiplications per query, and selecting the $k$ best of $N$ numbers adds work proportional to $N$. Nothing is built in advance, nothing is stored besides the vectors, and the answer is exact.
On the GloVe set that is $399{,}000 \times 100 = 39.9$ million multiplications per query. The vectors occupy 159.6 MB as 4-byte floats. On the machine that ran the script, a computer shared with other jobs, with the scan written as one matrix-vector product in NumPy on at most four threads, a query took 9.1 milliseconds in the run whose timings are stored with the script. The figure moves with the machine's load. Over the four runs of the same scan on record (that one, an earlier run of this script, and two runs stored by the script of the locality-sensitive hashing article) a query took between 9.1 and 72 milliseconds. Timings in this unit are secondary figures: they depend on the machine and on what else it is doing. The count that does not is the number of distance computations, and for a scan it is $N$.
Example (this site's passages). A full scan answers a query over this site's 11,264 passage vectors in 0.51 milliseconds on the same machine in the stored run, and over Cranfield's 1,400 in 0.044; over the four runs on record, between 0.51 and 3.1 milliseconds and between 0.044 and 0.080. At this size there is nothing for an index to save. Benchmarking vector indexes finds the size at which that stops being true.
The scan's cost grows in proportion to $N$. A collection of a hundred million vectors of the same dimension would need 251 times the work, seconds per query instead of milliseconds, and 40 GB of memory for the vectors alone. That is the case the rest of the unit is for. An index is a structure built in advance from the base vectors that lets a query be answered by comparing it with only some of them. Can an index return exactly $N_k(\vec q)$ while examining a small share of the vectors? In two or three dimensions it can. The structure that does it is the k-d tree.
k-d trees
In one dimension the problem is easy. Sort the numbers once, and a binary search finds the nearest to any query in about $\log_2 N$ comparisons. The k-d tree of Bentley (1975) carries the idea to several dimensions. It is a binary tree in which every internal node splits its vectors by the value of one coordinate. (The "k" in its name is the dimension. This unit writes $m$ for the dimension and keeps $k$ for the number of neighbors.)
The version measured here is the one Friedman, Bentley, and Finkel (1977) analyzed for nearest neighbor search.
- Build. A node holding more than a fixed number of vectors (16 here) chooses the coordinate in which its vectors are most spread out, finds the median value of that coordinate, and sends the vectors below the median to its left child and the others to its right child. A node with 16 vectors or fewer is a leaf, which the paper calls a bucket. Every node thereby owns a cell, the box of space cut out by the splits above it, and the leaves' cells tile the whole space.
- Search. Descend from the root, at each node entering the child on the query's side of the split, down to a leaf. Compute the distances to the leaf's vectors and keep the best $k$ found so far. Then climb back. At each node passed on the way up, the other child must be searched only if its cell comes closer to the query than the $k$-th best distance found so far. The paper calls this the bounds-overlap-ball test: the ball around the query that holds the current best $k$ either reaches into the cell or does not. If it does not, the whole subtree is skipped, and none of its vectors is examined.
The distance from the query to a cell is cheap to maintain. A cell is a box, so its nearest point to $\vec q$ is found one coordinate at a time. In a coordinate where the query lies inside the box's range the offset is 0, and otherwise it is the distance to the nearer face. The squared distance to the cell is the sum of the squared offsets. The search is exact, since a subtree is skipped only when no vector in it can enter the best $k$.
The tree by hand
Eight points in the plane show the mechanics: $A = (1, 2)$, $B = (2, 7)$, $C = (3, 4)$, $D = (4, 9)$, $E = (6, 1)$, $F = (7, 6)$, $G = (8, 3)$ and $H = (9, 8)$, with leaves of at most two points. The first coordinates range from 1 to 9 and the second from 1 to 9, a tie in spread, which goes to the first coordinate. The four smallest first coordinates belong to $A$, $B$, $C$, $D$, so the root splits at $x_1 = 6$ (the smallest value on the right): left $\{A, B, C, D\}$, right $\{E, F, G, H\}$. On the left the second coordinate has the larger spread (2 to 9 against 1 to 4) and the split is at $x_2 = 7$, giving the leaves $\{A, C\}$ and $\{B, D\}$. On the right the second coordinate again has the larger spread (1 to 8 against 6 to 9) and the split is at $x_2 = 6$, giving $\{E, G\}$ and $\{F, H\}$.
Take the query $\vec q = (6.5, 4)$ and $k = 1$.
- The query has $x_1 = 6.5 \ge 6$, so the search goes right, and $x_2 = 4 < 6$, so it reaches the leaf $\{E, G\}$. The squared distances are $0.5^2 + 3^2 = 9.25$ to $E$ and $1.5^2 + 1^2 = 3.25$ to $G$. The best so far is $G$ at 3.25.
- Back at the node that split at $x_2 = 6$: the other cell, holding $\{F, H\}$, lies above $x_2 = 6$, at offset $6 - 4 = 2$ from the query, a squared distance of 4. Since $4 > 3.25$, the ball does not reach it. The leaf is skipped.
- Back at the root: the left cell lies below $x_1 = 6$, at offset $0.5$, a squared distance of $0.25 < 3.25$. It must be searched. Inside it the query's side of the split at $x_2 = 7$ is the lower one, the leaf $\{A, C\}$, whose cell is still at squared distance 0.25. Its points are at squared distances $5.5^2 + 2^2 = 34.25$ and $3.5^2 + 0^2 = 12.25$. Neither beats $G$.
- The remaining cell, of $\{B, D\}$, is at offsets $0.5$ and $7 - 4 = 3$, a squared distance of $9.25 > 3.25$. It is skipped.
The nearest neighbor is $G$, found by computing four distances instead of eight. A query in the middle is less fortunate. For $\vec q = (5, 5)$ the first leaf, $\{A, C\}$, gives a best squared distance of 5, and the other three cells are at squared distances 4, 1 and 2, all below 5: every leaf is opened and all eight distances are computed. The tree saves work only when the ball around the query is small compared with the cells.
From two dimensions to a hundred
Friedman, Bentley, and Finkel (1977) showed that for a fixed dimension the expected number of vectors examined does not grow with $N$, so the expected search time is proportional to $\log N$, the cost of the descent. Their analysis also shows how that number depends on the dimension. With distances measured by the largest coordinate difference, one vector per bucket and a file large enough for their approximations to hold, they derive that a search for one nearest neighbor examines $2^m$ vectors on average. The derivation assumes that buckets are examined in the best possible order, so they call the figure a lower bound even for that distance, and a lower bound for the Euclidean and the other $p$-norms as well. (Their paper was read here in its 1976 preprint, SLAC-PUB-1549, not in the journal.) The constant hidden in "does not grow with $N$" doubles with every dimension.
The script measures the same thing on synthetic data: 20,000 points drawn uniformly from the unit cube, 100 uniform queries, the exact ten nearest neighbors, 30 seeds for each dimension. The entry is the share of the 20,000 points whose distance to the query is computed (median over the seeds, with the interquartile range).
| Dimension $m$ | Share of points examined | Points examined |
|---|---|---|
| 2 | 0.0023 (0.0023 to 0.0024) | 47 |
| 4 | 0.0096 (0.0092 to 0.0099) | 191 |
| 8 | 0.0765 (0.0718 to 0.0791) | 1,529 |
| 12 | 0.3893 (0.3795 to 0.3975) | 7,787 |
| 16 | 0.8611 (0.8579 to 0.8664) | 17,222 |
| 24 | 0.9999 (0.9999 to 0.9999) | 19,999 |
| 32 | 1.0000 (1.0000 to 1.0000) | 20,000 |
In two dimensions the tree examines about 47 points of 20,000. By 16 dimensions it examines more than half of them, and from 24 dimensions on it examines practically all.
On the real data the result is the same. The tree over the 399,000 GloVe vectors has depth 15 and 32,768 leaves. For the first 100 queries the exact search computed the distance to 386,625 base vectors on average, 96.9% of all of them, and never fewer than 169,569. Over this site's 11,264 passage vectors of 384 dimensions it computed 11,264 distances per query: every vector, for every one of the 60 queries. The tree returns the exact answer, as the script asserts against the ground truth, and saves nothing: it does the work of a scan and the work of walking the tree as well.
Why the tree stops pruning
The reason can be read off the tree's depth. Here is the idea in one sentence: a cell is bounded only in the coordinates that were split on the way down to it, and a tree over $N$ vectors is too shallow to split more than a few of a hundred coordinates.
A tree with leaves of 16 over 399,000 vectors has depth 15, since each level halves the vectors and $399{,}000 / 2^{15} < 16$. A leaf's cell is therefore constrained in at most 15 of the 100 coordinates and extends without limit in the others. The squared distance from a query to a cell is a sum of at most 15 squared offsets, one for each split coordinate in which the query lies outside the cell. The squared distance from the query to an actual vector is a sum over all 100 coordinates. The script measures how little that is. For each of the first 50 queries it computes the distance to the cell of every one of the 32,768 leaves. The median cell is at distance 0.36 from the query and the farthest at 0.70, while the tenth nearest neighbor is at 0.88 (each a median over these 50 queries). For a typical query every cell (100.0% of them) is nearer than its tenth neighbor. The ball that holds the ten best reaches into all of them, and the test that skips subtrees almost never succeeds.
Doubling $N$ adds one level to the tree and one constrained coordinate to each cell. To constrain all 100 coordinates even once, the tree would need $2^{100}$ leaves. This is the sense, observed here and not proved, in which a balanced k-d tree needs a number of vectors exponential in the dimension before its cells are small enough to prune. Weber, Schek, and Blott (1998) analyzed index methods that partition the space or the data, or cluster it, and concluded that under their cost model such methods are outperformed on average by a sequential scan once the dimension exceeds about ten. Har-Peled, Indyk, and Motwani (2012) summarize the theory: with storage near linear in the number of points, the best known bound on the query time, even for random points, is of the form $\min(2^{O(m)}, mN)$, which is in effect linear in $N$ once $m$ is moderate.
The explanation usually given for this failure is a statement about the distances themselves: in many dimensions the nearest and the farthest vector are almost equally far away, so no partition can separate them. Behind that statement is a theorem about a limit, which the next section proves. How far it describes real embeddings at $m = 100$ is a separate question, which the section after the proof answers by measurement.
Distances concentrate
For neighborhood the nearest base vector is at distance 0.582, the median base vector at 1.526 and the farthest at 1.760. The farthest is 3.02 times as far as the nearest. For 10,000 points scattered uniformly in a square the same ratio is in the hundreds, as the simulation below shows. The shrinking of this ratio as the dimension grows is the concentration of distances. Cosine similarity and k-nearest neighbors each show it in a small simulation and cite the theorem. This section states the theorem with its conditions and proves it.
Here is the idea in one sentence: if a distance is the sum of many terms of which none dominates, its spread is small compared with its size, so all of a fixed number of points fall in a thin shell around the query.
The theorem
The setting is that of Beyer, Goldstein, Ramakrishnan, and Shaft (1999). For each $m = 1, 2, 3, \dots$ there are
- $n$ data points $P_{m,1}, \dots, P_{m,n}$ drawn independently from one distribution, where $n$ is the same for every $m$;
- a query point $Q_m$ drawn independently of the data points;
- a distance function $d_m$ that returns a nonnegative number for a data point and a query;
- a fixed exponent $p > 0$.
Write $D_{m,i} = d_m(P_{m,i}, Q_m)$ for the distance of the $i$-th point, and $\mathrm{DMIN}_m$ and $\mathrm{DMAX}_m$ for the smallest and the largest of the $n$ distances. The index $m$ will be read as the dimension, but nothing in the theorem requires it: the theorem is about a sequence of distance distributions.
Theorem (Beyer, Goldstein, Ramakrishnan, and Shaft, 1999, Theorem 1). Suppose that
$$\lim_{m \to \infty} \operatorname{Var}\!\left( \frac{D_{m,1}^{\,p}}{E\!\left[D_{m,1}^{\,p}\right]} \right) = 0 .$$
Then for every $\varepsilon > 0$,
$$\lim_{m \to \infty} P\bigl( \mathrm{DMAX}_m \le (1 + \varepsilon)\, \mathrm{DMIN}_m \bigr) = 1 .$$
The condition says that the $p$-th power of the distance, divided by its own mean, has a variance that vanishes. We call that variance the relative variance and write $v_m$ for it. The authors prove the theorem from Slutsky's theorem on convergence in probability. The proof below is more direct. It uses only Chebyshev's inequality, and it gives a bound for each $m$ instead of a limit.
Proposition (a bound for each $m$). In the setting above, let $v_m$ be the relative variance. Then for every $\delta$ with $0 < \delta < 1$,
$$P\!\left( \frac{\mathrm{DMAX}_m}{\mathrm{DMIN}_m} \le \left( \frac{1 + \delta}{1 - \delta} \right)^{1/p} \right) \ge 1 - \frac{n\, v_m}{\delta^2} .$$
Proof. Write $\mu = E[D_{m,1}^{\,p}]$, which is positive whenever the relative variance is defined, and $V_i = D_{m,i}^{\,p} / \mu$. The data points have one distribution and each is independent of the query, so every $V_i$ has the same distribution, with mean 1 and variance $v_m$.
- By Chebyshev's inequality, $P(\lvert V_i - 1 \rvert \ge \delta) \le v_m / \delta^2$ for each $i$.
- The probability that at least one of the $n$ variables is off by $\delta$ or more is at most the sum of the $n$ probabilities, $n\, v_m / \delta^2$. This step does not need the $V_i$ to be independent of one another, and they are not, since they share the query.
- With probability at least $1 - n\, v_m/\delta^2$, therefore, every $V_i$ lies strictly between $1 - \delta$ and $1 + \delta$. Then $D_{m,i}^{\,p}$ lies between $(1 - \delta)\mu$ and $(1 + \delta)\mu$ for every $i$, in particular for the smallest and the largest, so $\mathrm{DMAX}_m^{\,p} / \mathrm{DMIN}_m^{\,p} < (1 + \delta)/(1 - \delta)$. Taking the $p$-th root gives the claim. $\blacksquare$
Proof of the theorem. Given $\varepsilon > 0$, choose $\delta$ so that $\bigl((1 + \delta)/(1 - \delta)\bigr)^{1/p} = 1 + \varepsilon$. Solving for $\delta$ gives $\delta = \bigl((1 + \varepsilon)^p - 1\bigr) / \bigl((1 + \varepsilon)^p + 1\bigr)$, which lies between 0 and 1. By the proposition, $P(\mathrm{DMAX}_m \le (1 + \varepsilon)\mathrm{DMIN}_m) \ge 1 - n\, v_m / \delta^2$. Here $n$ and $\delta$ do not depend on $m$, and $v_m \to 0$ by assumption, so the right side tends to 1. $\blacksquare$
Two cases where the condition holds
Independent coordinates. Let the data points and the query be uniform on the unit cube $[0, 1]^m$, independent of each other, and take the squared Euclidean distance ($p = 2$). The squared distance is a sum of $m$ terms $(U_j - W_j)^2$, one per coordinate, where $U_j$ and $W_j$ are independent and uniform on $[0, 1]$. For one term,
$$E\!\left[(U - W)^2\right] = E[U^2] - 2E[U]E[W] + E[W^2] = \tfrac13 - \tfrac12 + \tfrac13 = \tfrac16 .$$
The difference $U - W$ has the triangular density $1 - \lvert t \rvert$ on $[-1, 1]$, so $E[(U - W)^4] = 2\int_0^1 t^4 (1 - t)\, dt = 2\left(\tfrac15 - \tfrac16\right) = \tfrac1{15}$, and the variance of one term is $\tfrac1{15} - \tfrac1{36} = \tfrac{7}{180}$. The $m$ terms are independent, so the squared distance has mean $m/6$ and variance $7m/180$. Its relative variance is
$$v_m = \frac{7m/180}{(m/6)^2} = \frac{7}{5m},$$
which tends to 0. The same calculation covers any distribution of this kind. Take the $L_p$ distance, with the theorem's exponent equal to that $p$, and let data and query have independent, identically distributed coordinates. Then $D^p = \sum_j \lvert X_j - Q_j \rvert^p$ is a sum of $m$ independent copies of one term. If that term has mean $\mu > 0$ and finite variance $\sigma^2$, the sum has mean $m\mu$ and variance $m\sigma^2$, and $v_m = m\sigma^2/(m\mu)^2 = \sigma^2/(\mu^2 m)$. Beyer and colleagues give this case as their first example of a workload that meets the condition.
Random directions. Let the data points be random unit vectors whose distribution is the same in every direction, and let the query be any unit vector. The squared distance is $2 - 2\cos\theta$, and the cosine of a random direction with a fixed one has mean 0 and variance exactly $1/m$ (cosine similarity proves it). So the squared distance has mean 2 and variance $4/m$, and $v_m = (4/m)/4 = 1/m$.
In both cases the relative variance of the squared distance is of order $1/m$, and the proposition gives a bound of the form $1 - \text{constant} \times n/m$. The theorem follows, and so does its fine print: the bound says something only when $m$ is much larger than $n$.
What the theorem does not say
Three conditions in the statement matter in practice, and each is easy to drop when the theorem is retold.
- The number of points is fixed. The limit is taken with $n$ constant. A collection whose size grows with the dimension is outside the theorem.
- It is a limit. The theorem gives no dimension at which the ratio is small. The proposition does, but weakly. For uniform points, $n = 10{,}000$ and $\varepsilon = 1/2$ it needs $\delta = 5/13$ and says nothing until $7n/(5m\delta^2) < 1$, that is, until $m$ exceeds 94,640. The simulation below shows the ratio below 1.5 long before that. Chebyshev's inequality is far from tight for sums of many terms.
- The relative variance must vanish. The condition is on the distribution of distances, not on the number of coordinates. Beyer and colleagues give examples on both sides. If every coordinate repeats the first one, the data lie on a line, the relative variance does not change with $m$, and the theorem does not apply. They also name the cases in which nearest neighbor search stays meaningful in any dimension: a query that falls within a small distance of some data point, data that form well-separated clusters with the query inside one of them, and data whose underlying dimensionality is much lower than the number of coordinates.
Example (the misreading). "In high dimensions all points are equally far apart, so the nearest neighbor is meaningless" is not what the theorem says. For the 399,000 GloVe vectors at $m = 100$ the farthest vector is 2.35 times as far from a typical query as the nearest (the median over the 1,000 queries), against 1.69 for uniform data of the same size and dimension. The nearest neighbors of neighborhood are neighborhoods and neighbourhood, which is not an accident of noise. The theorem describes a limit for distributions whose relative variance vanishes, and the next two tables show how far real embeddings are from that limit.
Simulation: uniform data
The script draws 10,000 points and 100 queries uniformly from the unit cube, 30 times for each dimension. For each query it divides the largest distance by the smallest, and the median distance by the smallest, and takes the median over the queries. The table gives the median of that figure over the 30 seeds with its interquartile range.
| Dimension $m$ | Farthest ÷ nearest | Median ÷ nearest | Queries with farthest ≤ 1.5 × nearest |
|---|---|---|---|
| 1 | 22,224 (20,809 to 24,690) | 9,341 | 0% |
| 2 | 220 (213 to 230) | 110 | 0% |
| 4 | 22.7 (22.2 to 23.4) | 12.6 | 0% |
| 8 | 6.62 (6.57 to 6.67) | 4.06 | 0% |
| 16 | 3.34 (3.33 to 3.36) | 2.28 | 0% |
| 32 | 2.22 (2.20 to 2.23) | 1.65 | 0% |
| 64 | 1.72 (1.72 to 1.73) | 1.38 | 0% |
| 100 | 1.54 (1.53 to 1.54) | 1.28 | 13% |
| 128 | 1.46 (1.46 to 1.46) | 1.24 | 86% |
| 256 | 1.30 (1.30 to 1.30) | 1.15 | 100% |
| 384 | 1.24 (1.24 to 1.24) | 1.12 | 100% |
| 512 | 1.20 (1.20 to 1.21) | 1.10 | 100% |
| 1,024 | 1.14 (1.14 to 1.14) | 1.07 | 100% |
The ratio falls from tens of thousands in one dimension to 1.54 at $m = 100$ and 1.14 at $m = 1{,}024$. The check of the variance calculation is in the same run: at $m = 100$ the squared distances of 20,000 pairs of a point and a query have mean 16.68 and variance 3.89 (medians over the seeds), against $m/6 = 16.667$ and $7m/180 = 3.889$.
Measurement: real embeddings
The same quantities for the unit's three real sets, each against two synthetic sets of the same $N$ and $m$: uniform points in the cube, and random unit vectors. The real figures are medians over the queries; the synthetic ones are medians over 30 seeds of the median over 100 queries.
| Set | $N$ | $m$ | Farthest ÷ nearest | Median ÷ nearest |
|---|---|---|---|---|
| GloVe words | 399,000 | 100 | 2.35 | 1.74 |
| uniform in the cube | 399,000 | 100 | 1.69 | 1.36 |
| random unit vectors | 399,000 | 100 | 1.61 | 1.34 |
| Site passages | 11,264 | 384 | 1.82 | 1.63 |
| uniform in the cube | 11,264 | 384 | 1.24 | 1.12 |
| random unit vectors | 11,264 | 384 | 1.22 | 1.11 |
| Cranfield abstracts | 1,400 | 384 | 1.86 | 1.56 |
| uniform in the cube | 1,400 | 384 | 1.20 | 1.10 |
| random unit vectors | 1,400 | 384 | 1.19 | 1.10 |
Two things stand out. First, the real sets are not far from the synthetic ones in the first ratio: with $m$ in the hundreds, the farthest vector is between 1.19 and 2.35 times as far as the nearest in every row. Concentration is real, and it contributes to the k-d tree's failure: the tenth neighbor of a typical GloVe query is at 0.85 (the median over all 1,000 queries; 0.88 for the 50 queries of the cell measurement) while a typical vector is at 1.30, so the ball that must be cleared is large compared with the cells a tree of depth 15 can bound. Second, the real sets differ from the synthetic ones exactly where search needs them to. A random unit vector's nearest neighbor among 399,000 others in 100 dimensions is at distance 1.055, three quarters of the typical distance $\sqrt2 = 1.414$. The nearest neighbor of a typical GloVe query is at 0.737, little more than half of its median distance, 1.295. The embeddings have a small number of vectors much nearer to each query than the bulk, because they were trained to put related words near each other. In the terms of Beyer and colleagues, the queries fall inside clusters.
A single number summarizes the bulk. The relative variance of the squared distance over all query and base pairs is 0.0386 for GloVe. Random unit vectors have relative variance $1/m$, so the GloVe distances are spread like those of random directions in about 26 dimensions, not 100. For the site's passages the figure is 0.0156, the spread of random directions in about 64 dimensions, not 384. These equivalent dimensions describe the bulk of the distances only. The near neighbors that make search worthwhile are in the lower tail, which the variance hardly registers.
So concentration makes exact pruning by boxes hopeless at this depth, and does not make the problem meaningless. The theorem describes the limit of the effect for a fixed number of points. It is not a proof that the tree must fail on this data; that was measured. What the measurements show is that the tenth neighbor's ball is too large, compared with any cell that a tree of feasible depth can produce, to exclude much. The indexes of the following articles do not try to exclude with certainty. They look where near vectors are likely to be and accept that some are missed. That needs a measure of how many.
Recall
An approximate nearest neighbor index returns a list $A_k(\vec q)$ of $k$ base vectors that need not be the true $k$ nearest. Its quality on a query is the share of the truth that it found.
Recall@$k$ of an answer is
$$\text{recall@}k = \frac{\lvert A_k(\vec q) \cap N_k(\vec q) \rvert}{k},$$
and the recall@$k$ of an index is the mean over the queries. The denominator is always $k$, also when an index returns fewer than $k$ vectors, so that returning little is never rewarded. The order within the list does not matter. This unit reports recall@10 throughout, over the 1,000 queries, as its headline figure.
The name comes from retrieval evaluation, where recall is the share of the relevant documents that were retrieved (retrieval evaluation). Here the "relevant" items are the $k$ true neighbors, of which there are exactly $k$, and the answer holds at most $k$ items, so recall@$k$ and precision@$k$ coincide when the answer is full. The measure says nothing about whether the true neighbors are good answers to the user's question. That is the business of the encoder and is measured by nDCG and its relatives. An index with recall 1 returns exactly what a scan would.
Two refinements appear in the literature. Aumüller, Bernhardsson, and Faithfull (2020) define recall by distance instead of identity in their benchmark: a returned vector counts if its distance is at most that of the true $k$-th neighbor, which treats tied vectors alike. On this data there are no ties and the two definitions agree. They also define an approximate version, in which a returned vector counts if it is within $(1 + \varepsilon)$ times the $k$-th distance.
The theory of the subject uses a different measure, the distance ratio. A returned vector $\vec x$ is a $c$-approximate nearest neighbor of $\vec q$, for a number $c \ge 1$, if its distance is at most $c$ times the distance of the true nearest neighbor (Har-Peled, Indyk, and Motwani, 2012). The guarantees of locality-sensitive hashing and of the lemma in the next section are of this kind. The two measures can disagree badly, and concentration is the reason: when the hundredth neighbor is only a little farther than the first, a list that misses all ten true neighbors can still have a ratio near 1.
Example (low recall, small ratio). Stop the k-d tree's search of the GloVe vectors after 100 leaves instead of letting it finish. It has then examined about 1,218 vectors, 0.3% of the base. Over the first 200 queries its recall@10 is 0.114, yet the vectors it returns are on average only 1.19 times as far as the true neighbors of the same rank. For neighborhood it returns neighborhoods, downtown, area, town, suburbs, nearby, village, residents, streets, crowded, of which 4 are among the true ten. Six of the ten words are wrong, and the distance ratio hardly shows it.
The stopped tree is itself an approximate index, a poor one:
| Leaves opened | Vectors examined | Share of $N$ | Recall@10 | Mean distance ratio |
|---|---|---|---|---|
| 1 | 12 | 0.00% | 0.016 | 1.510 |
| 10 | 122 | 0.03% | 0.048 | 1.318 |
| 100 | 1,218 | 0.31% | 0.114 | 1.194 |
| 1,000 | 12,177 | 3.05% | 0.288 | 1.102 |
| 10,000 | 121,767 | 30.52% | 0.777 | 1.018 |
To reach a recall of 0.78 it examines 31% of the vectors. The indexes of the following articles are judged on the same two axes, recall against distance computations, and do far better.
The Johnson–Lindenstrauss lemma
If the dimension is the difficulty, can it be reduced? The Johnson–Lindenstrauss lemma says that any finite set of points can be mapped into a space whose dimension depends only on the number of points and the accuracy wanted, not on the original dimension, with all pairwise distances nearly preserved. Johnson and Lindenstrauss (1984) proved it. (Their paper was not opened for this article; the statement and the attribution follow Dasgupta and Gupta.) The proof given here is the elementary one of Dasgupta and Gupta (2003).
Theorem (Johnson and Lindenstrauss; in the form of Dasgupta and Gupta, 2003, Theorem 2.1). Let $0 < \varepsilon < 1$, let $n$ be a positive integer, and let $\ell$ be a positive integer with
$$\ell \ge \frac{4 \ln n}{\varepsilon^2/2 - \varepsilon^3/3} .$$
Then for any set $V$ of $n$ points in $\mathbb{R}^m$ there is a map $f : \mathbb{R}^m \to \mathbb{R}^\ell$ such that for all $\vec u, \vec v \in V$,
$$(1 - \varepsilon)\, \lvert \vec u - \vec v \rvert^2 \;\le\; \lvert f(\vec u) - f(\vec v) \rvert^2 \;\le\; (1 + \varepsilon)\, \lvert \vec u - \vec v \rvert^2 .$$
The map is a projection onto a random $\ell$-dimensional subspace, scaled by $\sqrt{m/\ell}$, and the proof shows that a random choice works with probability at least $1/n$.
Here is the plan of the proof. A projection onto $\ell$ of $m$ orthonormal directions keeps, on average, the share $\ell/m$ of a vector's squared length. The lemma below shows that for a random projection the share kept is very unlikely to differ from $\ell/m$ by a factor of $1 \pm \varepsilon$: the probability is at most $1/n^2$ on each side when $\ell$ is as large as the theorem asks. A set of $n$ points has fewer than $n^2/2$ pairs, so with positive probability no pair's distance is distorted by more. The work is in the lemma, which is a calculation with normal variables.
Three facts about normal variables
Let $X_1, \dots, X_m$ be independent standard normal variables and $X = (X_1, \dots, X_m)$.
Fact 1 (the moment generating function of a square). For $s < \tfrac12$, $E[e^{sX_1^2}] = (1 - 2s)^{-1/2}$. Proof. By the definition of the normal density,
$$E\!\left[e^{sX_1^2}\right] = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} e^{sx^2} e^{-x^2/2}\, dx = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} e^{-(1 - 2s)x^2/2}\, dx .$$
Substitute $y = x\sqrt{1 - 2s}$, which is allowed because $1 - 2s > 0$. Then $dx = dy/\sqrt{1 - 2s}$ and the integral becomes $(1 - 2s)^{-1/2}$ times $\tfrac{1}{\sqrt{2\pi}}\int e^{-y^2/2}\, dy = 1$. For $s \ge \tfrac12$ the integral diverges. $\blacksquare$
Fact 2 (rotation invariance). For every orthogonal matrix $W$ (a rotation or reflection of $\mathbb{R}^m$), $WX$ has the same distribution as $X$. Proof. The joint density of $X$ is the product of the $m$ normal densities, $(2\pi)^{-m/2} e^{-\lvert x \rvert^2/2}$, which depends on $x$ only through its length. An orthogonal matrix preserves lengths and volumes, so the density of $WX$ at a point $y$ is the density of $X$ at $W^{\mathsf T}y$, which has the same length as $y$. The two densities are equal. $\blacksquare$
It follows that the unit vector $Y = X / \lvert X \rvert$ satisfies the same property: $WY = WX/\lvert WX \rvert$ has the distribution of $Y$. We call a random unit vector with this distribution a uniformly random unit vector. ($X$ is the zero vector with probability 0.)
Fact 3 (a fixed vector seen from a random frame). Let $G$ be an $m \times m$ matrix of independent standard normal entries, and let $R$ be the orthogonal matrix whose rows $\vec r_1, \dots, \vec r_m$ are obtained from the rows of $G$ by the Gram–Schmidt process. (The rows of $G$ are linearly independent with probability 1.) Then for every fixed unit vector $\vec w$, the vector $R\vec w$ has the distribution of $Y$.
Proof. First, for any fixed orthogonal $W$, the matrix $RW$ has the same distribution as $R$. The rows of $GW$ are the rows of $G$ each transformed by $W^{\mathsf T}$, so by Fact 2 they are again independent standard normal vectors, and $GW$ has the distribution of $G$. The Gram–Schmidt process uses only dot products between rows, which $W$ preserves, so applying it to $GW$ gives $RW$. Hence $RW$ has the distribution of $R$.
Second, the distribution of $R\vec w$ is the same for every unit vector $\vec w$. Given two unit vectors $\vec w$ and $\vec w'$, choose an orthogonal $W$ with $W\vec w' = \vec w$. Then $R\vec w = (RW)\vec w'$, which has the distribution of $R\vec w'$ by the first step.
Third, let $Y'$ be a uniformly random unit vector independent of $R$. For each fixed value of $R$, the vector $RY'$ has the distribution of $Y$ by Fact 2, so $RY'$ has the distribution of $Y$. On the other hand, for each fixed value $\vec w$ of $Y'$, the vector $R\vec w$ has one and the same distribution, by the second step. So $RY'$ also has that distribution. The two descriptions agree: $R\vec w$ has the distribution of $Y$. $\blacksquare$
Fact 3 is what lets a random projection of a fixed vector be studied as a fixed projection of a random vector. The first $\ell$ coordinates of $R\vec w$ are the dot products $\vec r_1 \cdot \vec w, \dots, \vec r_\ell \cdot \vec w$, which are the coordinates of the orthogonal projection of $\vec w$ onto the subspace spanned by $\vec r_1, \dots, \vec r_\ell$. That subspace is the random $\ell$-dimensional subspace of the theorem. In code, $\vec r_1, \dots, \vec r_\ell$ are the columns of the factor $Q$ in a QR factorization of an $m \times \ell$ matrix of normal entries (up to signs, which do not affect lengths).
The lemma
Lemma (Dasgupta and Gupta, 2003, Lemma 2.2). Let $\ell < m$, let $Y = (Y_1, \dots, Y_m)$ be a uniformly random unit vector, and let $L = Y_1^2 + \dots + Y_\ell^2$ be the squared length of its first $\ell$ coordinates. Then $E[L] = \ell/m$, and
- (a) for $0 < \beta < 1$: $\quad P\!\left(L \le \dfrac{\beta\ell}{m}\right) \le \beta^{\ell/2} \left(1 + \dfrac{(1 - \beta)\ell}{m - \ell}\right)^{(m - \ell)/2} \le \exp\!\left(\dfrac{\ell}{2}\,(1 - \beta + \ln\beta)\right)$;
- (b) for $\beta > 1$ with $\beta\ell < m$: $\quad P\!\left(L \ge \dfrac{\beta\ell}{m}\right) \le$ the same two expressions.
For $\beta\ell \ge m$ the event in (b) has probability 0, because $L \le 1$ always and $L = 1$ only if the last $m - \ell$ coordinates vanish.
Proof of the mean. Exchanging two coordinates is an orthogonal map, so by Fact 2 every $Y_j^2$ has the same mean. The squares add to 1, so each mean is $1/m$ and $E[L] = \ell/m$.
Proof of (a). Write $Y = X/\lvert X \rvert$. Then $L = (X_1^2 + \dots + X_\ell^2)/(X_1^2 + \dots + X_m^2)$, and the event $L \le \beta\ell/m$ is
$$\beta\ell\,(X_1^2 + \dots + X_m^2) - m\,(X_1^2 + \dots + X_\ell^2) \ge 0 .$$
Call the left side $S$. Collecting the coefficient of each square,
$$S = (\beta\ell - m)\sum_{j \le \ell} X_j^2 + \beta\ell \sum_{j > \ell} X_j^2 .$$
For any $t > 0$ the event $S \ge 0$ is the event $e^{tS} \ge 1$, and by Markov's inequality $P(e^{tS} \ge 1) \le E[e^{tS}]$. The $X_j$ are independent, so the expectation is a product of $m$ factors, each given by Fact 1:
$$E\!\left[e^{tS}\right] = \bigl(1 - 2t(\beta\ell - m)\bigr)^{-\ell/2}\,\bigl(1 - 2t\beta\ell\bigr)^{-(m - \ell)/2} .$$
Fact 1 requires $t(\beta\ell - m) < \tfrac12$, which holds for every $t > 0$ because $\beta\ell < m$, and $t\beta\ell < \tfrac12$. Any $t$ between 0 and $1/(2\beta\ell)$ therefore gives a valid bound. Choose
$$t_0 = \frac{1 - \beta}{2\beta\,(m - \beta\ell)},$$
the value that makes the bound smallest (setting the derivative of its logarithm to zero gives it). It is positive because $\beta < 1$, and it is below $1/(2\beta\ell)$ because $(1 - \beta)\ell < m - \beta\ell$ is the same as $\ell < m$. At $t_0$ the two bases are
$$1 - 2t_0(\beta\ell - m) = 1 + \frac{1 - \beta}{\beta} = \frac1\beta, \qquad 1 - 2t_0\beta\ell = 1 - \frac{(1 - \beta)\ell}{m - \beta\ell} = \frac{m - \ell}{m - \beta\ell} .$$
So
$$P\!\left(L \le \frac{\beta\ell}{m}\right) \le \beta^{\ell/2} \left(\frac{m - \beta\ell}{m - \ell}\right)^{(m - \ell)/2} = \beta^{\ell/2}\left(1 + \frac{(1 - \beta)\ell}{m - \ell}\right)^{(m - \ell)/2},$$
which is the first bound. For the second, $1 + x \le e^x$ for every real $x$. With $x = (1 - \beta)\ell/(m - \ell)$ the last factor is at most $\exp\bigl((1 - \beta)\ell/2\bigr)$, and $\beta^{\ell/2} = \exp\bigl((\ell/2)\ln\beta\bigr)$. $\blacksquare$
Proof of (b). Now $\beta > 1$ and $\beta\ell < m$. The event $L \ge \beta\ell/m$ is $-S \ge 0$, where
$$-S = (m - \beta\ell)\sum_{j \le \ell} X_j^2 - \beta\ell\sum_{j > \ell} X_j^2 .$$
For $t > 0$, Markov's inequality and Fact 1 give
$$P(-S \ge 0) \le E\!\left[e^{-tS}\right] = \bigl(1 - 2t(m - \beta\ell)\bigr)^{-\ell/2}\,\bigl(1 + 2t\beta\ell\bigr)^{-(m - \ell)/2},$$
valid when $t(m - \beta\ell) < \tfrac12$; the second factor needs no condition, since its exponent coefficient $-t\beta\ell$ is negative. Choose
$$t_1 = \frac{\beta - 1}{2\beta\,(m - \beta\ell)},$$
which is positive, with $2t_1(m - \beta\ell) = (\beta - 1)/\beta < 1$. At $t_1$ the two bases are
$$1 - 2t_1(m - \beta\ell) = \frac1\beta, \qquad 1 + 2t_1\beta\ell = 1 + \frac{(\beta - 1)\ell}{m - \beta\ell} = \frac{m - \ell}{m - \beta\ell},$$
the same two values as in (a). The bound is again $\beta^{\ell/2}\bigl((m - \beta\ell)/(m - \ell)\bigr)^{(m - \ell)/2}$, and the second inequality follows as before from $1 + x \le e^x$, now with the negative number $x = (1 - \beta)\ell/(m - \ell)$, for which $1 + x = (m - \beta\ell)/(m - \ell)$ is still positive. $\blacksquare$
The simulation agrees with the lemma. For $m = 100$ and $\ell = 20$ the script draws 200,000 uniformly random unit vectors per seed. The mean of $L$ in the first seed is 0.2002, against $\ell/m = 0.2$. The observed tail probabilities (median over 30 seeds) lie below both bounds:
| Event | Simulated | First bound | Second bound |
|---|---|---|---|
| $L \le 0.5\,\ell/m$ | 0.021470 | 0.108593 | 0.144935 |
| $L \le 0.25\,\ell/m$ | 0.000130 | 0.000922 | 0.001724 |
| $L \ge 1.5\,\ell/m$ | 0.047878 | 0.276207 | 0.388544 |
| $L \ge 2\,\ell/m$ | 0.001035 | 0.010298 | 0.046490 |
Proof of the theorem
If $m \le \ell$, let $f$ copy the $m$ coordinates and fill the rest with zeros. All distances are preserved exactly.
Otherwise $\ell < m$. Draw $R$ as in Fact 3 and define $f(\vec x) = \sqrt{m/\ell}\,\bigl(\vec r_1 \cdot \vec x, \dots, \vec r_\ell \cdot \vec x\bigr)$. The map is linear. Fix a pair $\vec u \ne \vec v$ in $V$ and let $\vec w = (\vec u - \vec v)/\lvert \vec u - \vec v \rvert$. Then
$$\frac{\lvert f(\vec u) - f(\vec v) \rvert^2}{\lvert \vec u - \vec v \rvert^2} = \lvert f(\vec w) \rvert^2 = \frac{m}{\ell}\, L,$$
where $L$ is the squared length of the first $\ell$ coordinates of $R\vec w$. By Fact 3, $R\vec w$ is a uniformly random unit vector, so the lemma applies to $L$.
The lower side. The ratio is below $1 - \varepsilon$ exactly when $L < (1 - \varepsilon)\ell/m$. By part (a) with $\beta = 1 - \varepsilon$,
$$P\!\left(\tfrac{m}{\ell} L \le 1 - \varepsilon\right) \le \exp\!\left(\tfrac{\ell}{2}\bigl(\varepsilon + \ln(1 - \varepsilon)\bigr)\right) \le \exp\!\left(-\tfrac{\ell\varepsilon^2}{4}\right) \le \exp(-2\ln n) = \frac{1}{n^2} .$$
The second step uses $\ln(1 - x) \le -x - x^2/2$ for $0 \le x < 1$. (The function $h(x) = -x - x^2/2 - \ln(1 - x)$ has $h(0) = 0$ and $h'(x) = -1 - x + 1/(1 - x) = x^2/(1 - x) \ge 0$, so $h \ge 0$.) The third uses the theorem's condition, which implies $\ell \ge 4\ln n/(\varepsilon^2/2) = 8\ln n/\varepsilon^2$.
The upper side. If $(1 + \varepsilon)\ell \ge m$ the ratio cannot exceed $1 + \varepsilon$ except with probability 0. Otherwise part (b) with $\beta = 1 + \varepsilon$ gives
$$P\!\left(\tfrac{m}{\ell} L \ge 1 + \varepsilon\right) \le \exp\!\left(\tfrac{\ell}{2}\bigl(-\varepsilon + \ln(1 + \varepsilon)\bigr)\right) \le \exp\!\left(-\tfrac{\ell}{2}\left(\tfrac{\varepsilon^2}{2} - \tfrac{\varepsilon^3}{3}\right)\right) \le \exp(-2\ln n) = \frac{1}{n^2} .$$
The second step uses $\ln(1 + x) \le x - x^2/2 + x^3/3$ for $x \ge 0$. (The function $g(x) = x - x^2/2 + x^3/3 - \ln(1 + x)$ has $g(0) = 0$ and $g'(x) = 1 - x + x^2 - 1/(1 + x) = x^3/(1 + x) \ge 0$.) The third is the theorem's condition on $\ell$.
All pairs. A given pair is distorted beyond $1 \pm \varepsilon$ with probability at most $2/n^2$. There are $n(n - 1)/2$ pairs, so the probability that some pair is distorted is at most $\tfrac{n(n-1)}{2} \cdot \tfrac{2}{n^2} = 1 - \tfrac1n$. With probability at least $1/n$ no pair is, and a map with the stated property exists. $\blacksquare$
The probability $1/n$ is what the proof guarantees, not what happens. Drawing the projection again and again until it works takes on average at most $n$ attempts, and each attempt can be checked.
What the lemma gives a search, and what it does not
Corollary. If $f$ preserves all squared distances among the points of $V \cup \{\vec q\}$ within factors $1 \pm \varepsilon$, then the nearest neighbor of $f(\vec q)$ among the images is a $c$-approximate nearest neighbor of $\vec q$ with $c = \sqrt{(1 + \varepsilon)/(1 - \varepsilon)}$. Proof. Let $\vec x^*$ be the true nearest neighbor of $\vec q$ and $\vec x'$ the point whose image is nearest to $f(\vec q)$. Then
$$\lvert \vec q - \vec x' \rvert^2 \le \frac{\lvert f(\vec q) - f(\vec x') \rvert^2}{1 - \varepsilon} \le \frac{\lvert f(\vec q) - f(\vec x^*) \rvert^2}{1 - \varepsilon} \le \frac{1 + \varepsilon}{1 - \varepsilon}\, \lvert \vec q - \vec x^* \rvert^2 . \;\blacksquare$$
The dimension the theorem asks for depends on $n$ and $\varepsilon$ only:
| Points $n$ | $\varepsilon = 0.5$ | $\varepsilon = 0.25$ | $\varepsilon = 0.1$ |
|---|---|---|---|
| 1,000 | 332 | 1,062 | 5,921 |
| 11,264 | 448 | 1,433 | 7,997 |
| 400,000 | 620 | 1,982 | 11,057 |
| 1,000,000,000 | 995 | 3,184 | 17,763 |
Example (a lemma that does not apply to this unit's data). For the 400,000 GloVe vectors the theorem asks for 620 dimensions at $\varepsilon = 0.5$, more than the 100 the vectors already have. The lemma promises nothing here. It is a statement about very high dimensions: a million-dimensional set of 400,000 points can be brought down to 620 dimensions with every squared distance within a factor of $1 \pm 0.5$, and no further by this argument.
Where the lemma applies, it holds with room to spare. The script takes 1,000 points with independent normal coordinates in 5,000 dimensions, for which the theorem asks for $\ell \ge 332$ at $\varepsilon = 0.5$, and projects them onto a random subspace, 30 times for each $\ell$. The table gives medians over the seeds for the ratio of projected to original squared distance over all 499,500 pairs.
| $\ell$ | Smallest ratio | Largest ratio | Pairs off by more than 0.5 | Seeds with every pair within 0.5 |
|---|---|---|---|---|
| 332 | 0.690 | 1.398 | 0.0 | 30 of 30 |
| 200 | 0.611 | 1.517 | 2.0 | 7 of 30 |
| 100 | 0.474 | 1.795 | 389.0 | 0 of 30 |
| 50 | 0.321 | 2.199 | 6,625.0 | 0 of 30 |
| 25 | 0.182 | 2.827 | 34,366.5 | 0 of 30 |
At the theorem's dimension every pair was within the bound in all 30 seeds, although the proof promises success only once in a thousand attempts. The largest distortion there was about 0.40, not 0.5. At $\ell = 200$, well below what the theorem asks, only a handful of the 499,500 pairs were off by more than 0.5. The bound is sufficient, not necessary.
On the GloVe vectors, below any guarantee, the projection can still be tried as an index: project base and queries to $\ell$ dimensions, scan in the projection, and compare with the truth. The scan costs $N\ell$ multiplications instead of $Nm$.
| $\ell$ | Recall@10 in the projection | True ten among the projected top 100 | Squared-distance ratio: standard deviation |
|---|---|---|---|
| 10 | 0.016 (0.016 to 0.018) | 0.066 | 0.419 |
| 25 | 0.105 (0.104 to 0.106) | 0.290 | 0.243 |
| 50 | 0.303 (0.299 to 0.304) | 0.677 | 0.140 |
| 75 | 0.528 (0.525 to 0.531) | 0.939 | 0.081 |
The recall falls quickly as coordinates are dropped. Even three quarters of the dimensions keep only 0.53 of the true ten, because the neighbors' distances differ by less than the distortion a random projection introduces. Re-ranking the projected top 100 by their true distances recovers more (third column), at the cost of 100 more distance computations. Random projection treats all directions alike, and the later articles of the unit reduce the cost of a distance in ways fitted to the data instead: product quantization learns its compression from the vectors.
The lemma's use in this subject is in its theory. Dasgupta and Gupta list approximate nearest neighbor search among its applications, citing Indyk and Motwani (1998), and the proof technique, a tail bound for each pair followed by a union over pairs, returns in the analysis of locality-sensitive hashing.
What is proved, what is cited, what the experiments show
Proved on this page. The explicit bound on the ratio of farthest to nearest distance from the relative variance, and from it the theorem of Beyer and colleagues; the relative variance $7/(5m)$ for uniform coordinates and $1/m$ for random directions (the latter from the proposition in cosine similarity); the three facts about normal variables; the lemma and the theorem of Johnson and Lindenstrauss in the form of Dasgupta and Gupta; the corollary for search. The correctness of the k-d tree's search follows from the definition of the cell distance.
Cited. The expected logarithmic search time of the k-d tree for fixed dimension and the $2^m$ vectors examined under the maximum norm, a lower bound (Friedman, Bentley, and Finkel, 1977, read in the preprint); the conclusion that, under their cost model, a sequential scan outperforms partitioning and clustering methods on average above about ten dimensions (Weber, Schek, and Blott, 1998); the best known query-time bound with near-linear storage (Har-Peled, Indyk, and Motwani, 2012); the cases Beyer and colleagues name in which nearest neighbor search stays meaningful.
Observed in the experiments, on this data and this machine. The shares of vectors a k-d tree examines; the ratios of farthest to nearest distance; the contrast between real embeddings and synthetic data; the recall of a stopped tree and of a random projection; all timings. The explanation of the k-d tree's failure by the depth of the tree rests on the measured distances to its cells. It is an observation about these trees and this data, not a theorem.
Worked problems
The unit has no course assignments, so the problems are posed on the eight points of the example, on the unit's GloVe data and on small exact cases. The script recomputes every number.
Problem 1 (a k-d tree search by hand). For the eight points $A$ to $H$ and the tree built above, find the nearest neighbor of $\vec q = (2.5, 8)$, listing each leaf opened and each subtree skipped.
Descent. $x_1 = 2.5 < 6$: left. $x_2 = 8 \ge 7$: right, to the leaf $\{B, D\}$. Squared distances: $B = (2, 7)$ gives $0.5^2 + 1^2 = 1.25$, and $D = (4, 9)$ gives $1.5^2 + 1^2 = 3.25$. Best so far: $B$ at 1.25.
Climbing. The sibling cell, of $\{A, C\}$, lies below $x_2 = 7$, at offset $8 - 7 = 1$, squared distance $1 \le 1.25$. It must be opened: $A$ is at $1.5^2 + 6^2 = 38.25$ and $C$ at $0.5^2 + 4^2 = 16.25$. No improvement. At the root, the right cell lies at $x_1 \ge 6$, at offset $6 - 2.5 = 3.5$, squared distance $12.25 > 1.25$. The whole right subtree, four points, is skipped.
Answer. $B$, at distance $\sqrt{1.25} = 1.118$, after four distance computations and one skipped subtree. The sibling leaf had to be opened although it held nothing useful: its cell came within the ball, and a cell's distance is only a lower bound on the distances of its points.
Problem 2 (the bound on the ratio for uniform data). For $n = 10{,}000$ uniform points in the unit cube and squared Euclidean distance, how large must $m$ be for the proposition to guarantee that the farthest point is at most twice as far as the nearest with probability at least 0.9? What does the simulation show at $m = 64$?
Solution. Here $p = 2$ and $1 + \varepsilon = 2$, so $\delta = (2^2 - 1)/(2^2 + 1) = 3/5$. The relative variance is $7/(5m)$, and the bound is $1 - n \cdot \tfrac{7}{5m} \cdot \tfrac{1}{\delta^2} = 1 - \tfrac{7 \times 10{,}000 \times 25}{5 \times 9\, m} = 1 - \tfrac{350{,}000}{9m}$. It is at least 0.9 when $m \ge 350{,}000/0.9 = 388{,}889$ (rounded up). The simulation already shows a ratio of 1.72 at $m = 64$, with the farthest point within twice the nearest for 100% of the queries. The proposition is a proof of the limit and a poor estimate of the rate.
Problem 3 (recall and distance ratio of an answer). For neighborhood the true ten nearest are neighborhoods, neighbourhood, suburb, downtown, residential, area, suburban, city, town, apartment, at distances 0.582 to 0.798. The k-d tree stopped after 100 leaves returns neighborhoods, downtown, area, town, suburbs, nearby, village, residents, streets, crowded. Compute its recall@10.
Solution. The words of the answer that are among the true ten: neighborhoods, downtown, area, town. That is 4 of 10, so recall@10 is 0.4. The order of the answer plays no part, and neither do the distances of the wrong words.
Problem 4 (how many dimensions, and what approximation). A set of $n = 1{,}000$ points is to be projected so that every squared distance is preserved within $\varepsilon = 0.5$. How many dimensions does the theorem ask for, and what approximation factor does the corollary then give for a nearest neighbor found in the projection?
Solution. $\varepsilon^2/2 - \varepsilon^3/3 = 0.125 - 0.041667 = 0.083333$, and $\ln 1{,}000 = 6.9078$, so $\ell \ge 4 \times 6.9078 / 0.083333 = 331.6$: the theorem asks for $\ell = 332$. The corollary needs the distances from the query preserved as well, so the theorem must be applied to the 1,000 points and the query together. For 1,001 points the bound is $4 \ln 1{,}001/0.083333 = 331.6$ again, and the theorem still asks for 332 dimensions. The corollary then gives $c = \sqrt{1.5/0.5} = \sqrt3 = 1.732$, for a projection that succeeds, which the proof guarantees with probability at least $1/1{,}001$. The original dimension does not enter: the answer is the same for points in 5,000 dimensions and in five million.
Problem 5 (the lemma's bound at one point). For $m = 100$ and $\ell = 20$, bound the probability that a uniformly random unit vector keeps at most half of its expected squared length in its first 20 coordinates.
Solution. Half the expected share is $\beta = 0.5$, the event $L \le 0.1$. The first bound is $0.5^{10} \times (1 + 0.5 \times 20/80)^{40} = 0.000977 \times 1.125^{40} = 0.000977 \times 111.2 = 0.1086$. The second is $\exp\bigl(10\,(1 - 0.5 + \ln 0.5)\bigr) = \exp(-1.9315) = 0.1449$. The simulated probability is 0.0215. Both bounds hold, and the first is the sharper, as the lemma says.
What we have learned
Exact nearest neighbor search is easy to state and, in many dimensions, no cheaper than comparing the query with everything. A full scan costs $Nm$ multiplications, and for some thousands of vectors, such as this site's passages, it is the right method. The k-d tree, which answers exactly in logarithmic expected time in a few dimensions, examined 97% of the GloVe vectors, because a tree of feasible depth bounds its cells in only a few of the hundred coordinates. Distances concentrate: when the relative variance of the distance vanishes, the farthest of a fixed number of points is, with probability approaching 1, no more than $1 + \varepsilon$ times as far as the nearest, and the proof is one application of Chebyshev's inequality. Real embeddings are concentrated in the bulk and not in the lower tail, which is why searching them is meaningful. An approximate index is judged by its recall@$k$, the share of the true $k$ nearest that it returns, against the number of distances it computes. The Johnson–Lindenstrauss lemma reduces any $n$ points to about $8\ln n/\varepsilon^2$ dimensions with squared distances preserved within $1 \pm \varepsilon$, which helps only when the original dimension is far larger than that.
The first index that gives up exactness on purpose does so by chance: it hashes the vectors so that near ones are likely to collide, and looks only at the collisions. That is locality-sensitive hashing.
References
- Aumüller, M., Bernhardsson, E., and Faithfull, A. (2020). ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87, 101374. record · 3 pages
- Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509–517. record
- Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. (1999). When is "nearest neighbor" meaningful? In C. Beeri and P. Buneman (Eds.), Database Theory: ICDT'99 (Lecture Notes in Computer Science, Vol. 1540, pp. 217–235). Springer. record · 3 pages
- Dasgupta, S., and Gupta, A. (2003). An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures & Algorithms, 22(1), 60–65. record
- Friedman, J. H., Bentley, J. L., and Finkel, R. A. (1977). An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3(3), 209–226. record
- Har-Peled, S., Indyk, P., and Motwani, R. (2012). Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of Computing, 8, 321–350. record · 2 pages
- Indyk, P., and Motwani, R. (1998). Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of STOC 1998, 604–613. record · 3 pages
- Johnson, W. B., and Lindenstrauss, J. (1984). Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26, 189–206. American Mathematical Society. record
- Pennington, J., Socher, R., and Manning, C. D. (2014). GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 1532–1543. record · 5 pages
- Weber, R., Schek, H.-J., and Blott, S. (1998). A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB '98), 194–205. record