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

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.