Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions

By Alexandr Andoni, Piotr Indyk. 2006

2,626 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

Learning Dense Representations for Entity Retrieval (2019, background): “Approximate nearest neighbor search is its own sub-field of study (Andoni and Indyk, 2008).”
Quantization based Fast Inner Product Search (2015, methodology): “The proposed hash function followed L2LSH form [1]: h i (x̂) = b T i x̂+bi r c, where Pi is a (d+m)-dimensional vector whose entries are sampled i.”
Graph Convolutional Neural Networks for Web-Scale Recommender Systems (2018, methodology): “Approximate KNN can be obtained efficiently via locality sensitive hashing [2].”
Learning to Remember Rare Events (2017, background): “LSH is a hashing scheme so that near neighbors get similar hashes (Indyk & Motwani, 1998; Andoni & Indyk, 2006).”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, background): “There has been substantial progress in designing LSH functions for various measures and understanding their limitations, see [AI08] for an overview.”
#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning (2016, neutral): “LSH is a popular class of hash functions for querying nearest neighbors based on certain similarity metrics [2].”
Scalable phylogenetic profiling using MinHash uncovers likely eukaryotic sexual reproduction genes (2019, neutral): “underpinning weighted minhashing and locality sensitive hashing forest algorithms and their implementation are described in earlier papers [61,72,73].”
K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes (2013, methodology): “We follow the search strategy of Hamming ranking commonly adopted in many hashing methods [1, 31, 29, 19, 5, 6].”
Inter-media hashing for large-scale retrieval from heterogeneous data sources (2013, methodology): “A typical LSH function is depicted as below: h (x)=sgnw T x + b, where w is a random hyperplane, which is usually constructed by sampling each component from a p-stable distribution, e.g., standard Gaussian distribution, and b is a random threshold.”
Optimized Product Quantization for Approximate Nearest Neighbor Search (2013, methodology): “…efficient nearest neighbor search on large-scale datasets, taking only a fraction of a second for each nearest neighbor query [18, 10] Hashing [1, 18, 20, 19, 6, 8] has been a popular approach to compact encoding, where the similarity between two data points is approximated by the Hamming distance…”
Efficient Interaction-based Neural Ranking with Locality Sensitive Hashing (2019, methodology): “Our work is motivated by the rich history of research on approximation with hashing such as LSH [1–4, 7, 8, 13, 15, 37] and in various data-intensive applications [6, 10, 17, 18, 30].”
Retrieve Fast, Rerank Smart: Cooperative and Joint Approaches for Improved Cross-Modal Retrieval (2021, methodology): “This enables cross-modal retrieval, where standard distance metrics are used to identify the most similar examples for each query in the target data collection via standard nearest-neighbor search [3, 4, 29, 35, 2, 20].”
Fast search in Hamming space with multi-index hashing (2012, methodology): “In all cases, for 64 and 128-bit codes, and for hash functions based on LSH [2] and MLH [16], there is a substantial variance in the search radius.”
Deep hashing for compact binary codes learning (2015, methodology): “Recall @ í µí± = 1000 16 32 64 PCA-ITQ [6] 31.29 34.54 37.97 KMH [8] 30.58 32.65 34.31 Spherical [9] 26.51 29.96 35.04 SH [36] 22.04 24.09 24.28 PCAH [34] 23.11 20.06 18.49 LSH [1] 28.”
Speeding up the Xbox recommender system using a euclidean transformation for inner-product spaces (2014, methodology): “The results indicate that treebased approaches are superior to an LSH based approach (except when the required speedup is very small).”