Locality-sensitive hashing

Locality-sensitive hashing (LSH) hashes similar items into the same buckets

Locality-sensitive hashing (LSH) is a technique that hashes similar input items into the same "buckets" with high probability. This characteristic makes LSH particularly useful for tasks like data clustering and nearest neighbor search, where grouping similar items together can significantly improve efficiency and accuracy.

Example

In a dataset of images, LSH can group similar images (e.g., pictures of cats) into the same bucket, allowing for faster retrieval of similar images when a query is made.

Remember this

LSH's ability to hash similar items together into the same buckets is crucial for efficient and accurate approximate nearest neighbor search, which is widely used in various applications such as recommendation systems and image retrieval.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

consistent hashing solves: minimizes key redistribution when servers are added/removed

Consistent hashing minimizes key redistribution when servers are added/removed

consistent hashing does: minimizes remapping when nodes join/leave

How can we efficiently share resources without constant reorganization?

UMAP is faster than t-SNE

UMAP is faster due to approximate nearest neighbors and cross-entropy optimization

the curse of dimensionality makes nearest neighbor search unreliable

Why can't we find our friends easily as we move to a city with more and more neighborhoods?

cosine similarity is preferred over dot product for normalized embeddings

Why do we need a special way to measure similarity in high-dimensional spaces?

t-SNE preserves local structure

Can we see the hidden patterns in a cloud of data points?

Swipe through 100 ML concepts daily

Open Pocket Polymath