Lsh Accuracy

It's probably unfair to say LSH is slow because it can indeed be very fast when you don't ask for accuracy. The problem is that all the available hash families distort the distance metric by so much that you cannot hope to have high recall (>90%) without forming many super bins when you index and hitting them frequently when you do online search. Ironically, it was found that k-means clustering as a LSH family beats all other hash families.

There's one application for which LSH still works well. That is when you have near-duplicate objects and you only want to find those near-duplicate objects (like reverse image search).