# Faster and Space Efficient Indexing for Locality Sensitive Hashing

arXiv: https://arxiv.org/abs/2503.06737 · HTML: https://mlsanity.com/paper/2503.06737/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 18 references that are in the map.
- First posted on arXiv 9 Mar 2025.

## Builds on (most cited first, 1 of 1)

- [Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring](https://mlsanity.com/paper/2004.05345/) (2020)

## Abstract (arXiv)

This work suggests faster and space-efficient index construction algorithms for LSH for Euclidean distance (textita.k.a.~ELSH) and cosine similarity (textita.k.a.~SRP). 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 ELSH~and SRP~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, CSELSH, HCSELSH~and CSSRP, HCSSRP, respectively. CSELSH~and CSSRP~are based on count sketch citecountsketch and HCSELSH~and HCSSRP~utilize higher-order count sketch citeshi2019higher. These proposals significantly reduce the hashcode computation time from O(md) to O(d). Additionally, both CSELSH~and CSSRP~reduce the space complexity from O(md) to O(d); ~and HCSELSH, HCSSRP~ 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.