B O S T O N   U N I V E R S I T Y
                      Computer Science Department
                          C O L L O Q U I U M
                     Wednesday, December 4, 3:00 PM
                       (Coffee served at 2:45 PM)
                         Seminar Room / MCS 135

                               Piotr Indyk
                                   MIT


    Approximate Algorithms for High-Dimensional Geometric Problems


Consider the following problem: given a database of points in a
multidimensional space, construct a data structure which given any query
point finds the database point(s) closest to it. This problem, called
nearest neighbor search, has been of great importance to several areas of
computer science, including pattern recognition, databases, vector
compression, computational statistics and data mining. Many of the above
applications involve data sets whose size and dimensionality are very
large. Therefore, it is crucial to design algorithms that scale well with
the database size as well as with the dimension.

The aforementioned nearest neighbor problem is an example of a large class
of *proximity problems*. Apart from the nearest neighbor, the class
contains problems like closest pair, diameter (or furthest pair), minimum
spanning tree and clustering.  Since these problems are ubiquitous, they
have been investigated in computer science for a long while (e.g., in
computational geometry). As a result of this research effort, many
efficient solutions have been discovered for the case when the points lie
in a space of small dimension. Unfortunately, their running time grows
exponentially with the dimension. It is conjectured that this exponential
dependence on dimension is inevitable. However, this does not preclude the
existence of efficient *approximate* algorithms for such problems. Indeed,
many such algorithms have been discovered during the last few years.

In this talk I will present an overview of the research in the area of
approximate algorithms for high-dimensional problems, as well as state
several open problems.

Host: Leo Reyzin

-------------------------------------------------------------------------
For colloquium info, including directions, see
http://cs-www.bu.edu/colloquium
-------------------------------------------------------------------------