[Colloquium] REMINDER: 2/10 Young Researcher Seminar Series: Ilya Razenshteyn, MIT
Mary Marre
mmarre at ttic.edu
Tue Feb 9 15:43:07 CST 2016
When: Wednesday, February 10th at 11am
Where: TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526
Who: Ilya Razenshteyn, MIT: CSAIL
Title: Locality-Sensitive Hashing and Beyond
Abstract:
Locality-Sensitive Hashing (LSH) is a powerful technique for the
approximate nearest neighbor search (ANN) in high dimensions.
In this talk I will present two recent results.
1) I will show a data structure for ANN for the Euclidean distance
that provably
outperforms the best possible LSH-based data structure. We proceed via
designing a good *data-dependent* hash family.
2) I will show a practical and optimal LSH family for the cosine similarity
(a.k.a. Euclidean distance on a sphere). It substantially outperforms the
celebrated Hyperplane LSH family. 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.
The talk is based on two papers: arXiv:1501.01062 (joint with Alexandr Andoni,
STOC 2015) and arXiv:1509.02897 (joint with Alexandr Andoni, Piotr Indyk,
Thijs Laarhoven and Ludwig Schmidt, NIPS 2015).
Host: Yury Makarychev, yury at ttic.edu <yury at ttic.edu>
*************************
The TTIC Young Researcher Seminar Series (
http://www.ttic.edu/young-researcher.php) features talks by Ph.D. students
and postdocs whose research is of broad interest to the computer science
community. The series provides an opportunity for early-career researchers
to present recent work to and meet with students and faculty at TTIC and
nearby universities.
The seminars are typically held on Wednesdays at 11:00am in TTIC Room 526.
For additional information, please contact Matthew Walter (mwalter at ttic.edu
).
Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL 60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160209/58467f06/attachment.htm
More information about the Colloquium
mailing list