Fast cross-polytope locality-sensitive hashing

DOI10.4230/LIPICS.ITCS.2017.53MaRDI QIDQ4638108zbMATH OpenFDO

Authors Rachel Ward, Christopher A. Kennedy

Publication date 3 May 2018

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

zbMATH Keywords

dimension reductionJohnson-Lindenstrauss transformlocality-sensitive hashing

Mathematics Subject Classification ID

General topics in the theory of data (68P01) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Lattice-based locality sensitive hashing is optimal
• On the kernel of the theta operator mod \(p\)
• Locality-sensitive hashing without false negatives
• Hypercube LSH for approximate near neighbors
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)

Cites work

• A randomized approximate nearest neighbors algorithm
• Beyond locality-sensitive hashing
• Efficient (ideal) lattice sieving using cross-polytope LSH
• Efficient algorithms for substring near neighbor problem
• Extensions of Lipschitz mappings into a Hilbert space
• scientific article; zbMATH DE number 5506204 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• Locality-sensitive hashing scheme based on p-stable distributions
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Optimal data-dependent hashing for approximate near neighbors
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Problems and results in extremal combinatorics. I.
• Sparser Johnson-Lindenstrauss transforms
• Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• The restricted isometry property of subsampled Fourier matrices

Cited in

(7)

• On the kernel of the theta operator mod \(p\)
• A new lattice sieving algorithm base on angular locality-sensitive hashing
• Index structures for fast similarity search for real-valued vectors. I
• Hypercube LSH for approximate near neighbors
• Graph-based time-space trade-offs for approximate near neighbors
• scientific article; zbMATH DE number 7278047 (Why is no real title available?)
• Polytopes, lattices, and spherical codes for the nearest neighbor problem

This page was built for publication: Fast cross-polytope locality-sensitive hashing

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