Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors

Abstract

[See the paper for the full 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)}+d{n}^{o(1)}$ for every ${\rho }_u,{\rho }_q\ge 0$ such that: \begin{equation} c^2 \sqrt{ρ_q} + (c^2 - 1) \sqrt{ρ_u} = \sqrt{2c^2 - 1}. \end{equation} This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor $c>1$, improving upon [Kapralov, PODS 2015]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [Becker, Ducas, Gama, Laarhoven, SODA 2016] and data-dependent hashing [Andoni, Indyk, Nguyen, Razenshteyn, SODA 2014] [Andoni, Razenshteyn, STOC 2015]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole above trade-off in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match the above trade-off for ${\rho }_q=0$, improving upon the best known lower bounds from [Panigrahy, Talwar, Wieder, FOCS 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes.

62 pages, 5 figures; a merger of arXiv:1511.07527 [cs.DS] and arXiv:1605.02701 [cs.DS], which subsumes both of the preprints. New version contains more elaborated proofs and fixed some typos

References in corpus (6)

• Practical and Optimal LSH for Angular Distance
• Probabilistic Polynomials and Hamming Nearest Neighbors
• Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters
• Tradeoffs for nearest neighbors on the sphere
• Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
• Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities

Cited by in corpus (5)

• An accelerated hybrid data-driven/model-based approach for poroelasticity problems with multi-fidelity multi-physics data
• Neural Distributed Autoassociative Memories: A Survey
• Fair Near Neighbor Search: Independent Range Sampling in High Dimensions
• Nearest neighbor decoding for Tardos fingerprinting codes
• Terminal Embeddings in Sublinear Time