Nearest neighbor search for general symmetric norms via embeddings into product spaces

Computer Science/Discrete Mathematics Seminar I
Topic:Nearest neighbor search for general symmetric norms via embeddings into product spaces
Speaker:Ilya Razenshteyn
Affiliation:Massachusetts Institute of Technology
Date:Monday, February 13
Time/Room:11:30am - 12:30pm/West Building Lecture Hall
Video Link:https://video.ias.edu/csdm/2017/0213-IlyaRazenshteyn

I will show a new efficient approximate nearest neighbor search (ANN) algorithm over an arbitrary high-dimensional *symmetric* norm. Traditionally, the ANN problem in high dimensions has been studied over the $\ell_1$ and $\ell_2$ distances with a few exceptions. Thus, the new result can be seen as a (modest) step towards a "unified theory" of similarity search. At a high level, the new algorithm proceeds by embedding an arbitrary $d$-dimensional symmetric normed space into a $\mathrm{poly}(d)$-dimensional space with a nice *product structure*, which allows to solve the ANN problem via a combination of classical and new algorithmic and geometric tools. The talk is based on a joint work with Alexandr Andoni, Aleksandar Nikolov, and Erik Waingarten.