Comparison with LSH

Locality Sensitive Hashing (LSH) is an indexing method whose theoretical aspects have been studied extensively. For most application cases it performs worse than PQ in the tradeoffs between memory vs. accuracy and/or speed vs. accuracy. There has is renewed interest in LSH variants following the publication of the bio-inspired "Fly indexing" algorithm [].

However, most LSH papers avoid directly comparing with PQ. This is a bit surprising, since one of the main datasets that is used for comparison is SIFT1M, that was introduced simultaneously with PQ in the same paper.

In the following, we provide points of comparison with a few other papers, and with Faiss' own implementation of LSH, and short code snippets that show these results.

Comparison with classical LSH

Comparison with the "Fly algorithm"

Comparison with ITQ

Another useful resource is Ann-Benchmarks, although we of course dispute their result that Faiss is not the fastest package out there!