Introduction to Locality-Sensitive Hashing

What are the gold standard algorithms now?

There are many great algorithms that outperform LSH on ANN vector search, but vectorization in itself a high-compute task, which ads latency and require GPUs, but this is not reported in benchmarks. For text LSH hash can be efficiently created directly from tokens. Of course, this does not work for semantic similarity, but can be used for lexical similarity search.

By the way. I enjoyed listening the interview with you on Practical AI podcast!

This thread contains many excellent points, and it's true that LSH is no longer SOTA for ANN problems. Generally, LSH indices are much faster to construct but slower to query than other ANN methods (graph-based, cluster-based, etc). In many applications, construction time matters less than query time, so LSH is unattractive there.

However, I'd like to add that LSH has recently been applied to other types of problems with very good results.

For example, LSH-based methods are at the core of the best sampling methods for kernel density estimation (KDE) and other problems [1,2]. This has recently led to fast approximations for the top eigenvalues of kernel matrices [3], SGD sampling [4], and probably more. LSH can also be used to construct sketches for kernel sums [5], which have applications to bioinformatics and can lead to fast neural network inference [6]. So, LSH is alive and well - just not necessarily for ANN.

(Full disclaimer: I am an author of [5] and [6])

[1]: https://arxiv.org/abs/1808.10530 [2]: http://proceedings.mlr.press/v97/siminelakis19a [3]: https://arxiv.org/abs/2102.08341 [4]: https://arxiv.org/abs/1910.14162 [5]: https://arxiv.org/abs/1912.02283 [6]: https://arxiv.org/abs/2106.11426

http://infolab.stanford.edu/~ullman/mmds is 401 for me - presumably because directory indexing is turned off.

http://infolab.stanford.edu/~ullman/mmds/book.pdf is the book; http://infolab.stanford.edu/~ullman/mmds/bookL.pdf is the hyperlinked book; and http://www.mmds.org/ seems to be the official homepage.

Yes, given the dimensionality of the input is at least the dimensionality of the hash value, location-sensitive hashing is always a dimensionality reduction operation.

Conversely, any dimensionality-reducing technique with a fixed number of finite range output dimensions can be used for location-sensitive hashing as long as a couple of extra constraints hold: (1) nearby inputs (given an appropriate distance metric) will produce nearby outputs (given a second appropriate distance metric), and (2) far-apart inputs are likely to produce far-apart outputs.

UMAP is sort of along those lines: https://umap-learn.readthedocs.io/en/latest/how_umap_works.h...

Replying in kind: if it optimizes memory layout then it speeds up computation. However if you reduce the hardness from 5 bn years to 1bn years it's important but amusing.

They discuss distance metrics, which may be sensitive to inducive bias, which may perhaps be substantiated by external knowledge about the specific instance of the problem. Then things are not amusing anymore.

A few observations: we don't yet know how to perform long-term qbit storage, so all multi-day storage at present is classic bits.

If the proposal is to hash all of the possible lattice points using irreversable computation on Earth in a reasonable amount of time, for a cryptographically useful lattice, the waste heat would literally boil the oceans. That's limitation doesn't hold for quantum computers, but results need to be converted into classic bits for storage. Presumably rainbow-table-like operations could reduce the storage space and waste heat necessary in storing these bits. Maybe quantum rainbow tables are a fruitful area of research.

If we're not pre-hashing all possible lattice points, then either we has the public value and we have some heuristic that allows us to hash only some small subset of lattice points for this particular value (... but then why use a hash? ... just compare points in your heuristic sequence) or we have some inverse hash operation where we hash the public value, then explore the "un-hash space" of lattice points corresponding to the LSH for the point in question.

This last general line of inquiry (trying to find search-space reducing heuristics) is probably where most of the research effort is going, though perhaps not specifically using LSH. In order to be useful for the lattice problem, the distance metrics for the input and output spaces of the LSH need to have specific relations to the lattice distance metric.

So... yea... maybe it helps to re-cast the problem in terms of LSH, but not in any obvious way. Also, any search-space reducing heuristic could probably be re-interpreted as a LSH if you squint at it hard enough.

I also wish to know! Specially because https://en.wikipedia.org/wiki/Locality-sensitive_hashing says "See also: Rolling hash" (and a bunch of other things like bloom filters and wavelet compression)

The best I can find is https://medium.com/@glaslos/locality-sensitive-fuzzy-hashing... in which SSDEEP apparently uses a rolling hash to implement locality sensitive fuzzy hashing

ssdeep would be a fuzzy hashing program https://ssdeep-project.github.io/ssdeep/index.html

It's widely used in recommenders based on embeddings. See:

https://github.com/spotify/annoy

https://github.com/facebookresearch/faiss

It's used in the cybersecurity world for fuzzy file comparison. See https://github.com/trendmicro/tlsh

Academic example but I'm sure it's made it's way to this industry as well: in bioinformatics, this has proven tremendously useful for approximate string matching to do things like identify microbes in sequenced microbiome samples - cf https://genomebiology.biomedcentral.com/articles/10.1186/s13...

It was used in https://ai.googleblog.com/2020/01/reformer-efficient-transfo... for faster and more memory-efficient attention.

The recommender system mention is very valuable use case that I've seen at some of the largest ml using companies in the world. If you have a recommendation system on millions or much higher pool of content you will need an ANN index. I would expect google image search is using an ANN index. Facebook definitely uses ANN indices. Spotify is where Annoy comes from. They're pretty key at tiktok.

Whether you use locality sensitive hashing or something else is a separate question. Personal experience is graph based ANN indices (hnsw is one nice one) have tended to a bit better, but LSH is competitive so I wouldn't strongly be against a design decision choosing it. One downside I've seen with some ann index libraries is a lot of them don't support incremental updates/deletions and force you to build the index as a batch job. That's fine in some use cases, but breaks others. LSH based approach spotify uses doesn't support incremental updates, but that's not because LSH can't support it just Annoy wasn't designed for it.

A lifetime ago I used it on a document clustering system. It is not very good as a general similarity function, but excellent for quickly finding near duplicates in linear time. About half of the documents of set I was working on (news articles) were duplicates, so an early removal pass would speed up the actual clustering algorithm pass.

My recollection is a bit fuzzy, but I remember specifically using Min-Hash together with random projection.

Locality sensitive hashing is extensively used in bioinformatics and genomics.

mash is probably the best-known implementation (https://doi.org/10.1186/s13059-016-0997-x). It allows you to do highly efficient pairwise comparisons of genome sequences, where it provides a good approximates their actual pairwise sequence divergence.

Is MinHash used industrially outside of genomics? In theory, it'd be useful on any kind of text corpus. The design of the hash functions that the sketch is built from is non-trivial The hashes typically come from k-mers of a fixed length and various fast hash functions over them.

I used it in ecommerce to find duplicate product titles.

It was used extensively in classic computer vision descriptor matching including most image lookup e.g. google image search today. There are many reasons it not much used in recent computer vision. The first is that it does not work when the descriptors themselves are explicitly designed to make visually similar features descriptively distinct, and the second is that it generally works poorly for binary vectors which dominate. With regards to ml, its been tried, but the datasets are either too small or not available to researchers, and the result would be far too slow compared to the current approaches. Its actually one of the areas where deep learning hasn't reached parity to my current knowledge. It would be a great project, the dataset issue aside.

When I was in ByteDance, it was used extensively to deduplicate news articles.

It is being used in the reformer architecture to relate the dot product attention layer. This enables much longer input sequences and reduces computational complexity from O(n^2) to O(nlog(n)), where n in the length of the sequence.

https://huggingface.co/transformers/model_doc/reformer.html

The general idea of quantizing points so that similar points fall into the same bucket or a near bucket is a powerful one.

It's more appropriately used to answer Ball queries (i.e. find all points within distance r of the query) than near neighbor queries.

I've used it in multiple context :

-Low dimension : Computing all pair-wise interaction for nearby particles in physics simulations : You hash particles positions to cells, and you check interactions between nearby cells.

-Image Similarity search for candidates to loop closure in SLAM algorithms (Depending on the number of images you have brute-forcing in hamming space is often sufficient)

-Visual vocabulary, each key-point has a descriptor value, when you use opencv with SIFT/SURF for matching you can use Flann with LSH.

-K-mean variant clustering with large K, when K is large you need an index to find the closer point efficiently (used to compute the visual vocabulary above)

-Neural networks : for example it can be very tempting to put some kind of LSH index on the GPU as a standard neural-network layer, but if it's too small you are better with standard brute-force, and if it's too big you run out of memory. So you are looking for the sweet-spot. But remembering that if you have an index with 10M elements and you update sparsely only 10 elements by iteration, you'll need at least 1M iterations before each element has moved. So your algorithm will take a long time to converge.

-P2P indices : Tables of hashes that can be used to recover similar data when querying them.

The version of LSH described in the article is not often used because in real data you can often take advantage of some hierarchical representation inside the data.

It's among one of the many space-partitioning technique with multiple overlapping partitions.

Depending on the constraints on your data, it's hard to make it shine. It shines best when there are large quantity of data, but it consumes a lot of memory so it may be useful to have the index on disk, and ideally you'd like to be able to update the index incrementally. The various existing libraries work well for the specific situations they are designed to handle, but quite often you are still better rolling your own space-partitioning technique for your specific constraints.

Also quite often instead of an approximate search and have to fiddle with some tuning parameters, it's better to use some exact search : If you can project into hamming spaces, there are fast and exact algorithms (although memory intensive) based on the pigeon-hole principle.

I’ve used it in an HFT system. Basically as a form of latency-minimizing model compression for evaluation in production.

The problem was that the base layer model (tree ensembles) did very well in terms of training error but was much too slow to evaluate in production. With LSH, you can start with a bunch of points from the base model, then train the compressed model against the reference samples.

I've used it for a wide variety of search and recommendation problems, albeit not in isolation. In practice, I've found that it is a great way to reduce the size of a search space before handing the problem off to a more precise algorithm.

yes, this is true. In 2D/3D, sorting into regular space partitions of exponentially decreasing size (e.g. KD-trees) is far more effective - roughly log(N) vs N^rho (rho < 1). In high dimensions, the simple partitioning strategy runs up against the "curse of dimensionality" which is where LSH starts to work better.

I was barely hanging on to a lot of the math notation, but the author argues the advantage of the randomization is that on average the performance will be constant across all datasets. That is, once you develop a sense for how the system performs, you shouldn’t be surprised by wild performance swings.

If that is not a valuable feature for you, the I believe you could use any clustering hash function you want, including a deterministic one.

Malware detection uses it as a heuristic to peg specific “variants” to each other. Basically LSH is great for comparing corpuses of data that are slightly different.

If you hash the data using something like SHA256 and even one byte is different, it’ll produce a radically different hash (which is by design). With LSH you can have a measurement to say “corpus A has a 90% overlap with corpus B”, or in a single bit flip case, a very high correlation.

It actually has a lot of overlap with deep learning. Here's an NLP example.

Lets say you have millions of phrases and you want to find the ones that are the most similar to a given one that you've chosen. One way of doing this would be to create embedding for each phrase and looking at some metric like cosine similarity of the embeddings to determine closeness of the phrases. The problem is, you don't want to have to compare the embedding of your phrase to every other phrase in your collection. In this case, LSH can help you narrow it down.

Image similarity.

Well, that was one hell of a rabbit hole.

To some extent both define a kind of fuzzy neighbourhood for each point, and both kind of induce a topology on the points. Both also seem to end up with some kind of weighted graph.

That said the UMAP approach has some very deep mathematical foundations, so it could take you a while to work that one out for a LSH approach.

That said you could also just use a few random projections as an initial step and use UMAP from there. The random projections should also give you a lower bound for the distance, which can be useful in finding the k nearest neighbours.

It renders fine on my end. Try checking if your browser is blocking cdnjs.cloudflare.com for some reason.

Try to disable HTTPS Everywhere or Firefox' HTTPS Only Mode. Looks like this site is badly setup and can't handle HTTP-only requests properly.