LSH forest: self-tuning indexes for similarity search

By Mayank Bawa, Tyson Condie, Prasanna Ganesan. 2005

434 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search, Signal Processing

How researchers see this paper

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

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

In Signal Processing

Citations in the corpus

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (2016, methodology): “We used the LSHForest [2] on the learned word2vec embedding.”
Scaling Memory-Augmented Neural Networks with Sparse Reads and Writes (2016, positive): “An alternative approach which may be well-suited is LSH forests [3], which adaptively modifies the number of hashes used.”
Fast GPU-based locality sensitive hashing for k-nearest neighbor computation (2011, methodology): “LSH-forest [3] avoids tuning of the parameter M by representing the hash table as a preﬁx tree and the parameter M is computed based on the depth of the corresponding preﬁx-tree leaf node.”
Semi-Supervised Hashing for Large-Scale Search (2012, methodology): “For instance, a selftuning indexing technique, called LSH forest was proposed in [25], which aims at improving the performance without additional storage and query overhead.”
Locally Private k-Means in One Round (2021, background): “In this sense, our tree bears a strong resemblance to the so-called LSH forests (Bawa et al., 2005; Andoni et al., 2017).”
Scalable phylogenetic profiling using MinHash uncovers likely eukaryotic sexual reproduction genes (2019, methodology): “underpinning weighted minhashing and locality sensitive hashing forest algorithms and their implementation are described in earlier papers [61,72,73].”
Hashing for Similarity Search: A Survey (2014, methodology): “LSH forest [9] represents each hash table, built from LSH, using a tree, by pruning subtrees (nodes) that do not contain any database points and also restricting the depth of each leaf node not larger than a threshold.”
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].”
Rapid object indexing using locality sensitive hashing and joint 3D-signature space estimation (2006, background): “proposed recently the LSH forest [2] which was shown by the authors to improve the retrieval performance on skewed data distributions without the need to retune the algorithm.”
Collaborative Metric Learning (2017, neutral): “We provide a comparison in Section 4.4.”
Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search (2007, methodology): “Bawa et al . proposed the LSH Forest indexing method [3] which represents each hash table by a preﬁx tree so the number of hash functions per table can be adapted for diﬀerent approximation distances.”
Seeping Semantics: Linking Datasets Using Word Embeddings for Data Discovery (2018, methodology): “This approach uses LSHForest [27] and indexes the source elements twice.”
Learning to Hash for Indexing Big Data—A Survey (2015, methodology): “By converting rank lists to a triplet tensor matrix, listwise hashing is designed to preserve the ranking in the Hamming space [76].”
Scalable Nearest Neighbor Algorithms for High Dimensional Data (2014, positive): “number of hash tables, and LSH Forest [31] adapts better to the data without requiring hand tuning of parameters.”