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.