Random-Hyperplane LSH (Cosine)

Background

Random-hyperplane LSH (SimHash) turns each vector into a compact binary signature by taking dot products against random Gaussian hyperplane normals and thresholding at zero. The Hamming distance between signatures approximates the angular distance between the original vectors — sub-linear nearest-neighbour search with no learned parameters.

Problem statement

Implement lsh_signature(vec, hyperplanes). Compute the dot product of vec with each row of hyperplanes; return a boolean array where each entry is True iff the dot product is $\ge 0$.

$$\text{sig}_i \;=\; \mathbb{1}[\,h_i \cdot v \ge 0\,]$$

Input

• vec — 1-D np.ndarray of length $d$.
• hyperplanes — 2-D np.ndarray shape $(n_{\text{bits}}, d)$, rows sampled i.i.d. from $\mathcal N(0, I)$.

Output

Returns np.ndarray of bool, shape $(n_{\text{bits}},)$.

Examples

Example 1 — shape

Input:  vec shape=(2,), hyperplanes shape=(8, 2)
Output: shape=(8,), dtype=bool

Example 2 — opposite vectors have flipped signatures

Input:  sig_a = lsh_signature(v, H); sig_b = lsh_signature(-v, H)
Output: sig_a == ~sig_b

Example 3 — near vectors share most bits

Input:  v1 = [1, 0], v2 = [0.99, 0.01] over 64 hyperplanes
Output: Hamming distance is small (< 20% of bits)

Constraints

• vec.shape[0] == hyperplanes.shape[1] (dim match).
• Output dtype is bool.
• Threshold is $\ge 0$ (not $> 0$) — matters only on exact zeros.

Notes

• Why it works. For random hyperplanes, $\Pr[\text{sig}(u) \ne \text{sig}(v)]$ equals the angle between $u$ and $v$ divided by $\pi$ — so Hamming distance is a sample estimate of angular distance.
• Indexing. With $n_{\text{bits}}$ bits per vector, you can shard the database into $2^b$ buckets ($b = 8$ or so) for sub-linear lookup.