Faster and Space Efficient Indexing for Locality Sensitive Hashing

This work suggests faster and space-efficient index construction algorithms for LSH for Euclidean distance (a.k.a.~) and cosine similarity (a.k.a.~). The index construction step of these LSHs relies on grouping data points into several bins of hash tables based on their hashcode. To generate an m-dimensional hashcode of the d-dimensional data point, these LSHs first project the data point onto a d-dimensional random Gaussian vector and then discretise the resulting inner product. The time and space complexity of both ~and ~for computing an m-sized hashcode of a d-dimensional vector is $O(md)$, which becomes impractical for large values of m and d. To overcome this problem, we propose two alternative LSH hashcode generation algorithms, both for Euclidean distance and cosine similarity, namely, , ~and , , respectively. ~and ~are based on count sketch {count_sketch} and ~and ~utilize higher-order count sketch {shi2019higher}. These proposals significantly reduce the hashcode computation time from $O(md)$ to $O(d)$. Additionally, both ~and ~reduce the space complexity from $O(md)$ to $O(d)$; ~and , ~ reduce the space complexity from $O(md)$ to O(N √[N]d) respectively, where N≥ 1 denotes the size of the input/reshaped tensor. Our proposals are backed by strong mathematical guarantees, and we validate their performance through simulations on various real-world datasets.