Locality-Sensitive Hashing

5.1 Intuition

5.2 Random Hyperplane LSH for Cosine Similarity

python
Run Inline
import numpy as np
class RandomHyperplaneLSH:
    def __init__(self, n_hyperplanes=10):
        self.n_hyperplanes = n_hyperplanes
        self.planes = None
    def fit(self, X):
        d = X.shape[1]
        self.planes = np.random.randn(self.n_hyperplanes, d)
    def hash_vector(self, x):
        return tuple((x @ self.planes.T > 0).astype(int))
    def query(self, x, database):
        h = self.hash_vector(x)
        candidates = [i for i, db_h in enumerate(self.hashes)
                      if db_h == h]
        return candidates

5.3 LSH Families

• $\Pr[h(x) = h(y)] \geq p_1$ when $||x-y|| \leq r_1$
• $\Pr[h(x) = h(y)] \leq p_2$ when $||x-y|| \geq r_2$ Common families: random hyperplanes (cosine), minhash (Jaccard), p-stable distributions (Euclidean). Join Discord PreviousJL ProofNextMinHash, SimHash, Bloom