Look Who it Was Random video

[Коллоквиум]: Approximate Nearest Neighbor Search: Beyond Locality-Sensitive Hashing

2,603 views · Published 3 February 2015 · 52:19 · Indexed 8 October 2026

Channel: ФКН ВШЭ · 2015 · Education

Watch on YouTube

Докладчик: Илья Разенштейн (Ilya Razenshteyn) - MIT (язык доклада - русский).

In the Approximate Nearest Neighbor problem (ANN), we are given a set P of n points in a d-dimensional space, and the goal is to build a data structure that, given a query point q, reports any point from P that is approximately closest to q.
Locality-Sensitive Hashing (LSH) is by now a standard technique for solving the ANN problem. In my talk I will define LSH and show several constructions of good hash families. Then I will state some limitations of LSH and describe a recent line of research that provides data structures for ANN that are provably (substantially) better than what LSH could possibly give.
The talk is partially based on a joint work with Alexandr Andoni (Simons Institute, previously Microsoft Research Silicon Valley). See http://www.ilyaraz.org/optimal_lsh.pdf for the paper.

More from this channel