Learning to Hash Robustly, Guaranteed. (arXiv:2108.05433v4 [cs.DS] UPDATED)

The indexing algorithms for the high-dimensional nearest neighbor search
(NNS) with the best worst-case guarantees are based on the randomized Locality
Sensitive Hashing (LSH), and its derivatives. In practice, many heuristic
approaches exist to "learn" the best indexing method in order to speed-up NNS,
crucially adapting to the structure of the given dataset.

Oftentimes, these heuristics outperform the LSH-based algorithms on real
datasets, but, almost always, come at the cost of losing the guarantees of
either correctness or robust performance …

arxiv hash learning