Locality-Sensitive Hashing

Hash functions that collide more often for near vectors than for far ones, and the index built from them. The definition of a sensitive family, the random-hyperplane family with collision probability 1 − θ/π, tables of concatenated bits and the S-curve they produce in the angle, the proof that the index answers an approximate near neighbor query with N^ρ distance computations, a family for Euclidean distance with its collision probability derived, and measurements on 399,000 word vectors, where the theory predicts the recall and the cost and the cost turns out high. Worked problems choose the parameters for a target recall and for the theorem.

The vector of neighborhood makes an angle of 33.8 degrees with that of neighborhoods, its nearest neighbor among 399,000 word vectors, and an angle of 84.1 degrees with that of cheese. Cut the space by a random plane through the origin. The plane separates neighborhood from neighborhoods with probability $33.8/180 = 0.188$ and from cheese with probability $84.1/180 = 0.467$. One plane says little, but 64 planes give each word a 64-bit code, and the codes of the first pair agree in 51 bits while those of the second agree in 37. Can such codes serve as an index that finds the near vectors of a query without comparing it with all the others, and can anything be proved about how well?

Both, and the proof is short. A locality-sensitive hash family is a set of hash functions from which a random member makes near items collide with higher probability than far ones. From any such family one can build an index of several hash tables whose query time grows like $N^\rho$ for an exponent $\rho < 1$ that depends on the two collision probabilities: fewer distance computations than the $N$ of a scan, with a guarantee that holds for every dataset. This article proves that theorem, due to Indyk and Motwani (1998). It also measures the index on the unit's data, where the theory predicts the measured recall within 0.002 and the practical result is sobering: with random hyperplanes and 32 tables, a recall@10 of 0.91 costs the comparison of 25% of all vectors with the query, and keeping the recall near 0.9 at a smaller share is predicted to take hundreds of tables (Problem 2).

Here is the route. First we recall what the course established for sets, and state the general definition that covers sets and vectors alike. Then the random-hyperplane family is checked on the running example and on 200,000 pairs. Next the gap between near and far is amplified by concatenating bits and repeating tables, the index is built, and its recall and cost are predicted from the angles alone and measured. Then comes the query-time theorem with its proof and a run of the proof's own construction. A last section derives the collision probability of a family for Euclidean distance. The article assumes near-duplicate detection, where MinHash, banding and the hyperplane argument are worked out, and nearest neighbor search in high dimensions for the data, recall and the approximate problem. The numbers come from tools/experiments/vectors/locality-sensitive-hashing.py.

From sets to vectors

The course met this idea in near-duplicate detection, for documents represented as sets of shingles. Three results were proved there, and this article uses them without repeating the proofs.

  • MinHash. For a random permutation of the shingles, two sets have the same minimum with probability equal to their Jaccard coefficient.
  • Banding. If two sketches agree in each position independently with probability $s$, and the sketch is cut into $b$ bands of $r$ positions, the pair agrees on all positions of at least one band with probability $1 - (1 - s^r)^b$. The curve is S-shaped, with its steep part near $s = (1/b)^{1/r}$.
  • Random hyperplanes. Two vectors at angle $\theta$ fall on the same side of a random hyperplane through the origin with probability $1 - \theta/\pi$.

That article used them to find all similar pairs in a collection. Here the task is a query: given a vector that is not in the collection, find its near neighbors. The objects are dense vectors, and the angles between near neighbors are far larger than the few degrees that separate near-duplicate pages. Three things are added: the definition that makes "MinHash" and "hyperplanes" instances of one notion, a theorem about the query time of the resulting index, and the measurement of what the index costs when the neighbors are 40 to 50 degrees away.

Sensitive families

Let $D$ be a distance between items, and let $\mathcal{H}$ be a set of hash functions with a rule for drawing one at random. For distances $d_1 < d_2$ and probabilities $p_1 > p_2$, the family is $(d_1, d_2, p_1, p_2)$-sensitive if for any two items $x$ and $y$,

  • if $D(x, y) \le d_1$, then $P(h(x) = h(y)) \ge p_1$;
  • if $D(x, y) > d_2$, then $P(h(x) = h(y)) \le p_2$.

The probability is over the random choice of $h$; the items are fixed. Nothing is required of pairs at distances between $d_1$ and $d_2$. This is the definition of Indyk and Motwani (1998) as stated by Har-Peled, Indyk, and Motwani (2012, Definition 3.3), who write $r_1$ and $r_2$ for the two distances. (It is Definition 7 in an extended preliminary version of the 1998 paper dated 30 December 1999, the version of that paper read here; the STOC text itself was not opened.)

Three families that fit the definition:

  • Bit sampling for binary strings of length $d$ under the Hamming distance: $h$ returns the bit at a random position. Two strings that differ in $D$ positions collide with probability $1 - D/d$, so the family is $(d_1, d_2, 1 - d_1/d, 1 - d_2/d)$-sensitive. This is the family of the original analysis (Har-Peled, Indyk, and Motwani, 2012, Proposition 3.8).
  • MinHash for sets under the Jaccard distance $1 - J$: the collision probability is $J$, so the family is $(d_1, d_2, 1 - d_1, 1 - d_2)$-sensitive for any $d_1 < d_2$.
  • Random hyperplanes for vectors under the angle: the collision probability is $1 - \theta/\pi$, so the family is $(\theta_1, \theta_2, 1 - \theta_1/\pi, 1 - \theta_2/\pi)$-sensitive for any angles $\theta_1 < \theta_2$. For unit vectors the Euclidean distance is $2\sin(\theta/2)$, an increasing function of the angle, so the same family is sensitive for Euclidean distance on the unit sphere.

In all three the collision probability is not merely bounded: it is an exact, decreasing function of the distance. Charikar (2002) took that as the definition, asking for a family with $P(h(x) = h(y)) = \mathrm{sim}(x, y)$ for a given similarity function, and proved a necessary condition that rules such a family out for some common similarities, the Dice and Overlap coefficients among them (his section 2).

Proposition (Charikar, 2002, Lemma 1). If a family satisfies $P(h(x) = h(y)) = \mathrm{sim}(x, y)$ for all $x, y$, then $1 - \mathrm{sim}$ obeys the triangle inequality: $1 - \mathrm{sim}(x, z) \le \bigl(1 - \mathrm{sim}(x, y)\bigr) + \bigl(1 - \mathrm{sim}(y, z)\bigr)$.

Proof. For a fixed $h$, let $\Delta(x, y)$ be 1 if $h(x) \ne h(y)$ and 0 otherwise. Then $\Delta(x, z) \le \Delta(x, y) + \Delta(y, z)$: the right side is 0 only if $h(x) = h(y)$ and $h(y) = h(z)$, and then $h(x) = h(z)$ and the left side is 0 too. Taking the expectation over $h$ on both sides gives the claim, because $E[\Delta(x, y)] = P(h(x) \ne h(y)) = 1 - \mathrm{sim}(x, y)$. $\blacksquare$

The proposition explains why the hyperplane family estimates the angle and not the cosine. The angle is a distance on the sphere, and it obeys the triangle inequality. The quantity $1 - \cos\theta$ does not (Problem 5 gives three vectors that violate it), so no family of hash functions can have the cosine itself as its collision probability.

Random hyperplanes on the running example

The hash of a vector $\vec x$ under a direction $\vec g$ is one bit,

$$h_{\vec g}(\vec x) = \begin{cases} 1 & \text{if } \vec g \cdot \vec x \ge 0, \\ 0 & \text{otherwise,} \end{cases}$$

and a random member of the family is obtained by drawing the $m$ coordinates of $\vec g$ independently from the standard normal distribution (Charikar, 2002, §3). The hyperplane is the set of vectors perpendicular to $\vec g$, and the bit says on which side of it $\vec x$ lies. For two vectors at angle $\theta$,

$$P\bigl(h_{\vec g}(\vec x) = h_{\vec g}(\vec y)\bigr) = 1 - \frac{\theta}{\pi} .$$

Near-duplicate detection proves this in full: only the part of $\vec g$ in the plane of the two vectors matters, its direction in that plane is uniform over the circle, and the bits differ on two arcs of length $\theta$. We write $p(\theta) = 1 - \theta/\pi$ from here on. Computing one bit costs one dot product in $m$ dimensions, the same as one distance computation between unit vectors.

For neighborhood and its ten nearest neighbors (and cheese for contrast):

Word Angle to neighborhood (degrees) $p = 1 - \theta/\pi$
neighborhoods 33.8 0.812
neighbourhood 37.0 0.794
suburb 42.9 0.762
downtown 43.5 0.758
residential 44.3 0.754
area 45.3 0.748
suburban 45.4 0.748
city 45.9 0.745
town 46.1 0.744
apartment 47.0 0.739
cheese 84.1 0.533

The collision probabilities of the true neighbors lie between 0.74 and 0.81. An unrelated word is near 90 degrees and has $p$ near 0.5. That is the whole signal a single bit carries: a difference of about a quarter in the probability of agreeing.

Example (64 bits). With the 64 hyperplanes of seed 0, the code of neighborhood agrees with that of neighborhoods in 51 bits, where $64 \times 0.812 = 52.0$ are expected. It agrees with neighbourhood in 50, with suburb in 50 and with cheese in 37, where $64 \times 0.533 = 34.1$ are expected. The first 16 bits of neighborhood are 0101001001010110 and those of neighborhoods are 0111001011010110, differing in 2 places.

The script checks the formula on 200,000 pairs: each of the 1,000 queries with its 100 nearest base vectors and with 100 base vectors drawn at random. Each pair is hashed with 256 hyperplanes under each of 30 seeds, 7,680 bits in all, and the observed share of agreeing bits is compared with $1 - \theta/\pi$.

Angle (degrees) Pairs Observed agreement $1 - \theta/\pi$ (mean over the pairs)
10 to 20 286 0.8997 0.9022
20 to 30 1,633 0.8537 0.8538
30 to 40 7,347 0.8014 0.8017
40 to 50 28,015 0.7456 0.7447
50 to 60 44,506 0.6940 0.6936
60 to 70 30,066 0.6458 0.6454
70 to 80 28,372 0.5812 0.5804
80 to 90 37,857 0.5285 0.5281
90 to 100 18,912 0.4787 0.4786
100 to 110 2,824 0.4270 0.4271
110 to 120 170 0.3729 0.3741

For a single pair, the count of agreeing bits is binomial with 7,680 trials, so its expected deviation from the formula is 0. Standardized by the binomial mean and standard deviation, the 200,000 counts have a standard deviation of 0.995, as they should, and a mean of 0.08. The pairs are not independent of one another: all of them are hashed by the same hyperplanes, and the 200 pairs of one query share that query's bits. Dependence does not shift the mean. It makes the average of the 200,000 values vary far more than independent counts would. The seeds show by how much: the 30 per-seed averages have a standard deviation of 0.064, which is the standard error of the overall mean, so 0.08 is 1.2 standard errors from 0. The usual division by $\sqrt{30}$ does not apply here, for this reason. Each seed contributes 256 of the 7,680 trials. Standardized seed by seed, a pair's deviation is the sum of its 30 per-seed deviations divided by $\sqrt{30}$, so the overall mean is $\sqrt{30}$ times the mean of the 30 per-seed means, and the seeds being independent, it has the same standard deviation as one seed's mean: 0.064.

The same seed-to-seed spread gives a standard error for each row of the table. The largest deviation, in the 10 to 20 degree row (286 pairs from 12 queries), is 2.0 standard errors, and that of the 110 to 120 degree row (170 pairs from 112 queries) is 1.4. Among eleven rows, a largest deviation near two standard errors is what chance produces. The largest difference between observed and predicted agreement for any single pair is 0.027.

Amplifying the gap

A bit that agrees with probability 0.75 for a neighbor and 0.5 for an unrelated vector is a weak test. Two operations sharpen it, and they are the banding of the course article under other names.

Concatenation (AND). Draw $r$ hash functions independently and let the key of a vector be the $r$ values together. Two vectors have the same key only if they agree on all $r$. The draws are independent, so if each agrees with probability $p$, the keys agree with probability $p^r$. A $(d_1, d_2, p_1, p_2)$-sensitive family becomes a $(d_1, d_2, p_1^{\,r}, p_2^{\,r})$-sensitive one: near pairs collide with probability at least $p_1^{\,r}$, since each of the $r$ independent factors is at least $p_1$, and far pairs with probability at most $p_2^{\,r}$. Both probabilities fall, but the far one falls faster, and their ratio $(p_1/p_2)^r$ grows.

Repetition (OR). Build $b$ independent keys, each of $r$ bits, and call two vectors a match if they have the same key in at least one of the $b$. If one key agrees with probability $P$, none of $b$ independent keys agrees with probability $(1 - P)^b$, so the pair matches with probability $1 - (1 - P)^b$.

Together, a pair whose single bits agree with probability $p$ matches with probability

$$f(p) = 1 - (1 - p^r)^b ,$$

the function the course article derived for $b$ bands of $r$ rows, with the Jaccard coefficient replaced by $p$. Its analysis there carries over unchanged: $f$ rises steeply near $p = (1/b)^{1/r}$, and $f(p) \le b\,p^r$. For hyperplanes $p = 1 - \theta/\pi$, so in terms of the angle the steep part is near

$$\theta^* = \pi\left(1 - (1/b)^{1/r}\right) .$$

The literature on vector search writes $k$ for the number of concatenated functions and $L$ for the number of tables. This unit keeps $k$ for the number of neighbors and uses the course's $r$ and $b$.

$r$ bits per key $b$ keys Threshold $(1/b)^{1/r}$ Threshold angle $\theta^*$ (degrees)
8 8 0.771 41.2
8 32 0.648 63.3
12 64 0.707 52.7
16 16 0.841 28.6
16 32 0.805 35.1
20 64 0.812 33.8
Probability that a pair of vectors shares a key in at least one table, against the angle between them, for three choices of r bits per key and b tables. Lines are the formula; markers are the observed share among 200,000 pairs of GloVe vectors over 30 seeds. Notice how far to the left of 90 degrees each curve has already fallen: the neighbors of a typical query sit between 40 and 55 degrees, on the slope.
Probability that a pair of vectors shares a key in at least one table, against the angle between them, for three choices of r bits per key and b tables. Lines are the formula; markers are the observed share among 200,000 pairs of GloVe vectors over 30 seeds. Notice how far to the left of 90 degrees each curve has already fallen: the neighbors of a typical query sit between 40 and 55 degrees, on the slope.

The observed shares in the figure differ from the formula by at most 0.007 in any 5-degree bin, for the three settings shown.

Example (neighborhood with 32 tables of 16 bits). For $r = 16$ and $b = 32$ the threshold angle is 35.1 degrees, closer than any neighbor of neighborhood. Its nearest neighbor, at 33.8 degrees, has $p^{16} = 0.0359$ and matches with probability $1 - (1 - 0.0359)^{32} = 0.689$. Its tenth, apartment at 47.0 degrees, matches with probability 0.224. (These and the figures of Problems 1 and 2 are computed from the angles as printed, to one decimal.) Over 30 seeds, neighborhoods matched in 23 and apartment in 6, where $30 \times 0.689 = 20.7$ and $30 \times 0.224 = 6.7$ are expected. The recall@10 of this one query, averaged over the seeds, was 0.30, and the formula gives 0.35.

The index

The index applies the two operations to a whole collection (Indyk and Motwani, 1998; Har-Peled, Indyk, and Motwani, 2012, §3.2).

  • Build. Draw $b \times r$ hyperplanes. For each of the $b$ tables, compute every base vector's $r$-bit key and store the vector's number under that key. A table is a partition of the base vectors into at most $2^r$ buckets. The index holds $b$ numbers per base vector, $4bN$ bytes with 4-byte numbers, in addition to the vectors themselves. A directory of each table's buckets (the distinct keys and where each bucket starts) comes on top.
  • Query. Compute the query's key in each table, which takes $r b$ dot products. Collect the base vectors found in the query's $b$ buckets; these are the candidates. Compute the exact distance from the query to each candidate and return the $k$ nearest.

The cost of a query is the $rb$ hash evaluations plus one distance computation per candidate. Because the candidates are re-ranked by exact distance, a true neighbor is returned if and only if it is among the candidates: at most $k - 1$ base vectors are nearer to the query than one of its $k$ true nearest neighbors, so it cannot be pushed out of the best $k$ candidates. The recall@$k$ of a query is therefore the share of its $k$ true neighbors that are candidates.

Proposition (recall and cost from the angles). Let the base vectors make angles $\theta_1, \dots, \theta_N$ with the query, and let its $k$ nearest be those with angles $\theta_{(1)}, \dots, \theta_{(k)}$. Over the random choice of the hyperplanes,

$$E[\text{recall@}k] = \frac1k \sum_{i=1}^{k} f\bigl(p(\theta_{(i)})\bigr), \qquad E[\text{number of candidates}] = \sum_{i=1}^{N} f\bigl(p(\theta_i)\bigr) .$$

Proof. The base vector $\vec x_i$ is a candidate exactly when it matches the query in at least one table, which has probability $f(p(\theta_i))$ by the previous section. The number of candidates is the sum over $i$ of the indicator that $\vec x_i$ is a candidate, and $k$ times the recall is the same sum restricted to the true neighbors. The expectation of a sum of indicators is the sum of their probabilities. $\blacksquare$

The proposition needs no assumption about the data. It turns the angle distribution of a dataset into a prediction of the index's whole trade-off curve before any table is built. For the GloVe set the script computes the angles between the 1,000 queries and all 399,000 base vectors, 399 million pairs. Their median is 82.6 degrees. A share of 1.6% of them, about 6,261 base vectors per query, are within 60 degrees. The true neighbors of a typical query are at 43.2 degrees (the first) to 50.3 degrees (the tenth).

Measured against predicted

Each row is one setting, built 30 times with seeds 0 to 29 and queried with the 1,000 queries. Recall@10 and the number of candidates are means over the queries; the table gives the median over the seeds, with the interquartile range for the recall, beside the value the proposition predicts.

$r$ $b$ Recall@10 (IQR) Predicted Candidates Predicted Hash evaluations $rb$
8 1 0.091 (0.086 to 0.105) 0.100 3,261 4,031 8
8 4 0.328 (0.308 to 0.347) 0.327 15,838 15,688 32
8 16 0.743 (0.738 to 0.749) 0.744 56,202 56,739 128
8 64 0.985 (0.984 to 0.985) 0.985 165,828 165,089 512
12 1 0.036 (0.030 to 0.040) 0.036 419 509 12
12 4 0.126 (0.119 to 0.134) 0.128 1,969 2,021 48
12 16 0.372 (0.365 to 0.381) 0.373 7,763 7,880 192
12 64 0.757 (0.752 to 0.762) 0.757 28,422 28,845 768
16 1 0.015 (0.011 to 0.017) 0.014 52 74 16
16 4 0.052 (0.049 to 0.057) 0.052 281 295 64
16 16 0.167 (0.163 to 0.173) 0.166 1,179 1,167 256
16 64 0.420 (0.416 to 0.425) 0.420 4,447 4,515 1,024
20 1 0.006 (0.006 to 0.007) 0.006 10 12 20
20 4 0.023 (0.022 to 0.024) 0.023 45 49 80
20 16 0.077 (0.074 to 0.079) 0.076 193 195 320
20 64 0.207 (0.205 to 0.212) 0.208 742 763 1,280

The table shows every other value of $b$; the full grid has 28 settings ($r$ = 8, 12, 16, 20 and $b$ = 1 to 64 in powers of two). The proposition is about expectations, so the fair comparison is with the mean over the 30 seeds. That mean recall differs from the prediction by at most 0.002 in all 28 settings. The mean number of candidates is within 2.5% of the prediction in every setting with 8 or more tables, and within 8.1% in the others. With one or two tables the count swings widely from seed to seed, since it depends on how many base vectors happen to share the queries' buckets, and its median falls below its mean, as the first row of each group shows. The index does what the theory says. What the theory says for this data is not encouraging.

Recall@10 against the mean number of candidates per query, the cost on a logarithmic axis, for keys of 8, 12, 16 and 20 bits and 1 to 64 tables (medians of 30 seeds; the bars, mostly hidden by the markers, are interquartile ranges). The dashed line marks N = 399,000, the cost of a scan. Notice that longer keys reach a given recall with fewer candidates, but need many more tables to get there, and that every curve approaches high recall only as it approaches the scan.
Recall@10 against the mean number of candidates per query, the cost on a logarithmic axis, for keys of 8, 12, 16 and 20 bits and 1 to 64 tables (medians of 30 seeds; the bars, mostly hidden by the markers, are interquartile ranges). The dashed line marks N = 399,000, the cost of a scan. Notice that longer keys reach a given recall with fewer candidates, but need many more tables to get there, and that every curve approaches high recall only as it approaches the scan.
Target recall@10 Cheapest setting on the grid Recall@10 Candidates Candidates as a share of $N$
0.50 $r = 12$, $b = 32$ 0.564 15,154 3.8%
0.75 $r = 12$, $b = 64$ 0.757 28,422 7.1%
0.90 $r = 8$, $b = 32$ 0.913 101,111 25.3%
0.95 $r = 8$, $b = 64$ 0.985 165,828 41.6%

To find half of the true neighbors the index compares the query with 3.8% of the base vectors. To find 0.91 of them it compares the query with 25%. A recall of 0.985 takes 42%. The reason is in the angles. The neighbors sit at 40 to 55 degrees, where $p$ is about 0.69 to 0.78, and on average 24% of the base vectors are within 75 degrees of a query, where $p$ is still above 0.58. A key short enough to catch most of the first kind with a few dozen tables lets in a large part of the second kind.

Longer keys change the terms of the trade, not its nature. In the table, 16-bit keys reach a given recall with far fewer candidates than 8-bit keys, but need many more tables to reach it at all. Problem 2 works the case out: with 16-bit keys a recall near 0.87 is predicted at 26,000 candidates, a fifteenth of the base, in exchange for 435 tables, 0.7 GB of table entries beside 0.16 GB of vectors, and about 7,000 hash evaluations per query. The cost moves from distance computations to memory and hashing.

On the machine that ran the script, in the run whose results are stored with it, a scan of the 399,000 vectors took 12.5 milliseconds per query, and the index with $r = 16$, $b = 32$ took 0.50 milliseconds at a recall of 0.27, 25 times less, with tables of 78 MB: 51 MB of vector numbers and 27 MB of bucket directories and hyperplanes (26.3 MB and 0.2 MB). The one earlier run whose timings were kept, made with the machine fully loaded by other jobs, took 56.2 and 2.52 milliseconds, a factor of 22. So over the two stored runs a scan took between 12.5 and 56.2 milliseconds and the index between 0.50 and 2.52. The timings depend on the machine, its load and the implementation, a Python loop around NumPy; the candidate counts do not.

Where exact search wins

On the unit's small sets the hash evaluations alone settle the matter. For this site's 11,264 passage vectors (384 dimensions, 60 queries, 30 seeds):

$r$ $b$ Recall@10 Candidates Hash evaluations Total, as a share of $N$
8 4 0.228 320 32 3%
8 16 0.617 1,291 128 13%
8 64 0.965 4,113 512 41%
12 64 0.598 522 768 11%
16 64 0.225 62 1,024 10%

A setting that reaches a recall of 0.965 spends 4,625 dot products per query, against 11,264 for a scan that is exact. For Cranfield's 1,400 abstracts the picture is the same at a smaller size: with $r = 8$ and $b = 64$ a recall of 0.952 costs 1,240 dot products per query, where a scan makes 1,400. At these sizes a scan takes a few milliseconds at most, as the previous article measured, and an index has nothing to offer.

The query-time theorem

The table above reports what the index does on one dataset. The theorem of Indyk and Motwani says what it does on any dataset, for a problem slightly different from finding the nearest neighbors.

The problem. Fix a radius $R$ and a factor $c > 1$. In the $(c, R)$-near neighbor problem, a query $\vec q$ is given; if some base vector lies within distance $R$ of $\vec q$, the index must return a base vector within distance $cR$. If no base vector is within $R$, it may return anything or nothing. The index is randomized and is allowed to fail with a fixed probability (Har-Peled, Indyk, and Motwani, 2012, Definition 1.2). The nearest neighbor problem with approximation factor $c$ reduces to a sequence of such problems with different radii; the same paper gives the reduction, which is not reproduced here.

Theorem (Indyk and Motwani, 1998; in the form of Har-Peled, Indyk, and Motwani, 2012, Theorem 3.4). Suppose a $(R, cR, p_1, p_2)$-sensitive family exists, with $0 < p_2 < p_1 < 1$, and let

$$\rho = \frac{\ln(1/p_1)}{\ln(1/p_2)} .$$

Then there is an index for the $(c, R)$-near neighbor problem on $N$ items that answers a query with at most $3\lceil N^\rho/p_1 \rceil$ distance computations and $\lceil N^\rho/p_1 \rceil \cdot \lceil \log_{1/p_2} N \rceil$ evaluations of hash functions from the family, stores $\lceil N^\rho/p_1 \rceil$ numbers per item besides the items themselves, and fails with probability at most $1/3 + 1/e$.

The dependence on $p_1$ is the later paper's. Its authors remark that the 1998 version assumed both probabilities bounded away from 0, and that the 2012 statement makes the factor $1/p_1$ explicit (their Remark 3.5). They state the counts in $O$-notation; the constants above are the ones the proof below yields. In the preliminary version of the 1998 paper read here, the result is Theorem 5, with $O(n^\rho)$ hash evaluations per query, and the search stops after the first $2l$ points ($l$ being the number of tables) where the construction below stops after $3b$.

Since $p_1 > p_2$, the exponent $\rho$ is below 1: the number of distance computations grows more slowly than $N$. Here is the idea of the proof in two sentences. Choose $r$ just large enough that a far item shares a key with the query with probability at most $1/N$, so that each table brings in about one far item. Then a near item shares a key with probability about $N^{-\rho}$, and about $N^\rho$ tables are enough to catch it.

The construction. Let

$$r = \left\lceil \frac{\ln N}{\ln(1/p_2)} \right\rceil, \qquad b = \left\lceil \frac{N^\rho}{p_1} \right\rceil .$$

Build $b$ tables with keys of $r$ independent hash functions each, as in the previous section. To answer a query, go through its buckets in the order of the tables and compute the distance to each item met, counting an item again if it is met again. Stop as soon as an item within $cR$ is found, and return it. Stop also, and report failure, when $3b$ items have been examined or the buckets are exhausted.

Proof. Assume some item $x^*$ lies within $R$ of the query $q$; otherwise nothing is required. Call an item far if its distance from $q$ exceeds $cR$. Consider two events.

$E_1$: $x^*$ shares a key with $q$ in at least one table. In one table the keys agree with probability at least $p_1^{\,r}$. Since $r \le \ln N/\ln(1/p_2) + 1$ and $p_1 < 1$,

$$p_1^{\,r} \ge p_1 \cdot p_1^{\,\ln N/\ln(1/p_2)} = p_1 \exp\!\left(-\ln N \cdot \frac{\ln(1/p_1)}{\ln(1/p_2)}\right) = p_1 N^{-\rho} .$$

The tables are independent, so $x^*$ is missed by all of them with probability at most $(1 - p_1 N^{-\rho})^b \le \exp(-p_1 N^{-\rho}\, b) \le e^{-1}$, using $1 - x \le e^{-x}$ and $b \ge N^\rho/p_1$. So $P(E_1) \ge 1 - 1/e$.

$E_2$: fewer than $3b$ far items, counted with repetition, lie in the query's $b$ buckets. A far item shares the query's key in one table with probability at most $p_2^{\,r} \le p_2^{\,\ln N/\ln(1/p_2)} = 1/N$. There are at most $N$ far items, so the expected number in one bucket is at most 1, and in the $b$ buckets at most $b$. By Markov's inequality the number is $3b$ or more with probability at most $1/3$. So $P(E_2) \ge 2/3$.

If both events hold, the query succeeds. Suppose the procedure does not return an item within $cR$. Then every item it examined was far. It cannot have stopped at $3b$ items, because by $E_2$ fewer than $3b$ far items are in the buckets. So it exhausted the buckets, and by $E_1$ it met $x^*$, which is within $R \le cR$: a contradiction. Hence the procedure fails only if $E_1$ or $E_2$ fails, which has probability at most $1/e + 1/3$.

The cost. At most $3b$ distances are computed. The query's $b$ keys need $rb$ hash evaluations. Each item is stored once per table. $\blacksquare$

The failure probability $1/3 + 1/e \approx 0.70$ looks poor, but it is a bound, and it can be driven down: an independent copy of the index fails independently, so $j$ copies all fail with probability at most $(1/3 + 1/e)^j$, which is below $0.702^{\,j}$.

The construction run

For hyperplanes the distance is the angle and the family's probabilities are exact, $p_1 = 1 - \theta_1/\pi$ and $p_2 = 1 - \theta_2/\pi$. The script runs the construction on the 100,000 most frequent words of the base set, with $\theta_1 = 45$ and $\theta_2 = 80$ degrees:

$$p_1 = 0.75, \quad p_2 = 0.5556, \quad \rho = \frac{\ln(1/0.75)}{\ln(1/0.5556)} = 0.4894, \quad r = \left\lceil \frac{\ln 100{,}000}{\ln(1/0.5556)} \right\rceil = 20, \quad b = \left\lceil \frac{100{,}000^{0.4894}}{0.75} \right\rceil = 374 .$$

Of the 1,000 queries, 170 have a base vector within 45 degrees. For those, over 30 seeds:

Quantity Bound in the proof Measured (median over seeds)
Queries answered with a vector within 80 degrees at least $1 - 1/3 - 1/e = 0.299$ 1.000
$E_1$: a vector within 45 degrees shares a key at least $1 - 1/e = 0.632$ 0.941
$E_2$: fewer than $3b = 1{,}122$ far vectors in the buckets at least 0.667 1.000
Far vectors per bucket at most 0.78 expected 0.146
Distances computed up to the answer at most 1,122 1.7

Every bound holds with room to spare. Every one of the 170 queries was answered in every seed, after 1.7 distance computations on average, where a scan would make 100,000. The reason is less flattering than it looks. On this data a vector within 80 degrees is not rare. On average 8.5% of the 100,000 base vectors lie within 80 degrees of one of these queries, against about 49 vectors within 45 degrees. So the first or second vector met in a bucket usually qualifies, and only 19% of the answers returned (the median over the seeds) were themselves within 45 degrees. The other column of the bill is the hashing: $rb$ = 7,480 hyperplane dot products per query, each as expensive as a distance. The total is below 100,000 by a factor of 13, not by the factor the count of distances suggests.

What the theorem does and does not say

  • It is a guarantee for every dataset. No assumption is made about how the items are distributed. The price is that the bound is driven by the worst case, in which all $N$ items sit just beyond $cR$.
  • It answers a near neighbor question with a gap. An item within $cR$ is an acceptable answer when one within $R$ exists. It does not promise the nearest neighbor, or any of the $k$ nearest. On data where many items lie between $R$ and $cR$, as on GloVe, the answer is usually one of those.
  • The exponent is the whole story. With $\rho = 0.4894$ the gain over a scan grows like $N^{1 - \rho}$, slowly. For random hyperplanes $\rho = \ln(1 - \theta_1/\pi)/\ln(1 - \theta_2/\pi)$ depends only on the two angles. A larger gap between them gives a smaller $\rho$ and a weaker answer.
  • Hash evaluations are part of the cost. The theorem counts them separately, and at practical sizes they can exceed the distance computations, as they did above.

The tables of the previous section do not follow the theorem's recipe. They use far fewer tables and examine every candidate, which is how the index is used when the aim is recall and not a guarantee. The comparison of this index with the others of the unit, at equal recall, is in benchmarking vector indexes.

A family for Euclidean distance

Hyperplanes hash by angle and suit unit vectors. For vectors of arbitrary length under the Euclidean distance, Datar, Immorlica, Indyk, and Mirrokni (2004) gave a family that hashes a vector by where its projection onto a random line falls among segments of width $w$:

$$h_{\vec a, u}(\vec x) = \left\lfloor \frac{\vec a \cdot \vec x + u}{w} \right\rfloor ,$$

where the coordinates of $\vec a$ are independent standard normal variables and $u$ is uniform on $[0, w)$. The paper treats all distances $\ell_p$ with $0 < p \le 2$ through $p$-stable distributions, of which the normal distribution is the case $p = 2$. Only that case is derived here.

Proposition. Two vectors at Euclidean distance $c$ have the same hash with probability

$$P(c) = \int_0^w \frac{2}{c}\,\varphi\!\left(\frac{t}{c}\right)\left(1 - \frac{t}{w}\right) dt = 1 - 2\Phi\!\left(-\frac{w}{c}\right) - \frac{2c}{\sqrt{2\pi}\, w}\left(1 - e^{-w^2/(2c^2)}\right),$$

where $\varphi$ and $\Phi$ are the standard normal density and distribution function. $P$ is a decreasing function of $c$.

Here is the idea: the two projections differ by a normal variable whose standard deviation is the distance between the vectors, and two points on a line fall in the same segment of a randomly shifted grid with a probability that falls linearly with their separation.

Proof. The difference of the projections. $\vec a \cdot \vec x - \vec a \cdot \vec y = \vec a \cdot (\vec x - \vec y)$ is a sum of independent normal variables $a_j (x_j - y_j)$ with mean 0 and variances $(x_j - y_j)^2$. It is therefore normal with mean 0 and variance $\sum_j (x_j - y_j)^2 = c^2$. Its absolute value $T$ has density $\tfrac{2}{c}\varphi(t/c)$ for $t \ge 0$.

The grid. Given $T = t$, the two projections are two points on the line at distance $t$, and they receive the same hash exactly when no boundary of the grid lies between them. The boundaries are the points $jw - u$ for integers $j$. Because $u$ is uniform on $[0, w)$ and independent of $\vec a$, exactly one boundary falls in any interval of length $w$, at a uniformly distributed position. If $t \ge w$ a boundary certainly separates the points. If $t < w$, a boundary falls in the interval of length $t$ between them with probability $t/w$. So the hashes agree with probability $(1 - t/w)$ for $t < w$ and 0 otherwise.

The integral. Averaging over $T$ gives the first expression. To evaluate it, substitute $z = t/c$:

$$P(c) = \int_0^{w/c} 2\varphi(z)\, dz - \frac{2c}{w}\int_0^{w/c} z\,\varphi(z)\, dz .$$

The first integral is $2\bigl(\Phi(w/c) - \tfrac12\bigr) = 1 - 2\Phi(-w/c)$. For the second, $z\varphi(z)$ is the derivative of $-\varphi(z)$, so the integral is $\varphi(0) - \varphi(w/c) = \tfrac{1}{\sqrt{2\pi}}\bigl(1 - e^{-w^2/(2c^2)}\bigr)$. Together these give the closed form, which is the one Datar and colleagues state (2004, §4.1).

Monotonicity. Write $T = c\lvert Z \rvert$ for a standard normal $Z$. Then $P(c) = E\bigl[\max(0, 1 - c\lvert Z \rvert/w)\bigr]$, and the quantity inside the expectation decreases as $c$ grows for every value of $Z$. $\blacksquare$

Because $P$ is decreasing, the family is $(R, cR, P(R), P(cR))$-sensitive for every $R$ and $c > 1$, and the theorem applies with $\rho = \ln(1/P(R))/\ln(1/P(cR))$. Datar and colleagues computed this exponent numerically and report that, with the best width $w$ for each $c$, it lies below $1/c$ for the factors $c$ between 1 and 10 that they examined (2004, §4.1). For $R = 1$, $c = 2$ and $w = 4$, the script gives $P(1) = 0.8005$, $P(2) = 0.6095$ and $\rho = 0.4494$, below $1/c = 0.5$.

The script checks the closed form against numerical integration, and against a simulation of 200,000 hash functions per seed for three pairs with $w = 2$:

Pair Distance $c$ $P(c)$, closed form Simulated (median of 30 seeds)
neighborhood and neighborhoods 0.5820 0.7679 0.7684
neighborhood and apartment 0.7979 0.6832 0.6837
neighborhood and cheese 1.3393 0.5056 0.5053

What is proved, what is cited, what the experiments show

Proved on this page. That a similarity with a hash family whose collision probability equals it must have $1 - \mathrm{sim}$ obeying the triangle inequality; the effect of concatenation and repetition on a sensitive family; the expected recall and the expected number of candidates of the index from the angles; the query-time theorem, with its construction; the collision probability of the Euclidean family and its monotonicity.

Proved on a linked page. The hyperplane collision probability $1 - \theta/\pi$, the MinHash collision probability, and the shape and threshold of $1 - (1 - s^r)^b$, all in near-duplicate detection.

Cited. The reduction from approximate nearest neighbor search to near neighbor problems at several radii (Har-Peled, Indyk, and Motwani, 2012); the generalization of the Euclidean family to other $\ell_p$ distances and the numerical finding $\rho < 1/c$ (Datar, Immorlica, Indyk, and Mirrokni, 2004).

Observed in the experiments. The agreement of bit counts, matching shares, recall and candidate counts with the formulas, on the GloVe set with 30 seeds; the cost of each recall level on that set and on the two small sets; the behavior of the theorem's construction on 100,000 vectors; the timings, on one machine. That random-hyperplane hashing is an expensive index for this data is an observation about this data, whose neighbors are 40 to 55 degrees from their queries. On near-duplicate data, where neighbors are a few degrees apart, the same formulas give a sharp separation.

Worked problems

The unit has no course assignments, so the problems are posed on the running query, on the unit's data and on small exact cases. The script recomputes every number.

Problem 1 (one pair through the index). Suburb makes an angle of 42.9 degrees with neighborhood. With $b = 32$ tables of $r = 16$ bits, what is the probability that suburb is a candidate for the query neighborhood? In how many of 30 independent indexes should it be one?

Solution. One bit agrees with probability $p = 1 - 42.9/180 = 0.7617$. A 16-bit key agrees with probability $p^{16} = 0.01283$. No key among 32 agrees with probability $(1 - 0.01283)^{32} = 0.6615$, so suburb is a candidate with probability $0.3385$. Among 30 indexes the expected number is $30 \times 0.3385 = 10.2$. In the script's 30 seeds it was a candidate in 6. A binomial count with 30 trials and that probability has a standard deviation of 2.6, so 6 is 1.6 standard deviations below the expected number.

Problem 2 (tables needed for a target). With keys of $r = 16$ bits, how many tables are needed for a vector at 50.3 degrees, the median angle of a tenth neighbor to one decimal, to be a candidate with probability at least 0.9? What does the proposition predict for the recall@10 and the number of candidates of that index on the GloVe set?

Solution. $p = 1 - 50.3/180 = 0.7206$ and $p^{16} = 0.00528$ (0.0052806 before rounding). We need $(1 - p^{16})^b \le 0.1$, that is $b \ge \ln 0.1/\ln(1 - 0.0052806) = 434.9$, so $b = 435$ tables. The index would hold $4 \times 435 \times 399{,}000$ bytes, about 0.69 GB of table entries, and a query would evaluate $16 \times 435 = 6{,}960$ hyperplanes. From the angles of the 399 million pairs, the proposition predicts a recall@10 of 0.87 and 25,944 candidates per query, 7% of the base vectors. The neighbors closer than the median are found with probability above 0.9 and the farther ones below it, and the mean comes out at 0.87. This setting was not built; the figures are predictions of the kind the grid confirmed.

Problem 3 (the theorem's parameters at full size). For the whole base set, $N = 399{,}000$, and angles $\theta_1 = 45$ and $\theta_2 = 75$ degrees, compute $\rho$, $r$ and $b$, and the cost of a query in the theorem's construction.

Solution. $p_1 = 1 - 45/180 = 0.75$ and $p_2 = 1 - 75/180 = 0.5833$. Then $\ln(1/p_1) = 0.2877$ and $\ln(1/p_2) = 0.5390$, so $\rho = 0.5337$. With $\ln 399{,}000 = 12.897$, $r = \lceil 12.897/0.5390 \rceil = \lceil 23.93 \rceil = 24$. And $N^\rho = e^{0.5337 \times 12.897} = 976$, so $b = \lceil 976/0.75 \rceil = 1{,}302$. A query computes at most $3b = 3{,}906$ distances and $rb = 31{,}248$ hash bits, 35,154 dot products in all, against 399,000 for a scan: a factor of 11.4. The tables hold $1{,}302 \times 399{,}000$ numbers, 2.1 GB at 4 bytes each, against 0.16 GB for the vectors. The guarantee bought at that price is a vector within 75 degrees when one within 45 exists, with probability at least 0.299 per query.

Problem 4 (the Euclidean family). The unit vectors of neighborhood and neighborhoods are at Euclidean distance 0.5820. With width $w = 2$, what is the probability that they receive the same hash?

Solution. $w/c = 2/0.5820 = 3.4364$. $\Phi(-3.4364) = 0.000295$, so the first two terms give $1 - 2 \times 0.000295 = 0.99941$. The last term is $\dfrac{2 \times 0.5820}{\sqrt{2\pi} \times 2}\bigl(1 - e^{-3.4364^2/2}\bigr) = 0.23218 \times 0.99727 = 0.23155$. So $P = 0.99941 - 0.23155 = 0.76786$, which is 0.7679 to four decimals, and the simulation gave 0.7684.

Problem 5 (no hash family for the cosine). Show that no family of hash functions has $P(h(\vec x) = h(\vec y)) = \cos\theta$ for all unit vectors with nonnegative cosine, while the angle itself passes the same test.

Solution. By the proposition of Charikar, such a family would make $1 - \cos\theta$ obey the triangle inequality. Take three unit vectors in the plane at 0, 45 and 90 degrees. The first and third are at 90 degrees, so $1 - \cos 90^\circ = 1$. Each is at 45 degrees from the second, and $1 - \cos 45^\circ = 0.2929$. The triangle inequality would require $1 \le 0.2929 + 0.2929 = 0.5858$, which is false. For the hyperplane family, $1 - p(\theta) = \theta/\pi$, and the same three vectors give $0.5 \le 0.25 + 0.25$, which holds with equality, as it must for three vectors in a plane with the middle one between the others.

What we have learned

A locality-sensitive family is defined by two distances and two collision probabilities. Concatenating $r$ functions and repeating in $b$ tables turns a weak single bit into the S-curve $1 - (1 - p^r)^b$, and for random hyperplanes $p = 1 - \theta/\pi$. The resulting index is fully predictable: its expected recall and its expected number of candidates are sums of that curve over the angles of the data, and the measurements on 399,000 word vectors agree with the sums. The theorem of Indyk and Motwani shows that for any data an approximate near neighbor query needs about $N^\rho$ distance computations, with $\rho = \ln(1/p_1)/\ln(1/p_2) < 1$, and the proof is two applications of elementary inequalities. On this data the exponent is near 0.49 and the practical cost is high: with 32 tables a recall@10 of 0.91 took 25% of a scan's distance computations, and a smaller share is predicted to take hundreds of tables, because the neighbors are too far from their queries, in angle, for random planes to tell them from the crowd.

The hash functions here are drawn without looking at the data. The indexes that follow all look. The next one partitions the vectors where they actually cluster, with k-means, and probes the cells nearest the query: inverted file indexes for vectors.

References

  • Charikar, M. S. (2002). Similarity estimation techniques from rounding algorithms. In Proceedings of STOC 2002, 380–388. record · 3 pages
  • Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. S. (2004). Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the 20th Annual Symposium on Computational Geometry (SCG '04), 253–262. 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