Data-dependent hashing via nonlinear spectral gaps

DOI10.1145/3188745.3188846zbMath1427.68327OpenAlexW2809514611MaRDI QIDQ5230338

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

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

nearest neighbor searchlocality-sensitive hashingnonlinear spectral gapsrandomized space partitions

Mathematics Subject Classification ID

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

Related Items (6)

Fast spectral analysis for approximate nearest neighbor search ⋮ VBLSH: volume-balancing locality-sensitive hashing algorithm for K-nearest neighbors search ⋮ ForestDSH: a universal hash design for discrete probability distributions ⋮ Impossibility of dimension reduction in the nuclear norm ⋮ An average John theorem ⋮ Nonpositive curvature is not coarsely universal

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