Abstract
We show tight upper and lower bounds for time-space trade-offs for the $c$-approximate Near Neighbor Search problem. For the $d$-dimensional Euclidean space and $n$-point datasets, we develop a data structure with space $n^{1+\rho_u+o(1)} + O(dn)$ and query time $n^{\rho_q+o(1)} + dn^{o(1)}$ for every $\rho_u, \rho_q \geq 0$ satisfying the trade-off: $c^2 \sqrt{\rho_q} + (c^2 - 1) \sqrt{\rho_u} = \sqrt{2c^2 - 1}$. This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor $c > 1$. We further provide matching conditional and unconditional lower bounds, including the first space lower bound for two probes that is not polynomially smaller than the one-probe bound, established via a novel connection to locally-decodable codes.
1. Introduction
The Near Neighbor Search (NNS) problem is a fundamental challenge in computational geometry and machine learning, requiring the identification of a point in a dataset $P$ closest to a query point $q$. In high-dimensional settings, the problem is plagued by the "curse of dimensionality," where algorithms typically revert to a linear scan or require exponential space. To mitigate this, the $(c, r)$-Approximate Near Neighbor (ANN) search is employed: if a point exists within distance $r$, the algorithm returns a point within distance $cr$.
While Locality-Sensitive Hashing (LSH) has long been the standard approach, a comprehensive understanding of the trade-off between memory (space) and speed (query time) remained elusive—particularly in the "near-linear space" regime. This regime is of paramount importance for practical applications where memory is a constrained resource. This paper provides the first tight map of this trade-off frontier.
2. The Time-Space Trade-off Frontier
The core contribution of this work is the definition and proof of the optimal trade-off curve for Euclidean space. The relationship between the space exponent $\rho_u$ and the query time exponent $\rho_q$ is governed by the following equation:
$$c^2 \sqrt{\rho_q} + (c^2 - 1) \sqrt{\rho_u} = \sqrt{2c^2 - 1}$$
This Pareto frontier allows for a flexible selection of parameters depending on the application's constraints. For instance, one can optimize for near-constant query time at the cost of higher space, or minimize space usage while maintaining sublinear query performance.
3. Algorithmic Framework
The proposed data structure achieves these bounds through a combination of data-independent and data-dependent techniques.
3.1. Data-Independent Partitions
The algorithm utilizes a decision tree based on a modified version of Spherical Locality-Sensitive Filtering (LSF). By using random Gaussian vectors to define spherical caps, the algorithm partitions the space such that points falling into specific caps are stored in the leaves of the tree. This approach is highly effective for "pseudo-random" or well-distributed data.
3.2. Data-Dependent Partitions
To maintain optimality on "worst-case" datasets, the framework incorporates data-dependent clustering. The algorithm identifies "dense clusters"—groups of points that are significantly closer together than expected in a random distribution. These clusters are extracted into smaller balls and processed recursively. Points that do not belong to any dense cluster are treated as pseudo-random and handled via the spherical LSF method. This dual approach ensures that the data structure adapts to the underlying geometry of the dataset.
4. Theoretical Optimality and Lower Bounds
The paper establishes the tightness of the trade-off through two distinct types of lower bounds:
- Conditional Bounds: The authors prove that the trade-off is tight within the "list-of-points" model, which encompasses nearly all known hashing-based frameworks, including LSH and LSF.
- Unconditional Bounds: Using the cell-probe model, the authors prove lower bounds for data structures accessing only one or two memory cells.
- The LDC Connection: A significant theoretical breakthrough is the connection established between two-probe lower bounds and Locality-Decodable Codes (LDCs). By leveraging quantum information theory (specifically quantum random access codes), the authors demonstrate that a second probe cannot provide a polynomial improvement in space over a single probe, matching the predicted trade-off for $\rho_q = 0$.
5. Key Results for $c = 2$
To illustrate the impact of these bounds, consider the case of a 2-approximation ($c = 2$). The framework demonstrates several landmark points on the curve:
- Fast Queries: Space $n^{1.77...}$ with query time $n^{o(1)}$. This significantly improves upon previous structures designed for fast queries.
- Balanced Regime: Space $n^{1.14...}$ with query time $n^{0.14...}$, matching the performance of the best known data-dependent LSH.
- Near-Linear Space: Space $n^{1+o(1)}$ with query time $n^{0.43...}$. This represents the first time sublinear query time has been achieved in near-linear space for an arbitrary $c > 1$.
6. Conclusion and Future Work
This work provides a definitive answer to the time-space trade-off for hashing-based approximate near neighbor search in Euclidean space. While the theoretical bounds are tight, the authors note that the data-dependent clustering step remains a practical bottleneck for high-performance implementations. Future research may focus on simplifying these clustering techniques or extending the trade-off analysis to other metrics, such as $\ell_\infty$ or general $\ell_p$ spaces for $p > 2$. Additionally, the behavior of these bounds in the regime where the dimension $d = \Theta(\log n)$ remains an intriguing open question.
Summary updated