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

user:	bencoleman
created:	June 25, 2021
karma:	2