bencoleman

Author here - thanks for the feedback everybody! Agree that the weighted version and the skeleton version would be cool to talk about. Perhaps in future :)

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.

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