Hypercube LSH for approximate near neighbors

DOI10.4230/LIPICS.MFCS.2017.7MaRDI QIDQ5111221zbMATH OpenFDO

Authors Thijs Laarhoven

Publication date 26 May 2020

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

zbMATH Keywords

approximate near neighborsdimensionality reductionlarge deviationslattice algorithmslocality-sensitive hashing

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• On the kernel of the theta operator mod \(p\)
• A locality-sensitive hash for real vectors
• Lattice-based locality sensitive hashing is optimal
• Optimal Las Vegas approximate near neighbors in \(\ell_p\)
• Fast cross-polytope locality-sensitive hashing

Cites work

• A framework for similarity search with space-time tradeoffs using locality-sensitive filtering
• Beyond locality-sensitive hashing
• Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
• Efficient (ideal) lattice sieving using cross-polytope LSH
• Extensions of Lipschitz mappings into a Hilbert space
• Fast cross-polytope locality-sensitive hashing
• Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
• How many entries of a typical orthogonal matrix can be approximated by independent normals?
• scientific article; zbMATH DE number 3863589 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• Large deviations techniques and applications.
• Lower Bounds on Locality Sensitive Hashing
• New directions in nearest neighbor searching with applications to lattice sieving
• On computing nearest neighbors with applications to decoding of binary linear codes
• Optimal data-dependent hashing for approximate near neighbors
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Pattern classification.
• Pattern recognition and machine learning.
• Sieve algorithms for the shortest vector problem are practical
• 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

(7)

• On the kernel of the theta operator mod \(p\)
• Index structures for fast similarity search for real-valued vectors. I
• Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
• Efficient Nearest Neighbors via Robust Sparse Hashing
• Fast cross-polytope locality-sensitive hashing
• Graph-based time-space trade-offs for approximate near neighbors
• Polytopes, lattices, and spherical codes for the nearest neighbor problem

Describes a project that uses

Uses Software

• FALCONN
• PRMLT

This page was built for publication: Hypercube LSH for approximate near neighbors

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