Locality-sensitive hashing (LSH) is an effective randomized technique widely
used in many machine learning tasks. The cost of hashing is proportional to
data dimensions, and thus often the performance bottleneck when dimensionality
is high and the number of hash functions involved is large. Surprisingly,
however, little work has been done to improve the efficiency of LSH
computation. In this paper, we design a simple yet efficient LSH scheme, named
FastLSH, under l2 norm. By combining random sampling and random projection,
FastLSH reduces the time complexity from O(n) to O(m) (m<n), where n is the
data dimensionality and m is the number of sampled dimensions. Moreover,
FastLSH has provable LSH property, which distinguishes it from the non-LSH fast
sketches. We conduct comprehensive experiments over a collection of real and
synthetic datasets for the nearest neighbor search task. Experimental results
demonstrate that FastLSH is on par with the state-of-the-arts in terms of
answer quality, space occupation and query efficiency, while enjoying up to 80x
speedup in hash function evaluation. We believe that FastLSH is a promising
alternative to the classic LSH scheme.

通过随机抽样和随机投影的组合，FastLSH 算法将 LSH 计算的时间复杂度从 O (n) 降低到 O (m)（其中 m < n），并具有可证明的 LSH 属性，是一种有希望替代经典 LSH 方案的方法。