Faster and Space Efficient Indexing for Locality Sensitive Hashing
Bhisham Dev Verma, Rameshwar Pratap · 2025
Read Faster and Space Efficient Indexing for Locality Sensitive Hashing by Bhisham Dev Verma, Rameshwar Pratap (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-06737.txt.
Introduction
Bhisham Dev Verma and Rameshwar Pratap speed up locality sensitive hashing, a method for finding near neighbors in large datasets. Building its index needs a hash code for every data point, normally computed by projecting the point onto a random vector of the same size. That cost grows as the product of two dimensions and becomes impractical for big data.
The authors replace the projection with sketching techniques borrowed from streaming algorithms. Their four variants, covering both distance and angle similarity, cut hash code time to a single pass over the data's dimension and shrink the memory footprint sharply. Strong mathematical guarantees back the shortcuts, and simulations on real datasets confirm the performance.
Catalog record
| CREATOR | Bhisham Dev Verma, Rameshwar Pratap |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 143 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-06737
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Faster and Space Efficient Indexing for Locality Sensitive Hashing Bhisham Dev Verma, Rameshwar Pratap Abstract This work suggests faster and space-efficient index construction algorithms for LSH for Euclidean distance ( a.k.a. E2LSH) and cosine similarity ( a.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 m -dimensional hashcode of the d d -dimensional data point, these LSHs first project the data point onto a d d -dimensional random Gaussian vector and then discretise the resulting inner product. The time and space complexity of both E2LSH and SRP for computing an m m -sized hashcode of a d d -dimensional vector is O ( m d ) O(md) , which becomes impractical for large values of m m and d d . To overcome this problem, we propose two alternative LSH hashcode generation algorithms both for Euclidean distance and cosine similarity, namely, CS-E2LSH, HCS-E2LSH and CS-SRP, HCS-SRP, respectively. CS-E2LSH and CS-SRP are based on count sketch [ 1 ] and HCS-E2LSH and HCS-SRP utilize higher-order count sketch [ 2 ] . These proposals significantly reduce the hashcode computation time from O ( m d ) O(md) to O ( d ) O(d) . Additionally, both CS-E2LSH and CS-SRP reduce the space complexity from O ( m d ) O(md) to O ( d ) O(d) ; and HCS-E2LSH, HCS-SRP reduce the space complexity from O ( m d ) O(md) to O ( N d N ) O(N\sqrt[N]{d}) respectively, where N ≥ 1 N\geq 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. 1 Introduction Approximate nearest neighbor (ANN) search is one of the most common subroutines in several real-life applications such as recommendation engines, duplicate detection, clustering, etc. For a given query point, the ANN problem allows it to return a point within a distance of some constant times the distance of the query point to its actual nearest neighbor. The seminal work of Indyk and Motwani [ 3 ] suggested an algorithmic framework, namely Locality Sensitive Hashing (LSH), to solve this problem. The idea of LSH [ 3 ] is based on designing a family of hash functions that group points into several buckets of hash tables such that with high probability, it maps " similar " points in the same bucket and " not so similar " points in different buckets. Consequently, this restricts the search space for a query point to that particular bucket in which it falls, leading to a sublinear search algorithm. We refer to the step of arranging points into hash tables as the indexing step. LSH functions have been studied for different similarity/distance measures, e.g. , cosine similarity [ 4 , 5 , 6 , 7 , 8 , 9 ] , Euclidean distance [ 10 , 11 ] , Hamming distance [ 3 , 12 ] , Jaccard similarity [ 13 , 14 , 15 , 16 ] , and many more. Further, such results have been utilized in a wide range of applications, e.g. , near-duplicate detection [ 17 ] , clustering [ 18 , 19 ] , audio processing [ 20 , 21 ] , image/video processing [ 22 , 23 ] , blockchain [ 24 ] , etc. The sublinear search time of the LSH algorithm comes at the cost of (preprocessing) time required to construct the indexing/hash tables. The indexing ( a.k.a. hash table construction) step requires arranging data points into several bins based on their hashcode. We elaborate it for LSH for Euclidean distance ( a.k.a. E2LSH) [ 10 , 3 ] . In the E2LSH algorithm, a hashcode of a data point is computed by projecting a d -dimensional data point on a random vector whose elements are sampled from \mathcal{N}(0,1) . The resultant inner product is discretized by adding a random number (let’s say b ) uniformly sampled from [0,w] , dividing it by w , and finally computing the floor (see Definition 2 ). The process is independently repeated m times to generate an m -sized hashcode of the data point. This can be considered as projecting a d -dimensional input vector on a d\times m random projection matrix whose each entry is sampled from a Gaussian distribution, followed by discretizing the components of the resultant vector. Therefore, to generate an m sized hashcode of a datapoint, E2LSH requires O(md) running time and space. Similarly, signed-random-projection ( a.k.a. SRP) [ 4 ] , which is an LSH for real-valued vectors for cosine similarity, also requires O(md) running time and space to generate an m -sized hashcode of the input vector. The idea of SRP is similar to E2LSH, where the d -dimensional input vector is projected on d -dimensional random Gaussian vectors, and the hashcode is assigned to 0 or 1 based on the sign of the resultant inner product (see Definition 3 ). The time and space required by the E2LSH and SRP in the preprocessing step become prohibitive for high-dimensional datasets. This work addresses this challenge and suggests a simple, intuitive algorithmic approach that significantly improves the indexing step’s time and space complexity. At a high level, our idea is to use a super sparse projection matrix for projecting the input vector, followed by discretizing the resultant inner product. We use the count-sketch based projection matrix [ 4 ] for this purpose. This reduces the preprocessing step’s space and execution time to O(d) in contrast to the O(md) space and time needed by E2LSH and SRP to produce an m -sized hashcode. We give another result that gives a more space-efficient algorithm. We use the recently proposed higher order count sketch (HCS) [ 2 ] for this purpose. At the core, our idea is to visualize the input vector as a high-order tensor, compress it using higher order count sketch [ 2 ] , discretize the resultant tensor, and finally unfold the tensor to a vector that serves as the hashcode of the input vector. For example, for N=2 , where N denotes the order of tensor, we reshape the d -dimensional input vector as a matrix of size \sqrt{d}\times\sqrt{d} . 1 1 1 For ease of analysis, we consider the same dimension along each mode of the reshaped tensor as well as the compressed (HCS) tensor i.e. , d^{\frac{1}{N}} and m^{\frac{1}{N}} respectively. However, our results can easily be extended to different values of mode dimensions. We then compress this matrix using a higher order count sketch and obtain an \sqrt{m}\times\sqrt{m} matrix. This compression step can be considered as left multiplying the input matrix with a count-sketch projection matrix of size \sqrt{m}\times\sqrt{d} , and right multiplying it with a count-sketch matrix of size \sqrt{d}\times\sqrt{m} . We then discretize the resultant \sqrt{m}\times\sqrt{m} matrix, and finally reshape this matrix and obtain the desired m -sized hashcode of the input d -dimensional vector. In both results, we show that the probability of hash collision is monotonic to the pairwise similarity between input points. Our key contributions