|
СЕМИНАРЫ |
Коллоквиум Факультета компьютерных наук НИУ ВШЭ
|
|||
|
Approximate Nearest Neighbor Search: Beyond Locality-Sensitive Hashing Ilya Razenshteyn Massachusetts Institute of Technology |
|||
Аннотация: 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. |