Source-linked AI summary
Beyond Locality-Sensitive Hashing
Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya Razenshteyn
TL;DR
The paper seeks faster approximate near neighbor search than standard LSH bounds permit. It introduces a data-aware two-level hashing structure combining bounded-diameter bucketing with improved inner hashing, achieving the first stated improvements over prior Euclidean and ℓ1 results while retaining explicit query-time and space bounds.
Problem
Approximate near neighbor search in high-dimensional Euclidean space has standard LSH bounds whose running time cannot be improved within the simple LSH-based framework.
Method
The method combines an outer data partition into bounded-diameter buckets with an inner bucket-specific Gaussian hash structure centered using the bucket’s geometry.
Results
7/(8c^2) + O(1/c^3) + o(1) bounds ρ for ℓ2, with query time O(n^ρ + d log n) and space O(n^{1+ρ} + d log n), while the ℓ1 reduction gives ρ ≤ 7/(8c) + O(1/c^{3/2}) + o(1).
Takeaways & Limitations
The results are the first improvements over the cited Andoni–Indyk and Indyk–Motwani bounds and bypass the cited locality-sensitive hashing lower bound through data-aware hashing.
Takeaways & Limitations
The two-level intuition is not fully rigorous because it does not properly condition on all buckets having low diameter; the paper analyzes a similar scheme rigorously.
Abstract
from arXiv · showhide
We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in R^d, our algorithm achieves O(n^ρ + d log n) query time and O(n^{1 + ρ} + d log n) space, where ρ<= 7/(8c^2) + O(1 / c^3) + o(1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). By a standard reduction we obtain a data structure for the Hamming space and \ell_1 norm with ρ<= 7/(8c) + O(1/c^{3/2}) + o(1), which is the first improvement over the result of Indyk and Motwani (STOC 1998).
1 Introduction
The paper addresses approximate near neighbor search, where high-dimensional exact methods suffer from the curse of dimensionality. It improves prior LSH-based bounds through a data-aware two-level hashing algorithm.
- Motivation: ANN permits returning a point within distance cr when a point within distance r exists, trading approximation for improved high-dimensional search.The problem is important in databases, data mining, information retrieval, computer vision, and signal processing.
- Prior approach: LSH achieves near-neighbor retrieval by making close pairs collide more often than far pairs, with exponent ρ = log(1/p1)/log(1/p2).Its standard construction uses n^{1+ρ+o(1)} extra space and dn^{ρ+o(1)} query time.
- Prior approach: The standard LSH exponent reaches ρ = 1/c for ℓ1 and ρ = 1/c^2 + o_c(1) for ℓ2, with matching lower bounds preventing improvement within that framework.The paper targets an improvement beyond this LSH limitation.
- Results: 7/(8c^2) + O(1/c^3) + o(1) bounds the Euclidean exponent ρ, while the reduction gives 7/(8c) + O(1/c^{3/2}) + o(1) for ℓ1.These constitute the first improvements over the cited prior results.
- Approach: The algorithm combines an outer hash partition into bounded-diameter buckets with an inner, bucket-specific hash structure centered at each bucket’s minimum enclosing ball.Because inner functions depend on the data and bucket centers, the resulting two-level hashes cannot be unwrapped into a standard data-independent LSH family.
- Intuition: For bounded-diameter Hamming instances, min-wise hashing produces a collision-probability gap that yields ρ lower than 1/c.This intuition motivates the use of improved hashing after shrinking bucket diameters.
2 Preliminaries
The preliminaries define ANN and locality-sensitive hashing, then state the standard reduction from sensitive hash families to ANN data structures and the prior Euclidean baseline.
- Definitions: ANN with failure probability f must report a point within cr whenever a point within r exists, with probability at least 1 − f.The definition applies to a metric space (X, D).
- Guarantees: The framework allows randomized preprocessing and query phases, with success probability measured over both sources of randomness.The data structure’s failure probability can be made an arbitrarily small constant.
- Definitions: An (r1, r2, p1, p2)-sensitive hash family gives higher collision probability p1 for pairs within r1 than p2 for pairs beyond r2.Useful families require r1 < r2 and p1 > p2.
- Hashing framework: Combining k independent hashes maps each point to a tuple and changes the collision probabilities to p1^k and p2^k.This construction is denoted H⊗k.
- Hashing framework: The standard reduction sets ρ = ln(1/p1)/ln(1/p2) and obtains ANN query work proportional to O(n^ρ/p1) distance computations.The query also performs O(n^ρ/p1 · ⌈log1/p2 n⌉) hash evaluations or other operations.
- Baseline: The baseline Euclidean construction has preprocessing time and space O_c(n^{1+1/c^2+o_c(1)} + nd) and query time O_c(dn^{1/c^2+o_c(1)}).The norm notation ∥·∥ denotes the ℓ2 norm in the paper.
3 Gaussian LSH
The Gaussian LSH construction improves hashing for points on a bounded-width spherical shell, then supplies a practical family whose quality remains valid after normalization.
- Construction: The Gaussian LSH family improves the Andoni–Indyk exponent for ℓ2 when points and queries lie on a spherical shell of radius O(c) and width O(1).The construction is similar to an SDP rounding scheme.
- Idealized family: The idealized construction assumes all points lie on a sphere of radius O(c), without accounting for time and space complexity.Its parameters are later converted into a real family.
- Construction: Gaussian partitioning samples Gaussian vectors and builds parts until their union covers the target spherical shell, defining the hash by the part containing each point.The procedure uses a parameter ε satisfying ε = o(1) and ε = ω(d^-1/2).
- Analysis: The collision-probability estimates yield p1 = exp(−o_{c,ν}(d)); a comparable p2 estimate holds when η is separated from 1/2.The analysis requires c to be sufficiently large so the relevant angle remains below π/2.
- Caveat: The stated O_ν(1/c^3) term is looser than the O_ν(1/c^4) term available in an intermediate expression, for consistency with the next theorem.This is a presentation choice in the theorem statement.
- Real family: The real family preserves the conclusion of the idealized theorem after normalizing vectors before hashing.Functions can be sampled, stored, and queried in exp(o(d)) time or space for every k.
4 Two-level hashing
The data structure combines an outer LSH partition that bounds bucket diameters with an inner, bucket-specific LSH scheme that exploits this improved geometry. Independent copies provide constant success probability, while the analysis establishes correctness and query-time bounds.
- Two-level design: Two-level hashing first partitions points into bounded-diameter buckets, then applies bucket-specific inner hashing whose functions depend on each bucket’s data.The outer family performs partial standard LSH partitioning; the inner family uses improved Gaussian LSH after the bucket geometry is controlled.
- Two-level design: The method introduces a third distance scale, τc, and uses outer hashing to make bucket diameters O_τ(c) before inner hashing.This enables the inner family to operate on buckets whose point sets have bounded diameter.
- Construction: For each bucket, preprocessing repeatedly removes pairs farther than τc, computes the minimum enclosing-ball center, and organizes points by distance from that center.The resulting annular groups are indexed with the inner hash family.
- Correctness: If the query algorithm returns a point, that point belongs to P and lies within distance c of the query.The construction’s correctness is stated directly before the probability analysis.
- Complexity and success: The expected query time for one two-level table is O_c(n^{o_c,τ(1)} + d log n), because it examines at most one non-approximate near neighbor on average.The algorithm uses independent copies to amplify the success probability to a constant.
- Complexity and success: With probability at least 1−1/3−1/e, the modified algorithm finds an approximate near neighbor without examining more than 3/Q + 1 non-approximate points.This gives a worst-case query bound variant while preserving the multi-table failure analysis.