Optimal hashing-based time-space trade-offs for approximate near neighbors

DOI10.1137/1.9781611974782.4zbMATH Open1410.68091arXiv1608.03580OpenAlexW2508919161MaRDI QIDQ4575737FDOQ4575737

Authors: Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, Erik Waingarten 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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+h{o}_u+o(1)}+O(dn)$ and query time $n^{h{o}_q+o(1)}+d{n}^{o(1)}$ for every $h{o}_u,h{o}_{q}geq0$ such that: �egin{equation} c^2 sqrt{ ho_q} + (c^2 - 1) sqrt{ ho_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 $h{o}_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.

Full work available at URL: https://arxiv.org/abs/1608.03580

Recommendations

• Optimal data-dependent hashing for approximate near neighbors
• Beyond locality-sensitive hashing
• Space-time tradeoffs for approximate nearest neighbor searching
• A framework for similarity search with space-time tradeoffs using locality-sensitive filtering
• Graph-based time-space trade-offs for approximate near neighbors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (24)

• Terminal embeddings in sublinear time
• Hash Bit Selection for Nearest Neighbor Search
• Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\)
• Optimal data-dependent hashing for approximate near neighbors
• A framework for similarity search with space-time tradeoffs using locality-sensitive filtering
• Optimal Las Vegas Approximate Near Neighbors in ℓ _p
• Optimal Las Vegas approximate near neighbors in \(\ell_p\)
• ForestDSH: a universal hash design for discrete probability distributions
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Data-dependent hashing via nonlinear spectral gaps
• Index structures for fast similarity search for real-valued vectors. I
• Graph-based time-space trade-offs for approximate near neighbors
• Index structures for fast similarity search for binary vectors
• A sub-linear time algorithm for approximating k-nearest-neighbor with full quality guarantee
• Beyond locality-sensitive hashing
• Streaming Euclidean MST to a constant factor
• On the Distortion of Locality Sensitive Hashing
• Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1
• Lower bounds on lattice sieving and information set decoding
• A kd-tree-accelerated hybrid data-driven/model-based approach for poroelasticity problems with multi-fidelity multi-physics data
• A new coding-based algorithm for finding closest pair of vectors
• Title not available (Why is that?)
• Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
• Efficient Nearest Neighbors via Robust Sparse Hashing

This page was built for publication: Optimal hashing-based time-space trade-offs for approximate near neighbors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575737)