Optimal Data-Dependent Hashing for Approximate Near Neighbors

DOI10.1145/2746539.2746553zbMath1321.68212arXiv1501.01062OpenAlexW2017851434MaRDI QIDQ2941575

Ilya Razenshteyn, Alexandr Andoni

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

data structuresdecision treeshigh-dimensional geometrysimilarity search

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Approximation algorithms (68W25)

Related Items (20)

Lower bounds on lattice sieving and information set decoding ⋮ Exploiting pseudo-locality of interchange distance ⋮ Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ Finding shortest lattice vectors faster using quantum search ⋮ Lattice Sieving via Quantum Random Walks ⋮ Unnamed Item ⋮ Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time ⋮ Lattice-based locality sensitive hashing is optimal ⋮ Identifying an unknown code by partial Gaussian elimination ⋮ Index structures for fast similarity search for real-valued vectors. I ⋮ Index structures for fast similarity search for binary vectors ⋮ An \(O(\log n)\) query time algorithm for reducing \(\varepsilon \)-NN to \((c,r)\)-NN ⋮ ForestDSH: a universal hash design for discrete probability distributions ⋮ Unnamed Item ⋮ A sub-linear time algorithm for approximating k-nearest-neighbor with full quality guarantee ⋮ Locality-Sensitive Hashing Without False Negatives for $$l_p$$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximate Nearest Neighbors Search Without False Negatives For l_2 For c>sqrt{loglog{n}}. ⋮ Local Density Estimation in High Dimensions

Uses Software

• Graphs

Cites Work

• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Unnamed Item

This page was built for publication: Optimal Data-Dependent Hashing for Approximate Near Neighbors