# Experimental Analysis of Locality Sensitive Hashing Techniques for High-Dimensional Approximate Nearest Neighbor Searches

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2020.

## Built on by (most cited first, 4 of 4)

- [From HNSW to Information-Theoretic Binarization: Rethinking the Architecture of Scalable Vector Search](https://mlsanity.com/paper/2601.11557/) (2025)
- [LSH methods for data deduplication in a Wikipedia artificial dataset](https://mlsanity.com/paper/2112.11478/) (2021)
- [Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/2607.01283/) (2026)
- [NeuRoute: Logit-Guided Neural Routing for Billion-Scale Vector Search with Sub-Hour Index Construction](https://mlsanity.com/paper/2608.15438/) (2026)

## Abstract (arXiv)

Finding nearest neighbors in high-dimensional spaces is a fundamental operation in many multimedia retrieval applications. Exact tree-based indexing approaches are known to suffer from the notorious curse of dimensionality for high-dimensional data. Approximate searching techniques sacrifice some accuracy while returning good enough results for faster performance. Locality Sensitive Hashing (LSH) is a very popular technique for finding approximate nearest neighbors in high-dimensional spaces. Apart from providing theoretical guarantees on the query results, one of the main benefits of LSH techniques is their good scalability to large datasets because they are external memory based. The most dominant costs for existing LSH techniques are the algorithm time and the index I/Os required to find candidate points. Existing works do not compare both of these dominant costs in their evaluation. In this experimental survey paper, we show the impact of both these costs on the overall performance of the LSH technique. We compare three state-of-the-art techniques on four real-world datasets, and show that, in contrast to recent works, C2LSH is still the state-of-the-art algorithm in terms of performance while achieving similar accuracy as its recent competitors.