# A Survey on Locality Sensitive Hashing Algorithms and their Applications

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2021.

## Built on by (most cited first, 30 of 40)

- [Graph Retrieval-Augmented Generation: A Survey](https://mlsanity.com/paper/2408.08921/) (2024)
- [MagicPIG: LSH Sampling for Efficient LLM Generation](https://mlsanity.com/paper/2410.16179/) (2024)
- [A Survey on Retrieval-Augmented Text Generation for Large Language Models](https://mlsanity.com/paper/2404.10981/) (2024)
- [Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2311.12351/) (2023)
- [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023)
- [On the De-duplication of LAION-2B](https://mlsanity.com/paper/2303.12733/) (2023)
- [Mercury: A Code Efficiency Benchmark for Code Large Language Models](https://mlsanity.com/paper/2402.07844/) (2024)
- [Similarity search in the blink of an eye with compressed indices](https://mlsanity.com/paper/2304.04759/) (2023)
- [The Synergy between Data and Multi-Modal Large Language Models: A Survey from Co-Development Perspective](https://mlsanity.com/paper/2407.08583/) (2024)
- [EraRAG: Efficient and Incremental Retrieval Augmented Generation for Growing Corpora](https://mlsanity.com/paper/2506.20963/) (2025)
- [Exploring Musical Roots: Applying Audio Embeddings to Empower Influence Attribution for a Generative Music Model](https://mlsanity.com/paper/2401.14542/) (2024)
- [Antidote: A Unified Framework for Mitigating LVLM Hallucinations in Counterfactual Presupposition and Object Perception](https://mlsanity.com/paper/2504.20468/) (2025)
- [An Automatic Graph Construction Framework based on Large Language Models for Recommendation](https://mlsanity.com/paper/2412.18241/) (2024)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [LeanVec: Searching vectors faster by making them fit](https://mlsanity.com/paper/2312.16335/) (2023)
- [Data Leakage Detection and De-duplication in Large Scale Geospatial Image Datasets](https://mlsanity.com/paper/2304.02296/) (2023)
- [How Social is It? A Benchmark for LLMs' Capabilities in Multi-user Multi-turn Social Agent Tasks](https://mlsanity.com/paper/2505.04628/) (2025)
- [From Similarity to Vulnerability: Key Collision Attack on LLM Semantic Caching](https://mlsanity.com/paper/2601.23088/) (2026)
- [Deep Hashing via Householder Quantization](https://mlsanity.com/paper/2311.04207/) (2023)
- [HeteroMILE: a Multi-Level Graph Representation Learning Framework for Heterogeneous Graphs](https://mlsanity.com/paper/2404.00816/) (2024)
- [Evaluating the Effectiveness and Efficiency of Demonstration Retrievers in RAG for Coding Tasks](https://mlsanity.com/paper/2410.09662/) (2024)
- [B+ANN: A Fast Billion-Scale Disk-based Nearest-Neighbor Index](https://mlsanity.com/paper/2511.15557/) (2025)
- [A Super Fast K-means for Indexing Vector Embeddings](https://mlsanity.com/paper/2603.20009/) (2026)
- [Web Phishing Net (WPN): A scalable machine learning approach for real-time phishing campaign detection](https://mlsanity.com/paper/2502.13171/) (2025)
- [Provenance Detection for AI-Generated Images: Combining Perceptual Hashing, Homomorphic Encryption, and AI Detection Models](https://mlsanity.com/paper/2503.11195/) (2025)
- [Bang for the Buck: Vector Search on Cloud CPUs](https://mlsanity.com/paper/2505.07621/) (2025)
- [Evaluating the Performance of RAG Methods for Conversational AI in the Airport Domain](https://mlsanity.com/paper/2505.13006/) (2025)
- [Learning by Examples Based on Multi-level Optimization](https://mlsanity.com/paper/2109.10824/) (2021)
- [LSH methods for data deduplication in a Wikipedia artificial dataset](https://mlsanity.com/paper/2112.11478/) (2021)
- [Experimental Analysis of Machine Learning Techniques for Finding Search Radius in Locality Sensitive Hashing](https://mlsanity.com/paper/2211.09093/) (2022)

## Abstract (arXiv)

Finding nearest neighbors in high-dimensional spaces is a fundamental operation in many diverse application domains. Locality Sensitive Hashing (LSH) is one of the most popular techniques for finding approximate nearest neighbor searches in high-dimensional spaces. The main benefits of LSH are its sub-linear query performance and theoretical guarantees on the query accuracy. In this survey paper, we provide a review of state-of-the-art LSH and Distributed LSH techniques. Most importantly, unlike any other prior survey, we present how Locality Sensitive Hashing is utilized in different application domains.