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.