Overview
Locality-Sensitive Hashing supports approximate nearest-neighbor search by using hash families aligned with a similarity metric.
CoreSource checked
Locality-Sensitive Hashing
Hashes similar items into the same buckets with higher probability than dissimilar items.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Advanced
- Family
- Approximate Similarity Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
similarity-preserving hashbucket candidateapproximate neighborcollision probability
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(k)
Average
O(k n)
Worst
O(k n)
Space
O(k n)
When to Use
- Use when text search needs similarity-preserving hash.
- Use when the input matches the assumptions behind approximate Similarity Search.
When Not to Use
- Avoid when a simpler exact search is enough and approximate scoring is unnecessary.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Hashes similar items into the same buckets with higher probability than dissimilar items
- Uses similarity-preserving hash and bucket candidate to guide the work.
- Produces matches.
Use Cases
- Text search
- Sequence comparison
- Similarity detection
Inputs
- Pattern or query sequence
- Text or target sequence
Outputs
- Matches
- Score
- Alignment or index
Key Formulas (1)
LSH property
P[h(a) = h(b)] increases with similarity(a, b)
P[h(a) = h(b)] increases with similarity(a, b)Defines the hash behavior used to create candidate matches.
Pseudocode
- 1.Prepare the inputs and state needed for Locality-Sensitive Hashing.
- 2.Apply the similarity-preserving hash step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return matches.
Canonical Example
- Input
- Locality-Sensitive Hashing with a minimal inspectable input
- Output
- Matches
- Explanation
- Locality-Sensitive Hashing applies similarity-preserving hash to produce matches.
Implementation Notes
- Normalize input consistently before building indexes or comparing sequences.
- Keep the similarity-preserving hash step separate enough to test independently.
Common Pitfalls
- Changing tokenization or distance definitions changes the match result.
- Forgetting to check edge cases can make Locality-Sensitive Hashing look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow matched positions, dynamic-programming cells, or candidate buckets.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Prepare the inputs and state needed for Locality-Sensitive Hashing.
pattern-matching-mechanismNotes
Locality-Sensitive Hashing should be used with the assumptions and tradeoffs of approximate Similarity Search in mind.
Sources (2)
What each reference supports for this entry.
Indyk-Motwani LSH
PaperOriginal locality-sensitive hashing reference for sublinear approximate nearest-neighbor search.
Open sourceMining of Massive Datasets
BookLarge-scale data-mining reference covering Locality-Sensitive Hashing similarity estimation, sketching, or vector comparison use case.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsesMinHash
LSH can use MinHash signatures for approximate set similarity search.
Alternative toSuffix Array Search
LSH supports approximate search, while suffix arrays support exact substring search.
Related Algorithms
Tags
Pattern MatchingHashingNearest NeighborSimilarity