Locality-Sensitive Hashing (LSH)
You'll learn how LSH creates "similarity-preserving" hash functions that group similar vectors together with probabilistic guarantees.
What LSH Solves
Remember from previous lessons that brute-force similarity search becomes impractical as dimensionality and dataset size grow. LSH takes a radically different approach: instead of organizing vectors in tree structures, it uses special hash functions that intentionally cause hash collisions for similar items.
The Core Idea
Traditional hash functions (like those in dictionaries) try to spread items uniformly—similar inputs get completely different hash values. LSH does the opposite: it uses hash functions where similar vectors are more likely to produce the same hash value.
Think of it like organizing books: instead of perfect alphabetical order, you create rough categories like "action," "romance," "sci-fi." Similar books land in the same bucket. You lose perfect precision, but gain massive speed.
How It Works (Conceptually)
- Create multiple hash tables using different LSH functions
- Hash all vectors into buckets in each table
- At query time, hash the query vector and only compare against items in matching buckets
- Aggregate results across tables to improve recall
The "locality-sensitive" part means vectors close in the original space have a high probability of landing in the same hash bucket, while distant vectors likely don't.
Probabilistic Guarantees
LSH provides probabilistic guarantees: if two vectors are within distance d, there's a probability p₁ they'll hash to the same bucket. If they're beyond distance cd (where c > 1), the probability drops to p₂. By adjusting parameters (number of tables, hash functions), you trade off speed versus accuracy.
Key Takeaway: LSH uses cleverly designed hash functions that preserve similarity relationships, allowing fast approximate neighbor search with tunable probabilistic accuracy guarantees.