Hash functions that like their neighbours

1The definition

A family of hash functions is locality-sensitive if, for a randomly drawn member $h$ :

\text{close points: } \Pr[h(x) = h(y)] \ge \kdec{p_1} \qquad\qquad \text{far points: } \Pr[h(x) = h(y)] \le \kres{p_2} \qquad\qquad \kdec{p_1} > \kres{p_2}

“Close” and “far” are two thresholds on the distance you care about. Everything LSH can do follows from how far apart $p_1$ and $p_2$ are.

2SimHash: one hyperplane, one bit

For cosine similarity the classic family is Charikar’s SimHash (2002). Draw a random direction $r$ and record which side of its hyperplane the vector falls on:

h_r(\kvec{x}) \;=\; \operatorname{sign}(r \cdot \kvec{x})

When do two vectors get different bits? Exactly when the hyperplane passes between them.

Fig 5.1.1Random hyperplanes in the plane

Drag the two arrows Red lines are hyperplanes that separate the query from the document. In the plane a random line through the origin has a random angle, and it separates the arrows exactly when it falls inside the yellow angle between them.

That picture is the proof. The two vectors span a plane; only the hyperplane’s trace in that plane matters; that trace is a line at a uniformly random angle; and it separates the vectors when it lands inside an angle of size $\theta$ out of $\pi$ :

\Pr\big[h_r(x) \ne h_r(y)\big] \;=\; \frac{\kvec{\theta}}{\pi} \qquad\Longrightarrow\qquad \Pr[\text{same bit}] \;=\; 1 - \frac{\theta}{\pi}

It holds in any number of dimensions, because only that one plane matters.

SimHashnumpy

R = np.random.randn(n_bits, d)        # one random hyperplane per bit
bits = (X @ R.T) > 0                  # (N, n_bits) booleans
# two rows differ in about  n_bits * angle / pi  positions

3Does it hold on real embeddings?

Fig 5.1.2Collision probability, measured

Measured Dots: the fraction of 2,048 random hyperplanes on which real query–passage pairs agree, grouped by their true angle. Line: $1-\theta/\pi$ . The two dashed markers are the angles that matter for search on this data.

The formula is exact. The bad news is where the markers sit.

A single hash bit is a very weak witness.

On this data even a 10th-nearest neighbour is 70° away, and a random passage 86°. The whole craft of LSH is amplifying a small gap between two probabilities.

4Two ways to use the bits

The same random bits serve two quite different purposes, and the rest of this part takes them in turn.

As an address Concatenate a few bits into a bucket key and look only in the query’s bucket. This is LSH as an index. → 5.2 Turning a gentle slope into a cliff, 5.3 Random cuts against learned cuts
As a sketch Keep hundreds of bits per vector and compare bit strings with Hamming distance. This is LSH as a compressor, and it is how “binary quantization” in vector databases works. → 5.4 Bits as a compressed sketch