[cs-talks] TODAY: Ilya Razenshteyn MCS148 11am

Natali Ruchansky natalir at bu.edu
Tue Oct 6 07:36:46 EDT 2015

*Data Group Seminar*
*Practical** and Optimal LSH for Angular Distance*
*Ilya Razenshteyn, MIT*
*Tuesday, October 6th, 2015 at 11am in MCS 148*

Locality-Sensitive Hashing (LSH) is a powerful technique for
​ ​
the approximate nearest neighbor search (ANN) in high dimensions. In this
talk, I will describe a recent result that gives an *optimal* LSH family
for Cosine Similarity (aka Angular distance, aka Euclidean distance on a
sphere). Unlike known optimal constructions [Andoni, Indyk, Nguyen,
Razenshteyn 2014] [Andoni, Razenshteyn 2015], the new one
​ ​
is practical, which is demonstrated by experiments on real and synthetic
Along the way, I will try to debunk two popular myths about LSH:
 * LSH-based data structures consume too much memory and are thus
 * Optimal LSH constructions are too complicated to be made practical.

No prior knowledge about LSH is required: I will start the talk with
defining LSH and explaining how it can be used to solve ANN.
The talk is based on a NIPS 2015 paper joint with Alexandr Andoni, Piotr
​ ​
Indyk, Thijs Laarhoven and Ludwig Schmidt. The preprint is available at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/cs-talks/attachments/20151006/707dcd2d/attachment.html>

More information about the cs-talks mailing list