Lecture Title: Spectral Partitioning and Nearest Neighbor Search
Presented By: Aleksandar Nikolov, Assistant Professor, Department of Computer Science, University of Toronto
Location: Fields Institute, 222 College Street, Room 230
Abstract: In the Approximate Nearest Neighbor Search (NNS) problem our goal is to pre-process a given set of points P in d-dimensional space into a data structure so that, given a query point q, we can quickly find a point p in P which is as close as possible to q according to some distance measure. NNS is an important primitive in many data analysis tasks, and has numerous applications in computational geometry, databases, computer vision, and machine learning, among others. In this talk I will focus on the high-dimensional regime in which space or query time exponential in dimension are unacceptable. I will describe a way to apply spectral partitioning of graphs to the NNS problem, giving us a generic reduction from nonlinear spectral gaps of metric spaces to data-dependent Locality-Sensitive Hashing, and a new approach to NNS data structures in high-dimensional spaces. Using this reduction, we get NNS data structures in the cell probe model for any d-dimensional norm with log(d) approximation, near-linear space, and sublinear query complexity. We also obtain improved NNS data structures for classical norms, like Lp norms and Schatten-p matrix norms. Finally, combining this reduction with a smooth map between spheres of normed spaces due to Daher, we get the first efficient high-dimensional NNS data structure with approximation sub-polynomial in the dimension d.