Data-dependent hashing via nonlinear spectral gaps

DOI10.1145/3188745.3188846MaRDI QIDQ5230338zbMATH OpenOpenAlexFDO

Authors Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3188745.3188846

zbMATH Keywords

locality-sensitive hashingnearest neighbor searchnonlinear spectral gapsrandomized space partitions

Mathematics Subject Classification ID

Data structures (68P05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Optimal data-dependent hashing for approximate near neighbors
• Beyond locality-sensitive hashing
• Tight lower bounds for data-dependent locality-sensitive hashing
• Optimal hashing-based time-space trade-offs for approximate near neighbors
• Optimal Las Vegas approximate near neighbors in \(\ell_p\)

Cited in

(12)

• Multidimensional quantile hashing is very efficient for nonuniform distributions
• ForestDSH: a universal hash design for discrete probability distributions
• An average John theorem
• Fast spectral analysis for approximate nearest neighbor search
• Nonpositive curvature is not coarsely universal
• Optimal data-dependent hashing for approximate near neighbors
• Tight lower bounds for data-dependent locality-sensitive hashing
• Uncorrelated Component Analysis-Based Hashing
• Approximate near neighbors for general symmetric norms
• VBLSH: volume-balancing locality-sensitive hashing algorithm for K-nearest neighbors search
• Near neighbor search via efficient average distortion embeddings
• Lipschitz decompositions of finite _p metrics

This page was built for publication: Data-dependent hashing via nonlinear spectral gaps

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