Locality Sensitive Hashing

Locality Sensitive Hashing (LSH) is a family of algorithms that speed up similarity search by hashing similar data points into the same buckets, trading perfect accuracy for much faster lookups in high-dimensional spaces.

What It Is

When you search for something similar — a product image, a sentence meaning, or a customer profile — the system needs to compare your query against potentially millions of stored items. Checking every single one (brute force) works fine for small datasets, but becomes painfully slow as data grows. Locality Sensitive Hashing exists to solve this exact bottleneck in vector similarity search: finding similar items without checking everything.

Think of it like sorting books into themed shelves at a library. Instead of reading every book to find ones about cooking, you walk to the cooking section. LSH works the same way — it assigns each data point a short hash code designed so that items which are “nearby” in meaning or value land in the same bucket. When a query arrives, the system only checks items in the matching bucket, skipping vast portions of the dataset entirely.

In practice, LSH typically uses multiple hash tables rather than just one. Each table applies a different set of hash functions, creating multiple chances for similar items to land together. If two items share a bucket in any table, they become candidates for exact distance comparison. More tables mean higher recall (fewer missed neighbors) but also more memory and preprocessing time. This multi-table approach is what gives LSH its tunable accuracy-speed trade-off.

According to Indyk & Motwani, who introduced LSH at STOC 1998, the technique achieves sublinear query time — meaning search speed grows much slower than your dataset size — after a one-time preprocessing step that scales roughly with the data. The core guarantee is probabilistic: similar items have a high probability of receiving the same hash, while dissimilar items are unlikely to collide. This is the opposite of traditional hash functions (like those used in databases), where any small change in input produces a completely different hash.

Several variants of LSH exist for different distance metrics. According to Wikipedia, common families include random hyperplane LSH for cosine similarity, p-stable LSH for Euclidean distance, and MinHash for Jaccard similarity. The choice depends on which distance metric your vector similarity search pipeline uses — a decision that directly shapes retrieval quality.

How It’s Used in Practice

In the context of vector similarity search, LSH serves as one of the index structures that sits between raw embedding vectors and your application. When a vector database receives a query embedding, it needs a fast way to narrow down candidates before computing exact distances. LSH provides that first-pass filter — hashing the query vector and retrieving only the items that share its bucket.

According to FAISS Docs, LSH is available as IndexLSH in the FAISS library. Teams building search or recommendation systems sometimes start with LSH because it’s straightforward to implement and reason about. However, most production vector databases have shifted toward graph-based methods like HNSW, which tend to offer better recall-speed trade-offs for real-world workloads.

Pro Tip: If you’re evaluating index structures for a new vector search project, benchmark LSH against HNSW on your actual data before committing. LSH shines when memory is tight (hash codes are compact), but HNSW usually wins on recall at the same query speed.

When to Use / When Not

Common Misconception

Myth: LSH guarantees finding the exact nearest neighbor, just faster. Reality: LSH is an approximate method. It trades perfect recall for speed — some true nearest neighbors may end up in different buckets and get missed. The “approximate” in approximate nearest neighbor search is the whole point: you accept a small accuracy loss to avoid scanning every item in your dataset.

One Sentence to Remember

LSH is a shortcut for similarity search that groups similar items into the same bucket using special hash functions — a rough index that gets you close enough, fast enough, without checking everything in your vector store.

FAQ

Q: How does LSH differ from regular hashing? A: Regular hashing minimizes collisions — similar inputs get different hashes. LSH deliberately maximizes collisions for similar inputs so they land in the same bucket for fast similarity lookup.

Q: Is LSH still used in production vector databases? A: LSH remains available in libraries like FAISS, but most production systems have shifted to graph-based methods like HNSW, which typically achieve better recall at comparable query speeds.

Q: What types of similarity does LSH support? A: Different LSH variants handle different distance metrics: random hyperplane LSH for cosine similarity, p-stable LSH for Euclidean distance, and MinHash for Jaccard similarity between sets.

Sources

• Indyk & Motwani: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality - Foundational paper introducing LSH for sublinear approximate nearest neighbor search
• FAISS Docs: Welcome to Faiss Documentation - Reference documentation for Facebook AI Similarity Search library including IndexLSH