Abstract: 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.
Introduction
Locality-Sensitive Hashing (LSH) has long been the "gold standard" for approximate nearest neighbor search (NNS) in high-dimensional spaces. However, a frustrating gap has persisted for years: algorithms that were theoretically "optimal" (having the best possible scaling behavior) were often too slow to use in the real world, while the "practical" algorithms used by engineers were theoretically suboptimal.
In this work, we bridge this gap by introducing a new LSH family for angular distance that is both theoretically optimal and significantly faster than the industry-standard "hyperplane LSH" in practice. Our scheme, based on cross-polytopes, achieves up to a 10x speedup over standard methods on large-scale datasets.
The Problem: Balancing Theory and Practice
Nearest Neighbor Search (NNS) is the task of finding the closest point in a dataset to a given query. In high dimensions, this becomes computationally expensive—a phenomenon known as the "curse of dimensionality." LSH addresses this by using hash functions that ensure nearby points are more likely to "collide" in the same bucket than far-apart points.
For angular distance, the standard tool has been Hyperplane LSH. While simple and fast to compute, its "quality" (defined by the exponent $\rho$, which determines how query time scales with the number of points $n$) is suboptimal. Conversely, previous "Spherical LSH" schemes were proven to be optimal but involved hash functions so complex that they were often slower than a simple linear search. We set out to find a hash family that is both optimal and actually fast.
Methods: Cross-polytope LSH
The core of our approach is the Cross-polytope LSH. Instead of using a single hyperplane to split space, we utilize the geometry of a cross-polytope (the $L_1$ unit ball).
To hash a point, we rotate it randomly and find which vertex of the cross-polytope it is closest to. The cross-polytope is a simple enough shape that finding the "closest vertex" is extremely efficient—it is merely the coordinate with the largest absolute value. To make this practical in high dimensions, we employ several optimizations:
- Fast Rotations: A naive random rotation requires $O(d^2)$ time. We use Pseudo-random Rotations via the Fast Hadamard Transform (FHT), reducing computation time to $O(d \log d)$.
- Feature Hashing: For sparse data, we use feature hashing to reduce dimensionality before applying rotations.
- Multiprobe Scheme: To reduce memory footprint, we developed a multiprobe version that intelligently checks "nearby" hash buckets in a single table rather than requiring many independent tables.
Theoretical Optimality and Lower Bounds
We provide a new "fine-grained" lower bound showing that for any LSH family where the hash is computed by checking a fixed number of "parts" (like vertices), there is a fundamental trade-off between evaluation speed and quality (the $\rho$ value).
As shown in the figure above, our cross-polytope LSH sits very close to this theoretical limit, matching the optimality of much more complicated spherical schemes while remaining computationally efficient. Furthermore, the performance is essentially "dimension-free," making it robust for the extremely high-dimensional vectors found in modern machine learning.
Experimental Results
We evaluated the algorithm on both synthetic and real-world datasets, including SIFT (1M image features), NYT (300k text vectors), and Pubmed (8M medical abstracts). The Cross-polytope (CP) LSH consistently outperformed Hyperplane (HP) LSH:
- Speedup on Sparse Data: On NYT and Pubmed, CP was 3.4x to 4.0x faster than HP.
- Scaling: On synthetic data with up to 268 million points, the speedup over HP grew to 10.3x.
- Efficiency: On the largest datasets, the algorithm was up to 700x faster than a simple linear search while maintaining a 90%+ success rate.
Conclusion
By combining the geometric properties of cross-polytopes with fast pseudo-random rotations, we have developed an LSH scheme that finally reconciles theoretical optimality with practical performance. While future work may further optimize rotations for extremely sparse data, the cross-polytope LSH currently represents a significant step forward in high-dimensional similarity search.
Summary updated