Optimal Data-Dependent Hashing for Approximate Near Neighbors

By Alexandr Andoni, Ilya P. Razenshteyn. 2015

330 citations recorded by the source corpus.

We show an optimal data-dependent hashing scheme for the approximate near neighbor problem. For an n-point dataset in a d-dimensional space our data structure achieves query time O(d ⋅ nρ+o(1)) and space O(n1+ρ+o(1) + d ⋅ n), where ρ=1/(2c2-1) for the Euclidean space and approximation c>1. For the Hamming space, we obtain an exponent of ρ=1/(2c-1). Our result completes the direction set forth in (Andoni, Indyk, Nguyen, Razenshteyn 2014) who gave a proof-of-concept that data-dependent hashing can outperform classic Locality Sensitive Hashing (LSH). In contrast to (Andoni, Indyk, Nguyen, Razenshteyn 2014), the new bound is not only optimal, but in fact improves over the best (optimal) LSH data structures (Indyk, Motwani 1998) (Andoni, Indyk 2006) for all approximation factors c>1. From the technical perspective, we proceed by decomposing an arbitrary dataset into several subsets that are, in a certain sense, pseudo-random.

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

Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, methodology): “A new efficient LSH algorithm for cosine similarity data [51].”
Real-Time Open-Domain Question Answering with Dense-Sparse Phrase Index (2019, background): “Stronger empirical performance has been observed with a datadependent hashing function (Andoni and Razenshteyn, 2015) or k-means clustering for defining the cells.”
Practical and Optimal LSH for Angular Distance (2015, methodology): “Specifically, the hash functions match the theoretical guarantee of Spherical LSH from [2] and, when combined with additional techniques, give better experimental results than the hyperplane LSH.”
Deep Cross-Modal Hashing (2016, background): “…research community (Weiss et al., 2008; Raginsky & Lazebnik, 2009; Wang et al., 2010; Liu et al., 2011; Norouzi & Fleet, 2011; Norouzi et al., 2012; Rastegari et al., 2013; Yu et al., 2014; Liu et al., 2014; Shrivastava & Li, 2014; Andoni et al., 2015; Neyshabur & Srebro, 2015; Leng et al., 2015).”
The Faiss Library (2024, neutral): “In practice, algorithms based on random partitioning are signiﬁcantly outperformed by data-aware partitioning [20], [35].”
Handbook of Big Data (2016, background): “Instead of clicking, one can right-depress and drag the mouse across the blockplot with the eﬀect that horizontal and vertical strips are placed across all blocks touched by the drag motion.”
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0) (2016, background): “, [3]) or they do not support the Euclidean distance (e.”
Fast k-Nearest Neighbour Search via Prioritized DCI (2017, background): “Consequently, various data-dependent hashing schemes have been proposed (Paulevé et al., 2010; Weiss et al., 2009; Andoni & Razenshteyn, 2015); unlike data-independent hashing schemes, however, they do not allow dynamic updates to the dataset.”
Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time (2023, background): “…the Approximate Nearest Neighbor ( ANN ) problem (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) as: Definition J.1 (Approximate…”