Source-linked AI summary
A Survey on Locality Sensitive Hashing Algorithms and their Applications
Omid Jafari, Preeti Maurya, Parth Nagarkar, Khandker Mushfiqul Islam, Chidambaram Crushev
arXiv:2102.08942v1cs.DB
TL;DR
Finding nearest neighbors in high-dimensional spaces is important across diverse applications. This survey reviews and categorizes LSH techniques and distributed frameworks, and surveys LSH applications across different domains.
Problem
Finding nearest neighbors in high-dimensional spaces is an important problem in diverse applications.
Source: §1 · p. 1Method
The survey reviews recent LSH advances, categorizes techniques by hash-function family, explains distributed-framework architectures, and categorizes application papers.
Source: §6 · p. 18Results
The survey presents a categorization of LSH techniques, distributed frameworks, and application papers.
Source: §6 · p. 18Takeaways & Limitations
The survey describes how LSH is used across different application domains.
Source: §6 · p. 18SLSH requires several data shuffles across worker nodes.
Source: §4 · p. 9
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
High-dimensional nearest-neighbor search is important across diverse applications, but indexing faces the curse of dimensionality. The survey reviews LSH techniques and highlights their approximate-search trade-offs, then extends its coverage to distributed frameworks and application domains.
1 INTRODUCTION
- High-dimensional indexing structures can be outperformed by linear scans, motivating approximate nearest-neighbor search when exact accuracy is unnecessary.Approximate search trades accuracy for faster performance.Source: §1 · p. 1
1.1 Locality Sensitive Hashing
- LSH maps high-dimensional data into lower-dimensional representations with random hash functions, so nearby points have a high probability of sharing buckets.The query success guarantee governs the performance–accuracy trade-off.Source: §1.1 · pp. 1–2
1.2.1 Motivation for using LSH:
- Earlier surveys did not provide an extensive review of LSH-based techniques, while this survey focuses on ANN and includes distributed frameworks and application domains.The authors describe these latter two topics as absent from prior surveys, to their knowledge.Source: §1.2.2 · pp. 2–3
1.3 Contributions
- The survey categorizes LSH techniques by hash-function family and workflow, reviews distributed-framework architectures, and organizes applications by domain.It aims to help application domains improve efficiency by changing their base algorithm.Source: §1.2.2 · p. 2, §1.3 · p. 3
2 BACKGROUND AND KEY CONCEPTS
The section frames c-approximate nearest-neighbor search and explains how LSH uses projections to preserve locality. It introduces the collision-probability condition and popular hash families for several distance metrics.
Approximate Nearest Neighbor Search
- c-ANN search returns points whose distance to the query is at most c times the true nearest neighbor's distance.The section also introduces c-k-ANN search, but its definition is incomplete in the supplied passage.Source: §2 · p. 3
LSH and Locality
- LSH projects high-dimensional points into lower-dimensional spaces using hash functions intended to preserve the proximity of nearby points.The paper limits its focus to LSH-based methods for ANN, referring readers elsewhere for non-LSH methods.Source: §2 · p. 3
LSH Sensitivity
- An (R, cR, p1, p2)-sensitive hash collides with probability at least p1 for points within R and at most p2 for points beyond cR, with c > 1 and p1 > p2.The section describes these probabilities as high for close points and low for points that are not close.Source: §2 · p. 3
Hash Families
- Angular LSH uses the sign of a random normal projection, while Jaccard LSH uses a random permutation and has collision probability equal to Jaccard similarity.For angular distance, the section relates collision probability to the angle between points.Source: §2 · p. 4
3 REVIEW OF LSH TECHNIQUES
This section reviews LSH techniques and variants, covering Hamming- and Minkowski-based methods as well as approaches adapted to particular distance metrics, data characteristics, query workloads, and kernel- or application-specific settings. It emphasizes sub-linear query time and theoretical query-accuracy guarantees.
3.1 Hamming-based LSH Techniques
- The original Hamming LSH addresses (R,c)-near-neighbor search with multiple hash functions and tables, whose optimal counts are chosen to maintain constant hashing probabilities.The survey says the design aims to guarantee good search quality.Source: §3.1 · p. 4
- Boosted LSH sequentially trains linear classifiers using adaptive boosting to reduce redundant projections and shows comparable performance to machine- and deep-learning approaches in speech enhancement.Source: §3.1 · p. 4
3.2 Minkowski-based LSH Techniques
- E2LSH combines hash functions and tables to raise nearby-point collisions while reducing false positives and negatives; Multi-probe LSH searches nearby buckets in distance order to use fewer tables at the same accuracy.Multi-probe assigns distance scores to buckets and accesses them in increasing order.Source: §3.2 · pp. 4–5
- Data-adaptive Minkowski methods tailor projections or buckets to the data: density-based hashing uses finer buckets in dense regions, while PCA-based projections seek a more uniform dataset.Hadamard-based ACHash and DHHash use one and two transformations, respectively, to estimate Euclidean and angular distances and reduce LSH runtime.Source: §3.2 · p. 5
- C2LSH uses one table with m projections and collision counting to identify candidates, expanding the projection search radius until its candidate-count and true-positive stopping conditions are met.Candidates are checked by Euclidean distance against cR; the radius increases exponentially if the stopping conditions are unmet.Source: §3.2 · p. 5
- SRS uses R-tree indexes and incremental search to estimate original-space distances from projections, aiming to keep traditional LSH guarantees with smaller indexes.SK-LSH instead places nearby projected points on the same or close disk pages using a space-filling curve and a distance measure over compound hash keys.Source: §3.2 · p. 6
- I-LSH incrementally expands the projection search radius to avoid reading unnecessary disk buckets, but its reduced I/O comes with high computation costs.The survey reports the computation-cost limitation based on its experimental paper.Source: §3.2 · p. 6
- EI-LSH changes I-LSH’s stopping condition using a precomputed parameter, while PM-LSH uses PM-Trees and a tunable confidence interval to improve distance estimation and query processing.EI-LSH’s parameter depends on the number of projections, approximation ratio, and success probability.Source: §3.2 · p. 7
- R2LSH uses two-dimensional projections, B+-Trees, and a query-centric ball to search neighboring areas and save I/O costs.Source: §3.2 · p. 7
3.3 Angular-based LSH Techniques
- For angular similarity, SBLSH reduces estimation variance with orthogonalized super bits, while BOLSH uses batches of orthogonal projections to improve accuracy.The reported SBLSH variance reduction applies when the angle lies in (0, π/2]; BOLSH is supported experimentally and theoretically.Source: §3.3 · p. 7
3.4 Jaccard-based LSH Techniques
- LSH Forest stores compound hash keys in prefix trees and searches top-down and bottom-up, allowing traversal to stop once enough results are found.Source: §3.4 · p. 7
3.5 Other LSH Techniques
- BayesLSH [94] estimates Euclidean distance from collision distributions to speed false-positive removal, while S2LSH selects smaller signature regions near the query’s center.BayesLSH applies to Euclidean, angular, and Jaccard metrics; S2LSH supports angular and Euclidean metrics.Source: §3.5.1 · pp. 7–8
- For large query workloads, a representative query set reduces LSH lookups, and the approach uses optimized QALSH with compound keys and R-trees.The method is described as applicable to Euclidean-, Jaccard-, and Hamming-based LSH.Source: §3.5.1 · p. 8
- Kernelized methods construct LSH projections from a kernel and sparse samples [65], or adapt BayesLSH to arbitrary kernel similarities as K-BayesLSH.Source: §3.5.2 · p. 8
- Application-specific methods cluster categorical values before LSH bucketing, or learn graph bins and predict which bins to search for Edit and Optimal Transport distances [32].Source: §3.5.3 · p. 8
4 DISTRIBUTED FRAMEWORKS
The section surveys distributed LSH architectures and their approaches to partitioning, indexing, query processing, and load balancing. It describes designs for reducing network work as well as application-specific and streaming frameworks.
Distributed LSH Architecture
- A two-level mapping architecture groups similar LSH buckets on the same peers, balances peer load, and is reported to minimize network I/Os.The framework targets KNN and range queries in high-dimensional datasets.Source: §4 · p. 9
Layered LSH
- Layered LSH uses Hadoop for disk-based operation and Active DHT in memory, but theoretical network-operation guarantees are provided only for the single-hash-table setting.It works in Euclidean space and uses Entropy LSH as its base method.Source: §4 · p. 9
Parallel LSH
- PLSH supports streaming KNN search with caching, insert-optimized delta tables, periodic index merging, and bitmap-based duplicate removal, but is designed only for angular distance.New-data indexes are held in delta tables before being merged with the main index structures.Source: §4 · p. 9
Application-Specific Frameworks
- A privacy-preserving record-linkage framework distributes Minhash signatures encoded in Bloom filters, while CLSH partitions data with K-means and builds local indexes on compute nodes.CLSH directs queries to nodes according to the distance to cluster centers.Source: §4 · p. 9
Spark LSH Frameworks
- SLSH sends queries to all workers and incurs heavy network costs from data shuffles, while SES-LSH uses BKDR partitioning to co-locate points from the same hash tables for local computation.SLSH distributes dataset subsets across workers, which calculate their hash values during indexing.Source: §4 · p. 9
General Distributed Platforms
- LoSHa offers MapReduce APIs for distributing different LSH methods and uses bucket compression and deduplication, while C2Net partitions buckets with minimum spanning trees and spectral clustering.C2Net also supports virtual rehashing by merging bucket blocks across two MapReduce rounds.Source: §4 · p. 9
Load Balancing
- A distributed load-balancing approach predicts single-table data distribution with two theoretical models and uses CDF-based and virtual-node methods to balance indexing load.Its evaluations use the Gini coefficient to assess scalability.Source: §4 · pp. 9–10
Image Search and Master-Slave Frameworks
- RDH splits image datasets across nodes for local LSH indexing, and a master-slave design distributes queries and aggregates ranked results while aiming to maintain accuracy.RDH reports that accuracy does not change significantly when all nodes use the same hash functions.Source: §4 · pp. 8, 10
5 APPLICATIONS
The survey reviews how LSH is used across application domains, categorizing recent and popular papers by problem and by their LSH algorithms and hash families when reported. Audio and image/video examples include retrieval, identification, and anomaly detection.
5 APPLICATIONS
- The survey reports more than 1,000 application papers using LSH and organizes selected recent, popular work by problem and methodology.It notes the LSH algorithm and hash family when a paper specifies them.Source: §5 · p. 10
5.1 Audio Processing
- [120] uses Order Statistics LSH to map multi-probe histograms of audio-query Chroma sequences to hash keys, then compares associated histograms to return similar tracks.The approach includes a post-filtering step.Source: §5.1 · p. 10
- [41] uses LSH to search similar music clusters from MFCC and time-histogram features represented as a bag of words, instead of linear search with O(N^2) cost.The process first extracts features and applies K-Means clustering.Source: §5.1 · p. 10
- [83] indexes pitch vectors with LSH and uses Euclidean distance to retrieve the top-k Ragas most similar to a query.The method stores pitch vectors and their labels for recordings in a database.Source: §5.1 · p. 10
5.2 Image/Video Processing
- [64] extends LSH to arbitrary kernel functions while preserving sub-linear time, and proposes KLSH for image retrieval using kernel-space projections and a Gaussian RBF kernel.The projections are required only in the kernel space and for a limited number of database objects.Source: §5.2 · p. 11
- [128] detects video anomalies by comparing LSH buckets for test and training data, with bloom filters and PSO-selected hash functions used in the approach.A test point in a different bucket is treated as abnormal; one in the same bucket is treated as normal. The authors report that PSO improves detection quality.Source: §5.2 · p. 11
5.3 Security/Privacy Related
The survey describes LSH applications in security and privacy, blockchain, and data mining, covering workflows from malware clustering and authentication to anomaly detection and similarity search.
5.3 Security/Privacy Related
- For anonymization, Minhash LSH and Map-Reduce split the data into several partitions containing similar records; those partitions are anonymized using a recursive agglomerative k-member clustering method.Source: §5.3 · p. 11
- [8] combines LSH with deep neural networks and PCA to map mobile-device images to binary prints for authentication, using a classifier to set an error-tolerance threshold and Hamming distance for matching.The system is called ai.lock.Source: §5.3 · p. 11
5.4 Blockchain
- [131] adds image feature vectors to a blockchain and uses E2LSH to identify copyright owners from network data blocks when a user seeks to use an image.The listed blocks include authority, image index, usage, and ownership-change items.Source: §5.4 · pp. 11–12
5.5 Data Mining Approaches
- For noun clustering, LSH approximates a cosine-similarity matrix to speed its construction, while another study reports that LSH reduces nearest-cluster search complexity.The latter uses LSH in single-link hierarchical clustering and reports both experimental and theoretical support.Source: §5.5 · p. 12
- LSHiForest supports different distance metrics and LSH families, and experiments report better time efficiency and anomaly-detection quality than other methods.The framework is built on the isolation-based anomaly detection forest iForest.Source: §5.5 · p. 12
- [112] proposes multilayer LSH tables and an adaptive layer-search strategy to speed up traffic anomaly detection when robust matrix factorization is computationally expensive.The layers map origin-destination pairs at different similarity levels using Euclidean distance.Source: §5.5 · p. 12
5.6 Text/Document Processing
The survey covers LSH for text and document tasks, including document similarity, streaming signatures, and name matching, as well as biological sequence and molecule applications.
5.6 Text/Document Processing
- [53] proposes Semi-Supervised SimHash (S3H) for similar-document search, learning feature weights and using LSH fingerprints to retrieve results.The described pipeline maps data into an L-dimensional Hamming space before generating fingerprints.Source: §5.6 · p. 12
- [37] uses LSH with Jaccard distance to generate candidate pairs of similar names, then filters them with Full Damerau-Levenshtein distance and aggregates them using a graph..Source: §5.6 · p. 12
- [104] generates LSH signatures online for large text collections, supporting streaming while avoiding explicit feature-vector or random-matrix representations.It uses a fixed pool of random values for features and cosine similarity.Source: §5.6 · p. 13
5.7 Biological Sciences
- LSH-ALL-PAIRS groups sequence shingles by hash value and compares shingles within a class, while MHAP uses MinHash fingerprints and Hamming distance to identify overlaps between noisy long reads.MHAP's Hamming distance approximates the Jaccard distance of shingles.Source: §5.7 · p. 13
- MASH provides a MinHash toolkit and a significance test, and introduces Mash distance to estimate the mutation rate between sequences from MinHash fingerprints.The distance can be computed using only those fingerprints.Source: §5.7 · p. 13
- MHFP6 applies MinHash to molecular substrings and indexes the resulting fingerprints with LSH Forest for nearest-neighbor retrieval in molecular benchmarking.The fingerprint covers substrings up to six bonds.Source: §5.7 · p. 13
5.8 Geological Sciences
The survey describes LSH applications in geological sciences and graph processing, including spatial matching, trajectory operations, graph compression, and graph similarity search.
5.8 Geological Sciences
- [121] uses an R-tree followed by edge-based LSH to scale point-polygon pairing for INSIDE and WITHIN detection, then probes for nearby geo-edges.The cited work addresses real-time processing of hundreds of polygons and points.Source: §5.8 · p. 13
- [89] uses centroid-based hashing to find nearest neighbors during roadmap construction, retrieving candidate points from the Voronoi cells associated with centroids.The work reports faster construction without reducing quality.Source: §5.8 · p. 13
- [79] uses LSH to filter similar patterns in 2D and 3D image libraries before exhaustive similarity calculations, using Euclidean distance for continuous images and Hamming distance for categorical images.The subsequent exhaustive search uses Run-Length Encoding compression.Source: §5.8 · p. 13
- [6] applies LSH to Hausdorff and Fréchet distances for GPS trajectory tasks and builds Multi-Resolution Trajectory Sketches for compact storage and faster insertion.The tasks include nearest-neighbor search, distance estimation, clustering, and classification.Source: §5.8 · p. 14
5.9 Graph Processing
- [123] converts query and target graphs to high-dimensional vectors, then uses Multi-Probe LSH and Euclidean distance to find nearest graphs sharing the query's semantic class.The described setting is undirected, vertex-labeled simple graphs without self-loops or multiple edges.Source: §5.9 · p. 14
- [57] uses Min-Hash to find similar graph nodes for faster graph compression and proposes WOLSH to favor similar Min-Hash values from higher-weight neighbors.The strategy addresses graphs with edge weights.Source: §5.9 · p. 14
5.10 Machine Learning
The section surveys LSH applications in machine learning and healthcare, including maximum inner product search, model classification, speech features, and medical signal or image retrieval. Approaches adapt hashing to varying vector norms, multiple distance metrics, or application-specific candidate selection.
5.10 Machine Learning
- When dataset-point norms vary, MIPS is difficult to solve with near-neighbor methods; ALSH uses different hash functions for bucket creation and probing.ALSH is based on Euclidean-distance E2LSH.Source: §5.10 · p. 14
- For linear SVM classification, hashing the weight vector and features lets an approximate classifier estimate their dot product through Hamming distance.The classifier uses h(x) = sgn(w·x + b).Source: §5.10 · p. 14
- LPDA-LSH addresses pairwise-distance costs in manifold-learning speech features by creating candidate sets within hash buckets before constructing neighborhood graphs.Candidate sets are concatenated by class labels to form within-class and inter-class graphs.Source: §5.10 · p. 14
- For MIPS with long-tailed norm distributions, NORM-RANGING LSH partitions by norm percentiles and applies the state-of-the-art method separately to each partition.A new similarity metric defines how to probe across partitions.Source: §5.10 · p. 15
- H2ALSH transforms MIPS subsets with Query Normalized First, indexes them using QALSH, and reports the union of their results.The transformation is presented as reducing error from asymmetric MIPS strategies.Source: §5.10 · p. 15
5.11 Healthcare
- A two-level LSH approach retrieves approximate neighbors by repeating stratification and cosine-distance hashing, then performing a linear search and majority vote.The training data is stratified using l1 distance before cosine-distance LSH is applied within each bucket.Source: §5.11 · p. 15
- For bone-scan image retrieval, FLSH [114] uses SIFT features built from detected key points and their assigned orientations.The described pipeline detects potential minima with Difference of Gaussian and evaluates the normalized Laplacian at each key point.Source: §5.11 · p. 15
- For ECG prediction, LSH indexes training features and classifies a new signal by the majority class among its nearby points [4].A two-level approach stratifies training data using l1 distance, applies cosine-distance LSH within each bucket, then votes among retrieved neighbors.Source: §5.11 · p. 15
5.12 Plagiarism/Near-Duplicate Detection
The section describes LSH methods for near-duplicate detection and network applications. The methods range from image, document, and data-point matching to distributed search, attack detection, and congestion monitoring.
5.12 Plagiarism/Near-Duplicate Detection
- For image and video-shot duplicates, [25] describes a hierarchical tiled color histogram with Euclidean similarity and a sparse visual-word approach using Min-Hash.The approaches use image retrieval or set overlap to identify matches.Source: §5.12 · pp. 15–16
- SimPair LSH incrementally detects near-duplicates by storing similar pairs; if one pair member shares a query bucket, it can avoid distance calculations for the pair.It is an in-memory index using Euclidean distance.Source: §5.12 · p. 15
- Probabilistic SimHash Matching [97] uses VOSH to flip bits without repetition and supports online in-memory or batch disk-based document matching.The operating mode depends on whether documents fit in main memory.Source: §5.12 · p. 16
- Copy-move forgery detection combines image blocks, PCA dimensionality reduction, K-Means clustering, and LSH to find candidate matching blocks [2].The image is divided into non-overlapping blocks before feature extraction.Source: §5.12 · p. 16
- A neural network extracts image features for near-duplicate detection, while load-balanced LSH maps them into balanced buckets and selects neighboring buckets.The method uses Euclidean distance.Source: §5.12 · p. 16
5.13 Networks
- In network applications, LSH supports semantic document search across mobile P2P nodes, DDoS detection using selected training data, and congestion detection through bucket overflow.The mobile-network approach stores hashed document keys on nodes and uses access points to route queries; the DDoS classifier is RAN-LSH [3].Source: §5.13 · p. 16
- NearBucket-LSH limits social-network similarity searches to buckets mapped from the query, drawing on Multi-probe LSH and Content Tree Locality-Sensitive Hashing.For SSDN congestion detection, bucket overflow indicates congestion; XGBoost is then used to determine its type.Source: §5.13 · p. 16
5.14 Sofware Testing
The section covers LSH applications in software testing, ontology matching, and social-media tasks. These applications use hashing for similar-state search, ontology alignment, profile similarity, and matching records across bibliographic databases.
5.14 Sofware Testing
- Tree Locality-Sensitive Hashing applies Min-Hash with tree edit distance to find similar symbolic-execution path-constraint states and help identify software bugs.Similar trees map to the same hash value.Source: §5.14 · p. 17
5.15 Ontology Matching
- For ontology matching, [26] represents class labels as merged shingles or tokens for Min-Hash alignment, while [27] combines LSH Forest with random-hyperplane hashing for angular distance.The former compares one ontology as the dataset and the other as the query.Source: §5.15 · p. 17
5.16 Social Media and Community Detection
- For social-media profiles, [28] uses vector-space representations and random-hyperplane hashing to build an index, then removes false positives to obtain exact matches.The cosine-distance method is implemented on Spark for distributed processing, and the authors report experimentally demonstrating benefits for similarity search.Source: §5.16 · p. 17
- Tag Assignments Stream Clustering builds user-interest vectors and uses LSH with angular distance to cluster similar users and update clusters as users arrive.Similarities between new users and current users are recalculated over time.Source: §5.16 · p. 17
- An LSH-based method matches papers between Web of Science and Scopus in reasonable time, then applies heuristic approaches [1].The supplied description does not specify the heuristics.Source: §5.16 · p. 17
5.17 Time Series
The section reviews LSH for time-series similarity, physiological-event prediction, and robotics. It includes multi-metric and collision-counting variants for physiological data, alongside feature hashing for localization and image correspondence.
5.17 Time Series
- For time-series nearest neighbors, one described approach uses Hamming-distance LSH and E2LSH, prunes candidates using original distances, and selects parameters through error analysis.Another uses QALSH with Dynamic Time Warping and Euclidean distance.Source: §5.17 · pp. 17–18
- For physiological time-series classification, the query label is chosen by majority vote among its nearest neighbors.LSH methods are also used to predict critical events from physiological time series.Source: §5.17 · p. 17
- Generic LSH for physiological time series is described as unable to use multiple distance metrics at once and as requiring costly candidate-distance calculations to remove false positives.The proposed Stratified LSH addresses the first issue with a hierarchy supporting different metrics at different levels; Collision Frequency LSH addresses the second by counting collisions across hash tables.Source: §5.17 · p. 17
- For seismic time series, [91] converts inputs into compact binary fingerprints and applies Min-Hash to identify similar fingerprints.The study also examines how multiple CPU threads affect processing time.Source: §5.17 · pp. 17–18
- For ICU vital-sign time series, [31] combines BSS and HSS autoencoder context vectors with Stratified LSH to reduce the cost of detecting acute hypotensive episodes.The encoders may be used separately or in combination before similar context vectors are found.Source: §5.17 · p. 18
5.18 Robotics
- In robotics, [101] improves the scalability of Monte Carlo Localization (MCL); E2LSH selects required features, and the incremental mapper hashes each new feature and adds its location to corresponding buckets.Source: §5.18 · p. 18
- For dense stereo-image correspondences in robotics, LSH is used to approximate one high-resolution image with another using dense binary pixel strings.Source: §5.18 · p. 18
6 CONCLUSIONS
The survey reviews recent LSH techniques by hash-function family, explains distributed LSH architectures, and categorizes application papers by how they use LSH.
6 CONCLUSIONS
- The survey categorizes recent LSH techniques by the hash-function families they use.Source: §6 · p. 18
- It reviews proposed distributed LSH frameworks and explains their architectures.Source: §6 · p. 18
- It categorizes application papers and describes how each uses LSH.Source: §6 · p. 18