Practical and Optimal LSH for Angular Distance

By Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, Ludwig Schmidt. 2015

555 citations recorded by the source corpus.

We show the existence of a Locality-Sensitive Hashing (LSH) family for the angular distance that yields an approximate Near Neighbor Search algorithm with the asymptotically optimal running time exponent. Unlike earlier algorithms with this property (e.g., Spherical LSH [1, 2]), our algorithm is also practical, improving upon the well-studied hyperplane LSH [3] in practice. We also introduce a multiprobe version of this algorithm and conduct an experimental evaluation on real and synthetic data sets. We complement the above positive results with a fine-grained lower bound for the quality of any LSH family for angular distance. Our lower bound implies that the above LSH family exhibits a trade-off between evaluation time and quality that is close to optimal for a natural class of LSH functions.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, 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 Aerospace Engineering

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

Citations in the corpus

Reformer: The Efficient Transformer (2020, methodology): “This method is a known LSH scheme (Andoni et al., 2015) and is easy to implement and apply to batches of vectors.”
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, neutral): “It was shown that proximity graph approaches with such approximation perform competitive to other k-ANNS thechniques, such as kd-trees or LSH [18-26].”
Mitigating Sybils in Federated Learning Poisoning (2018, methodology): “Our Python prototype is not optimized and there are known optimizations to improve the speed of computing angular distance at scale [1].”
Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep Learning (2018, neutral): “[80] to efficiently perform the lookup of”
ETC: Encoding Long and Structured Inputs in Transformers (2020, methodology): “The Reformer (Kitaev et al., 2020) model ﬁnds the nearest neighbors of the attention query (those input tokens that would result in the highest attention weights) using locality sensing hashing (Andoni et al., 2015) and only uses those for attention.”
Orthogonal Random Features (2016, methodology): “We note that the HD 1 HD 2 HD 3 structure has also been recently used in fast cross-polytope LSH [2, 13, 7].”
End-to-End Training of Neural Retrievers for Open-Domain Question Answering (2021, methodology): “We therefore did not optimize or approximate the similarity search using LSH (Andoni et al., 2015) or efﬁcient maximum inner product search (Shrivastava and Li, 2014).”
Differentiable Reasoning over a Virtual Knowledge Base (2020, methodology): “The weights of the entities in Y are differentiable w.r.t the MIPS queries, which allows end-to-end learning without any intermediate supervision.”
ETC: Encoding Long and Structured Data in Transformers (2020, methodology): “, 2020) model assumes that the result of attention will be dominated by those tokens with higher attention weights, so they reduce computational cost by calculating the nearest neighbors to the attention query (those input tokens that would result in the highest attention weight) using locality sens”
Accelerating Large-Scale Inference with Anisotropic Vector Quantization (2019, unknown): “Locality sensitive hashing (Shrivastava & Li, 2014; Neyshabur & Srebro, 2015; Indyk & Motwani, 1998; Andoni et al., 2015) partitions the space using a similarity-preserving hash function.”
Multiscale Quantization for Fast Similarity Search (2017, methodology): “Tree based methods [7, 29, 9], graph based methods [16] and locality sensitive hashing style algorithms [19, 1, 32] focus on non-exhaustive search by partitioning the search space.”
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0) (2016, unknown): “There are two recent NNS benchmark studies: [34] and ann-benchmark [8].”
Scatterbrain: Unifying Sparse and Low-rank Attention Approximation (2021, background): “, by The sparse matrix S typically has support determined randomly [16] LSH [22, 36], or by clustering [53].”
Unifying Orthogonal Monte Carlo Methods (2019, methodology): “These matrices X T (typically with T ∈ { 1 , 2 , 3 } ) have been used recently in the context of dimensionality reduction (Choromanski et al., 2017) (see also (Ailon & Chazelle, 2009)), kernel approximation (Yu et al., 2016), and locality-sensitive hashing (Andoni et al., 2015).”
Orthogonal Estimation of Wasserstein Distances (2019, methodology): “These random matrices have been used as computationally cheap alternatives to exact sampling from UnifOrt( S d − 1 ; d ) in a variety of applications recently; see e.g. (Choromanski et al., 2017; Andoni et al., 2015).”
The Limitations of Federated Learning in Sybil Settings (2020, methodology): “Our Python prototype is not optimized and there are known optimizations to improve the speed of computing angular distance at scale [2].”
The Geometry of Random Features (2018, background): “…in very special scenarios such as Gaussian kernel approximation in the regime of high data dimensionality (Yu et al., 2016), dimensionality reduction with modified JohnsonLindenstrauss transform, angular kernel approximation (Choromanski et al., 2017) and cross-polytope LSH (Andoni et al., 2015).”
Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time (2023, methodology): “…definition of approximate nearest neighbor search is very standard in literature (Arya & Mount, 1993; Indyk & Motwani, 1998a; Datar et al., 2004; Andoni et al., 2014; 2015; Andoni & Razenshteyn, 2015; Indyk & Wagner, 2018; Andoni et al., 2017; 2018; Dong et al., 2019; Chen et al., 2020b; Li &…”