DataTerminology.comNEW
Also known as: LSH
A hashing technique that increases collision probability for similar items, enabling fast approximate nearest neighbor search in high-dimensional spaces.
DESCRIPTION
Locality-Sensitive Hashing (LSH) accelerates similarity search by mapping similar vectors or sets to the same buckets with high probability. It is widely used for near-duplicate detection, document similarity, and large-scale vector retrieval. LSH families exist for various metrics, such as Jaccard (MinHash), cosine similarity, and Euclidean distance (p-stable distributions). Multiple hash tables and concatenated hash functions tune precision–recall trade-offs. LSH scales well to high dimensions compared to exact structures like k-d trees. It underpins many industrial systems for recommendations and deduplication. Despite being probabilistic, careful parameterization yields robust performance.
ALTERNATIVE DEFINITIONS
Wikipedia
Locality-sensitive hashing (LSH) is an algorithmic technique that hashes similar input items into the same “buckets” with high probability.
Highlights probabilistic collisions for similar items and bucket-based hashing.
arXiv
Locality Sensitive Hashing (LSH) is a popular method to solve the approximate near neighbor problem in high dimensional spaces.
Emphasizes application to approximate nearest neighbor in high dimensions.
RELATED TERMS
Approximate Nearest Neighbor MinHash Cosine Similarity Jaccard Index Hash Function KD-Tree Annoy Vector Index
COMPETING TERMS
RELATIONS
- Broader: Hashing
KNOWLEDGE AREAS
AI Data Science Mathematics Data Engineering Data Storage & Operations
TARGET AUDIENCE
AI Engineer Data Scientist Data Engineer MLOps Engineer
EXTERNAL SOURCES
- Wikipedia - Locality-sensitive hashing
- Mining of Massive Datasets - Textbook chapter covering LSH foundations
- arXiv - Survey on LSH and ANN
- Datasketch - Python MinHash and LSH implementation
TOP QUESTIONS
Why is Locality-Sensitive Hashing useful for high-dimensional data?
LSH avoids the curse of dimensionality by probabilistically grouping similar items, enabling sublinear search with multiple hash tables rather than exhaustive comparison.
Category: Relevancy
What metrics does Locality-Sensitive Hashing support?
LSH families exist for Jaccard similarity (MinHash), cosine similarity (random hyperplanes), and Euclidean distance (p-stable distributions), each tailored to the specific metric.
Category: Overview
How do you tune Locality-Sensitive Hashing performance?
Adjust the number of hash functions per table and the number of tables to balance precision, recall, and query speed; more tables increase recall at the cost of memory.
Category: Requirements
What is a common mistake when applying Locality-Sensitive Hashing?
Using inappropriate LSH families for the target distance metric or too few tables leads to poor recall and unstable results; wrong parameterization undermines effectiveness.
Category: Mistakes
How does Locality-Sensitive Hashing compare to HNSW?
LSH uses hashing-based probability collisions, while HNSW builds navigable graph indexes. HNSW often yields higher recall but requires more memory and index construction time.
Category: Alternatives
Where is Locality-Sensitive Hashing applied in practice?
LSH powers near-duplicate detection, large-scale document and image similarity, and recommendation systems, especially when latency and scale preclude exact nearest neighbor search.
Category: Example
What is the biggest misunderstanding about Locality-Sensitive Hashing?
People assume LSH is exact; it is inherently approximate and probabilistic. Proper tuning is essential to achieve desired accuracy for a given task.
Category: Misunderstanding
How does MinHash relate to Locality-Sensitive Hashing?
MinHash is an LSH family designed for Jaccard similarity between sets, estimating similarity via hashed permutations and enabling efficient candidate retrieval.
Category: Overview
What risks accompany Locality-Sensitive Hashing in production?
Poor parameter choices can yield low recall, and skewed data distributions may cause uneven bucket loads. Monitoring and retraining mitigate performance drift.
Category: Risks