[Colloquium] 2/10 Young Researcher Seminar Series: Ilya Razenshteyn, MIT

[Mary Marre]

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/20160205/98470e2f/attachment.htm