4 ms·

Hi All, it's true that LSH (locality sensitive hashing) and DR (dimension reduction) are very related. They both derive their correctness from the same strong c

Hi All, it's true that LSH (locality sensitive hashing) and DR (dimension reduction) are very related. They both derive their correctness from the same strong concentration phenomenon. But, they are used/designed for different use cases. DR is mostly concerned with preserving distances such that c * D( f(x), f(y) ) < d(x,y) < C*D( f(x), f(y) ) Here, f(x) is the mapping of x to a lower dimensional space (or any other object, really). d(-,-) and D(-,-) are the original distance measure and new distance measure respectively. The smaller the ratio C/c the better. Clearly, the computational overhead of applying f and D are also important. LSH, on the other hand, is mostly concerned with probabilistically filtering and searching for nearby points efficiently. Here are some (old) class notes from a course I gave 2013https://edoliberty.github.io//classnotes/datamining2013/pdfs/12_approximate_nearest_neighbor_search.pdf https://edoliberty.github.io//classnotes/datamining2013/pdfs... While LSH is mathematically beautiful, it is no longer considered the gold standard for ANN. There are many open source algorithms that outperform LSH on most datasets. (I founded a vector search company: https://www.pinecone.io https://www.pinecone.io)

azinman2 5y ago
What are the gold standard algorithms now?
- cgreerrun 5y ago
  This site keeps track of them: https://github.com/erikbern/ann-benchmarks#glove-100-angular https://github.com/erikbern/ann-benchmarks#glove-100-angular ScaNN is currently SOTA: https://ai.googleblog.com/2020/07/announcing-scann-efficient-vector.html https://ai.googleblog.com/2020/07/announcing-scann-efficient...
  - azinman2 5y ago
    Thanks!
    - edoliberty 5y ago
      My 2c, the choice of algorithm is quite complex... It is data dependent and also depends on your read/write ratio, latency and accuracy needs, memory/cpu, and many other factors. If I were you I'd look for a versatile solution more than "the best" algorithm cos that choice will likely change... just sayin'...
    - cgreerrun 5y ago
      +1 to sibling comment about not choosing the SOTA just cuz SOTA (if you're in the market for an ANN algo). Almost all the ones there are pretty darn fast these days and many (e.g. hnsw) are implemented out of the box by libraries like nmslib. Also, most search use cases have requirements besides just the "get_k_nearest" functionality too (scoring-level filtering, business logic built into scoring unrelated to similarity, disparate query patterns that don't fit nicely into a single similarity space), so unless you only need to retrieve the K most-similar documents it might not be a good solution.
molodec 5y ago
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!
bencoleman 5y ago
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 https://arxiv.org/abs/1808.10530 [2]: http://proceedings.mlr.press/v97/siminelakis19a http://proceedings.mlr.press/v97/siminelakis19a [3]: https://arxiv.org/abs/2102.08341 https://arxiv.org/abs/2102.08341 [4]: https://arxiv.org/abs/1910.14162 https://arxiv.org/abs/1910.14162 [5]: https://arxiv.org/abs/1912.02283 https://arxiv.org/abs/1912.02283 [6]: https://arxiv.org/abs/2106.11426 https://arxiv.org/abs/2106.11426

azinman2 5y ago

What are the gold standard algorithms now?

cgreerrun 5y ago
This site keeps track of them: https://github.com/erikbern/ann-benchmarks#glove-100-angular https://github.com/erikbern/ann-benchmarks#glove-100-angular ScaNN is currently SOTA: https://ai.googleblog.com/2020/07/announcing-scann-efficient-vector.html https://ai.googleblog.com/2020/07/announcing-scann-efficient...
- azinman2 5y ago
  Thanks!
  - edoliberty 5y ago
    My 2c, the choice of algorithm is quite complex... It is data dependent and also depends on your read/write ratio, latency and accuracy needs, memory/cpu, and many other factors. If I were you I'd look for a versatile solution more than "the best" algorithm cos that choice will likely change... just sayin'...
  - cgreerrun 5y ago
    +1 to sibling comment about not choosing the SOTA just cuz SOTA (if you're in the market for an ANN algo). Almost all the ones there are pretty darn fast these days and many (e.g. hnsw) are implemented out of the box by libraries like nmslib. Also, most search use cases have requirements besides just the "get_k_nearest" functionality too (scoring-level filtering, business logic built into scoring unrelated to similarity, disparate query patterns that don't fit nicely into a single similarity space), so unless you only need to retrieve the K most-similar documents it might not be a good solution.

molodec 5y ago

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!

bencoleman 5y ago

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 https://arxiv.org/abs/1808.10530 [2]: http://proceedings.mlr.press/v97/siminelakis19a http://proceedings.mlr.press/v97/siminelakis19a [3]: https://arxiv.org/abs/2102.08341 https://arxiv.org/abs/2102.08341 [4]: https://arxiv.org/abs/1910.14162 https://arxiv.org/abs/1910.14162 [5]: https://arxiv.org/abs/1912.02283 https://arxiv.org/abs/1912.02283 [6]: https://arxiv.org/abs/2106.11426 https://arxiv.org/abs/2106.11426