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

DOI10.1137/1.9781611974782.4zbMath1410.68091arXiv1608.03580OpenAlexW2508919161MaRDI QIDQ4575737

Thijs Laarhoven, Erik Waingarten, Alexandr Andoni, Ilya Razenshteyn

Publication date: 16 July 2018

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

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

Mathematics Subject Classification ID

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

Related Items (12)

Lower bounds on lattice sieving and information set decoding ⋮ A new coding-based algorithm for finding closest pair of vectors ⋮ Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time ⋮ On the Distortion of Locality Sensitive Hashing ⋮ Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1 ⋮ A kd-tree-accelerated hybrid data-driven/model-based approach for poroelasticity problems with multi-fidelity multi-physics data ⋮ Index structures for fast similarity search for real-valued vectors. I ⋮ Index structures for fast similarity search for binary vectors ⋮ ForestDSH: a universal hash design for discrete probability distributions ⋮ A sub-linear time algorithm for approximating k-nearest-neighbor with full quality guarantee ⋮ Unnamed Item ⋮ Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\)

This page was built for publication: Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors