A Survey on Locality Sensitive Hashing Algorithms and their Applications

2021/02/17 by Jafari, Omid, Maurya, Preeti, Nagarkar, Parth +2 · 8 citations
#Databases (cs.DB) #FOS: Computer and information sciences #H.2.4

paper · doi:10.48550/arxiv.2102.08942

Abstract

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.

Cited by

• Distribution-Aware Exploration for Adaptive HNSW Search
• PG-HIVE: Hybrid Incremental Schema Discovery for Property Graphs
• Improving the Identification of Real-world Malware's DNS Covert Channels Using Locality Sensitive Hashing
• B+ANN: A Fast Billion-Scale Disk-based Nearest-Neighbor Index
• AudioNet: Supervised Deep Hashing for Retrieval of Similar Audio Events
• Individualized non-uniform quantization for vector search
• GoVector: An I/O-Efficient Caching Strategy for High-Dimensional Vector Nearest Neighbor Search
• Random-Access Ranked Retrieval and Similarity Search

Related

• Fast Locality-Sensitive Hashing Frameworks for Approximate Near Neighbor Search
• Improving Similarity Search with High-dimensional Locality-sensitive Hashing
• Density Sensitive Hashing
• A Refined Analysis of LSH for Well-dispersed Data Points
• Confirmation Sampling for Exact Nearest Neighbor Search