Graph-based time-space trade-offs for approximate near neighbors

DOI10.4230/LIPICS.SOCG.2018.57MaRDI QIDQ5115825zbMATH OpenFDO

Authors Thijs Laarhoven

Publication date 18 August 2020

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

zbMATH Keywords

similarity searchlocality-sensitive hashingapproximate nearest neighbor problemlocality-sensitive filtersnear neighbor graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Optimal hashing-based time-space trade-offs for approximate near neighbors
• New directions in nearest neighbor searching with applications to lattice sieving
• scientific article; zbMATH DE number 1559575
• scientific article; zbMATH DE number 1953148
• Space-time tradeoffs for approximate nearest neighbor searching

Cites work

• scientific article; zbMATH DE number 1003290 (Why is no real title available?)
• scientific article; zbMATH DE number 1559576 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• A framework for similarity search with space-time tradeoffs using locality-sensitive filtering
• Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
• Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detection
• Distributed computation of the \textit{k}nn graph for large high-dimensional point sets
• Efficient (ideal) lattice sieving using cross-polytope LSH
• Efficient algorithms for substring near neighbor problem
• Extensions of Lipschitz mappings into a Hilbert space
• Fast approximate \(k\)NN graph construction for high dimensional data via recursive Lanczos bisection
• Fast cross-polytope locality-sensitive hashing
• Hypercube LSH for approximate near neighbors
• LSH Forest: Practical Algorithms Made Theoretical
• Locality-sensitive hashing scheme based on \(p\)-stable distributions
• New directions in nearest neighbor searching with applications to lattice sieving
• On computing nearest neighbors with applications to decoding of binary linear codes
• On nearest-neighbor graphs
• Pattern classification.
• Pattern recognition and machine learning.
• Separators for sphere-packings and nearest neighbor graphs
• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
• Similarity estimation techniques from rounding algorithms
• Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere

Cited in

(3)

• Optimal hashing-based time-space trade-offs for approximate near neighbors
• The randomized slicer for CVPP: sharper, faster, smaller, batchier
• Approximate $k$-Nearest Neighbor Graph on Moving Points

Describes a project that uses

Uses Software

• PRMLT
• annoy
• GitHub
• FALCONN
• GloVe

This page was built for publication: Graph-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 Q5115825)