[Colloquium] TTI-C Talk: Alexandr Andoni (MIT)

[Julia MacGlashan]

When:              TOMORROW: Wednesday, February 18 @ 11:00am (lunch will be
provided after talk)

Where:            TTI-C Conference Room #526, 6045 S Kenwood Ave, 5th Floor

Who:                Alexandr Andoni (MIT)

Title:                 Nearest Neighbor Search: Old and New Approaches


When working with massive datasets, a frequently recurring problem is that
of Nearest Neighbor Search (NNS) in high-dimensional spaces. In this
problem, the goal is to preprocess a set of objects (e.g., images), so that
later, given a new query object, one can efficiently return the object most
similar to the query. This problem is of significant importance in several
areas such as machine learning, information retrieval, image/video/music
clustering, code clone detection, etc.

We develop new algorithms for NNS under several important distances, via
both old, tested paradigms as well as newly developed paradigms. In the
first part, we give a new near-optimal algorithm for NNS under the classical
Euclidean distance. This algorithm is based on Locality-Sensitive Hashing, a
scheme that has already been successfully used in a number of practical
scenarios. Our algorithm is near-optimal in the class of such hashing
algorithms.

In the second part, we propose a new approach to designing NNS algorithms,
for the scenarios where the above hashing approach is provably impossible.
Our approach has already been applied for designing NNS under a variant of
edit distance, yielding an exponential improvement in approximation over
what is even possible via the old approaches. Furthermore, the key idea,
embedding into product metrics, has also been used for other applications,
such as approximating the edit distance between two strings in near-linear
time.

Contact:          Julia Chuzhoy, TTI-C		cjulia at tti-c.org
834-2490


-------------- next part --------------
A non-text attachment was scrubbed...
Name: winmail.dat
Type: application/ms-tnef
Size: 8078 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090217/ff1a3259/attachment.bin