[Dmbu-l] Upcoming Seminar: Data Group (Tuesday Oct 6th 11am)
natalir at bu.edu
Mon Oct 5 13:35:19 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...
More information about the Dmbu-l