Optimal Data-Dependent Hashing for Approximate Near Neighbors

Alexandr Andoni; Ilya Razenshteyn

Source-linked AI summary

Optimal Data-Dependent Hashing for Approximate Near Neighbors

Alexandr Andoni, Ilya Razenshteyn

arXiv:1501.01062v3Jan 6, 2015cs.DS

TL;DR

Approximate near neighbor search seeks efficient data structures for returning a c-approximate neighbor, but classical LSH has settled exponent limits. The paper develops data-dependent hashing by decomposing arbitrary datasets into pseudo-random subsets. It achieves optimal exponents ρ = 1/(2c^2−1) in Euclidean space and ρ = 1/(2c−1) in Hamming space, improving over optimal LSH bounds for all c > 1.

Problem
The paper asks whether data-dependent hashing can achieve a better exponent than classical LSH for approximate near neighbor search on worst-case datasets.
Method
The method decomposes an arbitrary dataset into subsets that are, in a certain sense, pseudo-random, reducing the problem to an essentially random dataset.
Results
The data structure achieves query time O(d n^{ρ+o(1)}) and space O(n^{1+ρ+o(1)} + dn), with ρ = 1/(2c^2−1) for Euclidean space and ρ = 1/(2c−1) for Hamming space.
Takeaways & Limitations
The new bounds are optimal and improve over the best optimal LSH data structures for every approximation factor c > 1.
Takeaways & Limitations
Further improvement would require improving the random-dataset case, which appears to require fundamentally different techniques, if possible at all.

Abstract

from arXiv · show

We show an optimal data-dependent hashing scheme for the approximate near neighbor problem. For an $n$-point data set in a $d$-dimensional space our data structure achieves query time $O(d n^{ρ+o(1)})$ and space $O(n^{1+ρ+o(1)} + dn)$, where $ρ=\tfrac{1}{2c^2-1}$ for the Euclidean space and approximation $c>1$. For the Hamming space, we obtain an exponent of $ρ=\tfrac{1}{2c-1}$. Our result completes the direction set forth in [AINR14] who gave a proof-of-concept that data-dependent hashing can outperform classical Locality Sensitive Hashing (LSH). In contrast to [AINR14], the new bound is not only optimal, but in fact improves over the best (optimal) LSH data structures [IM98,AI06] 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.

1 Introduction

The paper develops optimal data-dependent hashing for approximate near neighbors, improving on classical LSH bounds in Euclidean and Hamming spaces while addressing worst-case datasets. Its structure decomposes arbitrary datasets into pseudo-random subsets and achieves efficient query, space, and preprocessing bounds.

Problem: ANN seeks a data structure that reports a point within distance cr whenever a point exists within distance r, with applications across several fields.The problem is motivated by databases, data mining, information retrieval, computer vision, computational geometry, and signal processing.
Classical hashing: LSH uses hash functions with higher collision probability for near than far points, yielding n^1+ρ extra space and dn^ρ query time, where ρ = log(1/p1)/log(1/p2).The construction hashes the query and retrieves points in buckets containing it.
Motivation: ρ = 1/c^2 was the settled optimal LSH exponent for Euclidean space before data-dependent hashing improved beyond the LSH framework.Earlier work established this exponent as both achievable and tight for classical LSH.
Motivation: Data-dependent hashing makes the randomized hash family depend on the dataset and had already achieved ρ = 7/8^c3 while improving over classical LSH on worst-case datasets.The paper asks for the best possible exponent under efficiently describable hash families.
Main result: For Euclidean ANN, the theorem gives O(d · n^ρ+o(1)) query time, O(n^1+ρ+o(1) + d · n) space, and O(d · n^1+ρ+o(1)) preprocessing time, with ρ = 1/(2c^2−1).The result applies for fixed approximation c > 1 and threshold r > 0.
Techniques: The method reduces a generic dataset to an essentially random dataset by decomposing it into pseudo-random subsets, while addressing preprocessing waste and replication.The analysis also goes beyond pairwise reasoning in the study of LSH.
Extensions and advantages: For Hamming space, the algorithm achieves ρ = 1/(2c−1), improving over classical LSH for every c and remaining optimal.The paper also states that preprocessing is near-linear in the space used, rather than quadratic as in [AINR14].

2 Preliminaries

The preliminaries define approximate near neighbor search and locality-sensitive partitions, then state the standard reduction from collision probabilities to an ANN data structure.

ANN requires reporting a point within distance cr whenever a query has a data point within distance r, with failure probability f.
A partition is (r1, r2, p1, p2)-sensitive when nearby points collide with probability at least p1 and distant points collide with probability at most p2.
Theorem 2.3 converts such partitions with ρ = ln(1/p1) / ln(1/p2) into an ANN structure under efficient sampling, storage, and point-location assumptions.
84: amplification yields O(dn^ρ+o(1)) query time, O(dn + n^1+ρ+o(1)) space, and O(dn^1+ρ+o(1)) preprocessing time.
The Euclidean LSH scheme used later provides partitions whose collision behavior depends exponentially on interpoint distance, with polynomial-dimensional sampling and point location.

3 Spherical LSH

Spherical LSH partitions the unit sphere into spherical caps and supplies collision and three-point properties that support the paper’s random-instance ANN bound.

Spherical LSH partitions the unit sphere by repeatedly carving spherical caps using Gaussian directions.
For random instances, combining Spherical LSH with Theorem 2.3 gives ρ ≤ 1/(2c^2−1) + o_c(1), achieving the desired bound.
The initial partitioning scheme is not efficient because computing the currently covered region and potentially continuing indefinitely are problematic.
Theorem 3.1 bounds pairwise collision probabilities for points at distances below or above τ by expressions governed by τ^2.
Theorem 3.1 additionally establishes a three-point conditional collision property, the new contribution beyond earlier Spherical LSH analysis.
The three-point analysis uses near-orthogonality of relevant directions to obtain almost-independent Gaussian events when the corresponding points are sufficiently separated.

4 The data structure

The data structure recursively decomposes arbitrary datasets into dense and pseudo-random components, reducing each component toward spherical instances where Spherical LSH applies.

The construction first achieves success probability n^−ρ, query time n^o_c(1), and near-linear space and preprocessing, then amplifies success to 0.99 using O(n^ρ+o_c(1)) copies.
4.1 Overview: A dataset is decomposed into dense components covered by small spherical caps and a pseudo-random component lacking large dense subsets.
4.1 Overview: Dense components are enclosed in smaller-radius balls and processed recursively, while the pseudo-random component is partitioned with Spherical LSH and recursion continues on nonempty parts.
4.1 Overview: Dense-cluster recursion shrinks the sphere radius by (1−Θ(ε^2)), reaching the easy regime R ≤ c/2 after O_c(1/ε^2) iterations.
4.2 Formal description: Ball instances are discretized into thin annuli treated as spheres, with distance rounding changing pairwise distances by at most 2δ.

5 Analysis of the data structure

The analysis establishes the data structure’s collision exponent, success probability, recursion invariants, and expected space and query-time bounds. It uses empirical collision estimates on pseudo-random remainders and auxiliary shrinking arguments to control the recursive process.

Proof strategy: The adaptive analysis uses an empirical estimate of the remaining points colliding with the query, rather than only far-point collision probabilities.Conditioning on the near neighbor’s collision is required, and pseudo-randomness eventually needs renewed dense-ball checks.
Collision analysis: ρ ≤ 1/(2c^2−1) + o_c(1) follows from the collision analysis for partitions applied to pseudo-random remainders.The partition quality satisfies ln(1/p1)/ln(1/p2) ≤ 1/(2c^2−1) + o_c(1).
Recursion control: O_c(1/ε^6) bounds the number of ProcessBall invocations in the recursion stack at any moment.The proof combines bounds on shrinking calls with the growth of the auxiliary quantity ξ.
Process behavior: O(log n) Process or ProcessSphere calls suffice with high probability for a point to be captured by a dense cluster or become the only remaining point.
Collision analysis: n^(−1/(2c^2−1)−o_c(1)) is the lower bound on success probability for a near pair.Claim 5.6 applies when ||p−q||≤1.

6 Fast preprocessing

The preprocessing is first reduced to n^(2+o_c(1)) time and then to n^(1+o_c(1)) time by restricting cluster searches and estimating dense balls from samples.

Quadratic preprocessing: n^(2+o_c(1)) preprocessing time is obtained by reducing each clustering step to near-quadratic time.Each point participates in n^(o_c(1)) clustering instances, while partition sampling costs n^(o_c(1)) time.
Spherical clustering: The van der Corput lemma supports searching for spherical clusters whose centers are data points without losing the required radius guarantee.ProcessSphere cannot afford a factor-of-two radius loss, making this case more delicate.
Spherical clustering: A nontrivially small spherical cap covering n points has a data-point-centered cap covering a substantial fraction of them.This permits cluster searches centered only at points from P while preserving the analysis.
Near-linear preprocessing: n^(1+o_c(1)) preprocessing time is obtained by sampling the dataset to compute dense balls.The sample is accurate with probability at least 1−n^−10 using the O(d) VC-dimension of balls in R^d.

A Analysis of Spherical LSH

This appendix section introduces a basic estimate used repeatedly in the analysis and includes the geometric region associated with the spherical LSH construction.

Auxiliary estimates: The appendix repeatedly invokes Lemma A.1 as a basic estimate.
Geometric region: Figure 5 depicts the region defined by X≥d^(1/4) and X cos α−Y sin α≥d^(1/4).

A.1 Collision probability for a pair

The collision probability for a pair is reduced to a two-dimensional Gaussian-region calculation. The analysis establishes monotonicity and approximation properties for this probability across angular regimes.

Collision probability: Pr_R[R(u)=R(v)] is analyzed as the probability that both points are captured, conditioned on either point being captured in one iteration.Gaussian spherical symmetry supplies the corresponding probability calculation.
Gaussian reduction: W_{α,λ}={(x,y):x≥λ and x cos α−y sin α≥λ} is the planar region used to compute the collision probability.The relevant Gaussian measure is that of W_{α,d^(1/4)}.
Collision probability: S(d,α) is non-increasing in α.
Gaussian approximation: S(d,α) is compared with its independent-Gaussian approximation eS(d,α) over angular ranges bounded away from 0 and π.The proof treats α<π/2 and α>π/2 separately, with α=π/2 immediate.
Gaussian approximation: The Gaussian calculation uses independence of X and Y and the intersection geometry shown in Figure 5.The intersection coordinate is y0=−d^(1/4) tan α.
Conclusion: The spherical LSH analysis yields the first two bullet points of Theorem 3.1.

A.2 Three-way collision probabilities

The section proves claim (4) by first treating the simpler case ε = 0.

The proof begins with the simpler case ε = 0.
This section is devoted to proving claim (4).
The ε = 0 case serves as the starting point of the section’s proof.

A.2.1 The case ε = 0

For ε = 0, the proof analyzes three points on the sphere through Gaussian collision events and combines the resulting bounds with Lemma A.1.

The argument considers u, v, and w on S^{d−1}, with ||u−v|| = τ and τ ≤ 1.99.
The proof extends the two-point analysis to three-point collision probabilities.
Spherical Gaussian symmetry and an immediate identity justify intermediate steps in the probability calculation.
Independence of X, Y, and Z, together with (16), supplies the remaining step.
Combining the derived inequality with Lemma A.1 gives the desired claim.

A.2.2 The case of arbitrary ε

For arbitrary ε, the proof separates the small-τ regime from the general case, uses spherical Gaussian symmetry and covariance comparison, and concludes by combining the resulting bounds.

Combining inequalities (19), (20), and (21) completes the small-τ case.
For τ ≤ εν, the proof lower-bounds the three-way collision probability by the corresponding two-point collision probability.
When τ ≥ εν, spherical Gaussian symmetry reduces the analysis to points in S^2 with matching distances from w′.
The two-point collision probability is preserved under the replacement of u, v by u′, v′ because their mutual distance is unchanged.
The three-way collision comparison incurs an additive error of ε^{Ω(ν)} + d^{−Ω(1)}.
The general case uses nondegenerate covariance matrices, Gaussian probabilities over T, and bounds from Sections A.2.1 and B.
Combining (25) and (26) finishes the argument, with the Section A.2.1 bound stable under small ε perturbations.

A.3 Efficiency

The partitioning scheme is made efficient by stopping after a fixed number of iterations, while choosing the cutoff so the omitted event has probability below e^{−d100}.

The original partitioning scheme is inefficient because it checks whether S_R ≠ S^{d−1}.
The implementation instead stops after T iterations.
The analysis invokes Gaussian 2-stability and Lemma A.1.
A sufficiently fine ε-net and a union bound yield the desired conclusion and the time and space bounds.

B Perturbed Gaussian measures

This section considers centered Gaussian measures with covariance matrix A and studies how perturbing A affects related matrix quantities. Under a lower spectral bound on A, the perturbation propagates to A^-1 and A^-1/2 with controlled spectral closeness.

A centered d-variate Gaussian N(0, A) is considered with covariance matrix A, together with a closed convex set S ⊆ R^d.
The argument uses multivariate Gaussian properties, spherical symmetry of N(0, I), and convexity of S and A^-1/2S.
When A ⪰ λI and ||B − A|| ≤ ε, the matrices A and B are O(ε/λ)-spectrally close.
A^-1 and B^-1 are O(ε/λ)-spectrally close under the same perturbation conditions.
A^-1/2 and B^-1/2 are likewise O(ε/λ)-spectrally close.