Similarity Search in High Dimensions via Hashing

By Aristides Gionis, Piotr Indyk, Rajeev Motwani. 1999

Subfields: Information Retrieval & Search

How researchers see this paper

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

In Information Retrieval & Search

Citations in the corpus

Real-Time Open-Domain Question Answering with Dense-Sparse Phrase Index (2019, background): “In metric space (L1 or L2), one of the most classic search algorithms is Locality-Sensitive Hashing (LSH) (Gionis et al., 1999), which uses a data-independent hashing function to map nearby vectors to the same cell.”
Pretrained Transformers for Text Ranking: BERT and Beyond (2020, methodology): “ ˚usually has no measurable impact on end-user perceptions of quality. The earliest solutions to approximate nearest neighbor search were based on locality-sensitive hashing [Indyk and Motwani, 1998, Gionis et al., 1999, Bawa et al., 2005], but proximity graph methods methods are generally acknowled”
The Arcade Learning Environment: An Evaluation Platform for General Agents (2012, methodology): “Such methods include polynomial bases (Schweitzer & Seidmann, 1985), sparse distributed memories (Kanerva, 1988) and locality sensitive hashing (LSH) (Gionis et al., 1999).”
Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep Learning (2018, background): “locality-sensitive hashing [81], [82] to find nearest neighbors according to the cosine similarity between vectors.”
A practical tutorial on autoencoders for nonlinear feature fusion: Taxonomy, models, software and guidelines (2018, background): “A special family of hash functions are those known as Locality Sensitive Hashing (LSH) [131].”
Privacy via the Johnson-Lindenstrauss Transform (2012, background): “We consider Euclidean ( ℓ 2 ) distance between users as the distance measure we aim to preserve, as it is a natural choice for similarity search in high dimensions [15].”
Scatterbrain: Unifying Sparse and Low-rank Attention Approximation (2021, background): “Locality Sensitive Hashing (LSH) has been well-studied in approximate nearest-neighbor search [2, 11, 27, 30, 34, 54].”
Structure-Preserving Binary Representations for RGB-D Action Recognition (2016, methodology): “In our experiments, we compare the proposed method against seven general hashing algorithms including KSH [58], BRE [60], MLH [61], LSH [56], SpH [57], AGH [68], PCAH [69], BSSC [53] and RBM [70].”
Leveraging Intra-User and Inter-User Representation Learning for Automated Hate Speech Detection (2018, methodology): “We collect similar Tweets from large unlabeled Tweet set U by Locality Sensitive Hashing (LSH) (Indyk and Motwani, 1998; Gionis et al., 1999).”
Binary Stochastic Representations for Large Multi-class Classification (2017, background): “Hashing algorithms can be divided in two categories: Local Sensitive Hashing which use random projections of the data [12,13], and learning to hash algorithms which are data-driven, optimizing a loss function to preserve similarities [14,15,16].”
Deep Supervised Hashing for Fast Image Retrieval (2016, methodology): “LSH [4] 0.”
LOCI: fast outlier detection using the local correlation integral (2003, methodology): “This is not a restrictive hypothesis, since it is well-known that, in practice, there are no clear advantages of one particular norm over another [10, 11].”
Inductive Hashing on Manifolds (2013, background): “As in LSH, the methods aim to identify a set of hyperplanes, but now these hyperplanes are learned, rather than randomly selected.”
External memory algorithms and data structures: dealing with massive data (2001, background): “1998a; 2000] and locality-sensitive hashing [Gionis et al. 1999].”
Getting the look: clothing recognition and segmentation for automatic product suggestions in everyday photos (2013, methodology): “Since speed is an issue, we represent the segments as binary vectors and use a multi-probe locality-sensitive hashing (LSH) index to get promising matches sublinearly [6].”