Practical and Optimal LSH for Angular Distance

Alexandr Andoni; Piotr Indyk; Thijs Laarhoven; Ilya Razenshteyn; Ludwig Schmidt

Source-linked AI summary

Practical and Optimal LSH for Angular Distance

Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, Ludwig Schmidt

arXiv:1509.02897v1Sep 9, 2015cs.DScs.CGcs.IR

TL;DR

The paper asks what good LSH families are for angular distance and develops cross-polytope hashing, including a multiprobe variant. It shows exponent-optimal guarantees, practical speedups over hyperplane LSH and linear scan, and a near-optimal evaluation-time–quality trade-off, while the underlying scheme can be too costly to evaluate in practice.

Problem
The paper studies what good LSH families are for angular distance, including the near–far search setting quantified by c > 1.
Method
The paper uses randomly rotated cross-polytopes for hashing unit vectors and proposes a multiprobe cross-polytope scheme with feature hashing to exploit sparsity.
Results
The cross-polytope family achieves the same parameter ρ as Spherical LSH for unit vectors, while its multiprobe variant is up to 10× faster than hyperplane LSH and up to 700× faster than linear scan.
Takeaways & Limitations
The combination provides an exponent-optimal and practical LSH approach for data sets with around 10^5 to 10^8 points.
Takeaways & Limitations
The earlier scheme is impractical because a single hash function can take longer to evaluate than a linear scan over 10^6 points, and an LSH structure uses many hash functions.

Abstract

from arXiv · show

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 [Andoni, Indyk, Nguyen, Razenshteyn 2014], [Andoni, Razenshteyn 2015]), our algorithm is also practical, improving upon the well-studied hyperplane LSH [Charikar, 2002] in practice. We also introduce a multiprobe version of this algorithm, and conduct 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.

1 Introduction

The paper asks whether locality-sensitive hashing for angular distance can combine optimal theoretical guarantees with practical performance. It presents cross-polytope LSH, multiprobe techniques, lower bounds, and experiments addressing this gap.

Angular distance is practically relevant because Euclidean distance on the unit sphere corresponds to cosine similarity in image, speaker, and tf-idf representations.
The central question is whether an LSH family can achieve optimal guarantees while improving over hyperplane LSH in practice.
Cross-polytope LSH based on randomly rotated cross-polytopes achieves the same parameter ρ as Spherical LSH for unit-vector data.
A fine-grained lower bound shows that requiring large far-point collision probability p2 forces the quality parameter ρ to be suboptimal, making the cross-polytope trade-off essentially optimal.
A novel multiprobe scheme makes cross-polytope LSH competitive with multiprobe hyperplane LSH while addressing LSH's often-large memory footprint.
For data sets with around 10^5 to 10^8 points, the multiprobe variant is up to 10× faster than hyperplane LSH and up to 700× faster than linear scan.

2 Preliminaries

The paper studies approximate near neighbor search on the unit sphere, where Euclidean distance between normalized vectors also captures angular distance. It formalizes approximate near neighbors and locality-sensitive hashing through collision probabilities for near and far points.

The unit sphere S^{d−1} is the domain for near neighbor search, with ∥.∥ denoting the Euclidean norm.
Angular distance can be handled through Euclidean distance between normalized vectors.
In (c, r)-ANN, a query with a datapoint within distance r must return a datapoint within distance cr.
An (r1, r2, p1, p2)-sensitive hash family gives collision probabilities p1 for near pairs and p2 for far pairs.
The standard LSH reduction yields ANN structures with space O(n1+ρ/p1 + dn) and query time O(d · nρ/p1).

3 Cross-polytope LSH

Cross-polytope LSH hashes rotated points to their nearest signed basis vector and achieves collision bounds comparable to theoretically optimal spherical LSH. The paper makes it practical with pseudo-random rotations, feature hashing, and partial basis selection while preserving the analysis in the stated forms.

3 Cross-polytope LSH: Cross-polytope LSH applies a random Gaussian rotation, normalizes the result, and selects its closest point among the signed basis vectors {±e_i}.
3 Cross-polytope LSH: Theorem 1 bounds collision probabilities for two sphere points at Euclidean distance τ, reducing the analysis to Gaussian probability estimates.
3 Cross-polytope LSH: The cross-polytope construction matches the collision-probability bounds of theoretically optimal spherical LSH and gives sub-quadratic space with sublinear query time.
3.1 Making the cross-polytope LSH practical: The original construction is impractical because sampling and applying a full random rotation can be prohibitively expensive.
3.1 Making the cross-polytope LSH practical: Pseudo-random rotations replace Gaussian matrices with HD3HD2HD1, storable in O(d) space and evaluable in O(d log d) time.
3.1 Making the cross-polytope LSH practical: For sparse vectors, feature hashing reduces dimension to d′ and evaluation time to O(s + d′ log d′).
3.1 Making the cross-polytope LSH practical: Restricting the hash to d′ ≤ d signed basis vectors preserves Theorem 1 with d replaced by d′, and d′ = 1 recovers hyperplane LSH.

4 Lower bound

The section establishes a lower bound on the collision-probability trade-off for angular-distance LSH and compares it with cross-polytope LSH. The bound implies that substantially improving the scheme in practice requires faster evaluation at nearly optimal quality.

The lower-bound analysis replaces p2 with a related quantity p∗2 that is easier to handle asymptotically.
Theorem 2 bounds p1 for sphere hash families whose functions partition the sphere into at most T parts of measure at most 1/2.
The lower-bound theorem assumes every hash partition has parts of measure at most 1/2, a restriction the authors conjecture is unnecessary and call essentially irrelevant in the interesting parameter range.
The cross-polytope LSH has an almost optimal trade-off between ρ and T, but its convergence to optimal ρ is extremely slow.
Because cross-polytope evaluation takes O(T log T), substantial practical improvement requires nearly optimal ρ with evaluation time sublinear in T.

5 Multiprobe LSH for the cross-polytope LSH

The section develops a multiprobe extension for cross-polytope LSH by ranking alternative hash locations according to their estimated collision probabilities. An incremental implementation reduces probing overhead while preserving the scheme's ranking principle.

Multiprobe LSH probes multiple nearby hash cells so a target success probability can be reached with fewer hash tables than standard LSH.
For one cross-polytope hash, alternative coordinates are probed in descending order of their absolute rotated-query coordinates.
For multiple hash functions, probing locations are ranked by approximating each location's probability through the Gaussian measure of its associated region.
The probability of probing location v is approximated as proportional to exp(−∥y_x,v∥^2), where y_x,v is the shortest vector that changes the winning coordinate to v.
A further approximation modifies only one coordinate, avoiding the need to know the distance R.
Incremental sorting reduces the running time from O(L · d log d + m log m) to O(L · d + m log m).

6 Experiments

Experiments evaluate cross-polytope LSH and its multiprobe variant against hyperplane LSH on synthetic and real data. The cross-polytope method is faster across the reported real data sets, with larger gains on tf-idf data and strong speedups on random data.

The evaluation targets exact nearest-neighbor query time on random, tf-idf, and SIFT data sets.
Multiprobe experiments: 13× faster performance is observed for multiprobe cross-polytope LSH than its standard variant in the memory-constrained random-data setting with L = 10.
Multiprobe experiments: Without multiprobing, cross-polytope LSH would be slower than hyperplane LSH, which already has a multiprobe scheme.
Experiments on random data: 3.5× speedup over hyperplane LSH occurs at n = 2^20 random points, increasing to 10.3× at n = 2^28.
Experiments on random data: Compared with linear scan, cross-polytope LSH achieves speedups from 76× at n = 2^20 to about 700× at n = 2^28.
Experiments on real data: On real data, cross-polytope LSH is 1.2× faster on SIFT and 3−4× faster on the two tf-idf data sets.

A Gaussian measure of a planar set

This section develops Gaussian-measure bounds for planar sets by relating radial intersection measures to the distance of a set from the origin. It then applies these facts to convex and half-plane intersections.

For a closed set A, μ_A(r) denotes normalized measure on A ∩ rS^1, while Δ_A is its essential distance from the origin.
Lemma 1 bounds the standard Gaussian measure G(A) when μ_A(r) is non-decreasing.
The proof derives upper and lower bounds by evaluating radial measures and using the monotonicity of μ_A(r).
For complements of symmetric open convex planar sets, convexity ensures the radial measure μ_K(r) is non-decreasing.
Lemma 3 applies the same framework to intersections of two closed half-planes whose corner is closest to the origin and which contain no line.

B Proof of Theorem 1

The proof of Theorem 1 reduces the collision bound to Gaussian probabilities involving σ(u, v) and distance from the origin to constraint sets.

σ(u, v) is defined as the Gaussian probability that both |X2| ≤ u and |αX2 + βY2| ≤ αu + βv.
The right-hand side of Eqn. (1) equals 2^d · E[σ(X1, Y1)^(d−1)] for independent standard Gaussians X1 and Y1.
The relevant distance is the distance from the origin to the set where either |x| ≥ u or |αx + βy| ≥ αu + βv.
For the Gaussian threshold event, the proof bounds Pr[∆(X1, Y1) ≥ t] by e^(−(4/(4−τ^2))·t^2/2).

B.1 Idealized proof

The idealized proof expands the collision-probability expression using asymptotic estimates, with each step justified by standard identities, lemmas, or approximations.

The idealized argument assumes Pr[∆(X1, Y1) ≥ t] = e^(−(4/(4−τ^2))·t^2/2).
The expansion of Eqn. (1) proceeds through expectation expansion, bounds from (2) and (3), a change of variables, and Beta-function and Stirling steps.
The fifth step defines the Beta function, while the sixth step uses the Stirling approximation.
Substituting the resulting expression into Eqn. (1) yields the idealized form used before the precise calculation.

B.2 The real proof

The real proof replaces idealized estimates with precise bounds, using ε = 1/d, and obtains Theorem 1 with a tight low-order correction.

ε = 1/d is used to obtain asymptotic estimates for σ(u, v) and the Gaussian tail probability.
Pr[∆(X, Y) ≥ t] = d^±O(1) · e^(−(1±d^−Ω(1))·(4/(4−τ^2))·t^2/2).
The idealized proof is repeated with the new estimates to obtain the final form of Theorem 1.
The real proof differs from the idealized version in a low-order term, O_τ(ln ln d), which the paper states is tight.

C Proof of Theorem 2

The proof of Theorem 2 uses spherical-cap extremality, concentration, and Gaussian approximation to establish the required concavity and handle small-measure parts.

For a measurable spherical subset A of measure µ0 ≤ 1/2, the left-hand side is maximized when A is a spherical cap.
The threshold η is chosen so that a standard Gaussian satisfies Pr[X ≥ η] = µ0.
The proof uses concentration of measure, conditional-probability expansion, and convergence of fixed-dimensional spherical projections to a standard Gaussian measure.
The function µ ↦ Λ(τ, Φ_c^−1(µ)) is concave for 0 < µ < 1/2.
To prove the needed nonnegativity, the argument shows Ω′(η) ≤ 0 for η ≥ 0 and uses lim_{η→∞} Ω(η) = 0.
The proof initially assumes every part has measure Ω(1), then removes this assumption because parts of measure at most ε contribute at most ε · T.
The remaining algebra uses the definitions of p1 and p*(H), the Ω(1) condition, Lemma 6, Lemma 7, and the bound µ(h^−1(i)) ≤ 1/2.

D Further description of experiments

The experiments evaluate cross-polytope LSH on synthetic and real data using matched implementations and varied data, dimensions, and query settings. Results include dataset-specific performance comparisons with hyperplane LSH and a multiprobe variant.

Implementation: The cross-polytope and hyperplane LSH implementations were both optimized by the authors to the same degree for fair running-time comparisons.The implementation uses matrix-vector multiplication, a SIMD-optimized Fast Hadamard Transform, and compiled C++ code.
Data sets: The evaluation uses random, pubmed, NYT, and SIFT data sets, with Figure 3 reporting their nearest-neighbor distance distributions.Random data vary dimension and number of points while holding other parameters constant; pubmed and NYT use high-dimensional tf-idf vectors, and SIFT uses normalized 128-dimensional feature vectors.
Data sets: The random data sets contain uniformly sampled unit-sphere points, with queries generated at a prescribed distance R from sampled data points.Experiments vary dimensions from 128 to 1,024.
Data sets: The pubmed and NYT collections use approximately 100,000-dimensional tf-idf vectors, containing about 8 million and 300,000 points, respectively.The experiments reserve 1,000 data points as query vectors and focus on nearest-neighbor inner products between 0.3 and 0.8.
Data sets: The SIFT benchmark contains one million 128-dimensional feature vectors and 10,000 queries; normalization changes only a very small fraction of nearest-neighbor assignments.The speed-up of cross-polytope LSH is more modest on this data set.
Results: On random data with d = 128 and R = 2/2, cross-polytope LSH is up to 10× faster than hyperplane LSH.The speed-up is not monotonic in n because performance depends on the optimal k and the dimension of the last cross-polytope.