[Dmbu-l] Upcoming Seminar: Data Group (Tuesday Oct 6th 11am)

Natali Ruchansky 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*


*ABSTRACT*:
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
data.
Along the way, I will try to debunk two popular myths about LSH:
 * LSH-based data structures consume too much memory and are thus
impractical;
 * 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
http://arxiv.org/abs/1509.02897
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/dmbu-l/attachments/20151005/bfbd5e31/attachment.html>


More information about the Dmbu-l mailing list