Spectral Partitioning for Metrics (And NNs Too)

This talk establishes a general reduction from nonlinear spectral gaps of metric spaces to data-dependent space partitions in the form of locality-sensitive hashing. The reduction yields an approach to high-dimensional approximate near-neighbor search and a data structure for any d-dimensional norm whose query algorithm makes a sublinear number of probes. Its approximation factor is O(log d), improving on the square-root-of-d factor available from the generic approach based on John’s ellipsoid. The presentation connects spectral properties, geometric partitions, and efficient approximate search. Joint work with Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten.