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 \geq 0\) such that: \begin\{equation\} c^2 \sqrt\{\rho_q\} + (c^2 - 1) \sqrt\{\rho_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 lo

Stats

• citations31
• S2 citations—
• github stars0
• HF likes0
• heat score11.29
• arxiv keyandoni2016optimal

Related papers

• Optimal Las Vegas Locality Sensitive Data Structures (2017)6.77
• Approximate Nearest Neighbors Search Without False Negatives For \(l_2\) For \(c>\sqrt{\log\log{n}}\) (2017)0.00
• Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search (2017)7.81
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Approximate Near Neighbors For General Symmetric Norms (2016)8.35
• Sublinear Data Structures For Nearest Neighbor In Ultra High Dimensions (2025)0.00
• A Framework For Similarity Search With Space-time Tradeoffs Using Locality-sensitive Filtering (2016)8.35
• Multi-level Spherical Locality Sensitive Hashing For Approximate Near Neighbors (2017)0.00