Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search

By Qin Lv, William K. Josephson, Zhe Wang, Moses Charikar, Kai Li. Very Large Data Bases Conference, 2007

906 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/9ed960374381062d85d3944182a539c1d00f7703

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Benchmarking modern multiprocessors (2011, methodology): “The middle four stages are for query image segmentation, feature extraction, indexing of candidate sets with multi-probe Locality Sensitive Hashing (LSH) [60] and ranking.”
Aurum: A Data Discovery System (2018, background): “Although in our deployments storage overhead is not a problem, there are alternative LSH indexes which help with reducing such overhead, such as LSHForest [5] and MultiProbe-LSH [6].”
Distributed Representations of Tuples for Entity Resolution (2017, background): “It has been shown that this approach often requires substantially less number of hash tables (as much as 20x) than a traditional approach [36].”
Scalable Nearest Neighbor Algorithms for High Dimensional Data (2014, background): “Comparison between the hierarchical clustering index and LSH for the Nister/Stewenius recognition benchmark images data set of about 5 million features.”
Fast locality-sensitive hashing (2011, background): “[27] designed a careful probing heuristic to look up multiple buckets that have a high probability of containing the nearest neighbors of a query.”
GPU accelerated t-distributed stochastic neighbor embedding (2019, methodology): “In cases where we have very few points, or are operating in low dimension, tsnecuda defaults to a base approximate nearest neighbor structure: an inverted index based on locality sensitive hashing (LSH) with multi-probing [46].”
Practical and Optimal LSH for Angular Distance (2015, methodology): “Once we have estimated the probabilities for each vi ∈ [d], we incrementally construct the probing sequence using a binary heap, similar to the approach in [14].”
Learning to Prune in Metric and Non-Metric Spaces (2013, background): “proposed a multi-probe version of the LSH, which can query multiple buckets of the same hash table [22].”
Learning to Hash for Indexing Big Data—A Survey (2015, methodology): “Based on the random projection scheme, there have been several efforts to improve the performance of the LSH method [37] [39] [41].”
The PARSEC benchmark suite: Characterization and architectural implications (2008, methodology): “The middle four stages are for query image segmentation, feature extraction, indexing of candidate sets with multi-probe Locality Sensitive Hashing (LSH)[28] and ranking.”
Semi-Supervised Hashing for Large-Scale Search (2012, methodology): “In [25], a technique called MultiProbe LSH was developed to reduce the number of required hash tables through intelligently probing multiple buckets in each hash table.”
A Survey on Learning to Hash (2016, background): “Following the pioneering works [14], [44], there are a lot of efforts, such as proposing random hash functions satisfying the locality sensitivity property for various distance measures [10], [11], [14], [19], [20], [100], [111], proving better search efficiency and accuracy [19], [113], developing ”
Fast Matching of Binary Features (2012, methodology): “In figure 7 we compare the hierarchical clustering tree with a multi-probe locality sensitive hashing implementation [19], also available in FLANN.”
ORB: An efficient alternative to SIFT or SURF (2011, methodology): “We use multi-probe LSH [18] which improves on the traditional LSH by looking at neighboring buckets in which a query descriptor falls.”
Scalable Mutual Information Estimation Using Dependence Graphs (2018, methodology): “LSH-based methods have previously been used for KNN search and graph constructions problems [14, 15], and they result in fast and low complexity algorithms.”
Efficient Similarity Search over Encrypted Data (2012, methodology): “In our scheme, we propose to utilize it in the context of the encrypted data.”