From:                     Kendra Smith

Sent:                      Thursday, February 03, 2000 12:45 AM

To:                         M?crosöft Research Tech Talk, Sem. Notice

Cc:                         Kendra Smith

Subject:                 UW-CSE Colloq / 2-17-2000 / Indyk / Stanford / High-Dimensional Computational Geometry

UW-CSE Colloq / 2-17-2000 / Indyk / Stanford / High-Dimensional Computational Geometry

 

*NOTE* This lecture will be broadcast live via the Internet. See

http://www.cs.washington.edu/news/colloq.info.html for more information.

 

UNIVERSITY OF WASHINGTON

Seattle, Washington 98195

 

Department of Computer Science and Engineering

Box 352350

(206) 543-1695

 

COLLOQUIUM

 

SPEAKER:      Piotr Indyk, Stanford University

 

TITLE:          High-Dimensional Computational Geometry

 

DATE:           Thursday, February 17, 2000

 

TIME:           3:30 pm

 

PLACE:                   134 Sieg Hall

 

HOST:           Martin Tompa

 

ABSTRACT:

 

Computing with massive and high-dimensional data is critical to a large

and diverse set of applications, including multimedia and hyperlinked

databases (the World Wide Web being the prime example), data mining,

machine learning, computational statistics, and vector

quantization/compression. Improving performance in the above applications

has been an important research goal in a variety of fields, including

Computational Geometry and Databases.  Unfortunately, the running times of

the algorithms discovered so far depend exponentially on the dimension,

which usually makes them inefficient in the aforementioned applications.

 

In my talk, I will show that it is possible to overcome this ``curse of

dimensionality'' and obtain algorithms that are efficient in theory and

practice, as long as one is satisfied with approximate answers.  The

algorithms employ novel techniques which are very different from the ones

used in standard (low-dimensional) Computational Geometry. In particular,

I will describe/address the following:

 

  - approximate nearest-neighbor algorithms for normed spaces with running

    time *polynomial* in dimension and logarithmic or sublinear in the

    data size

 

  - algorithmic reductions to the above problem from a large set of

    Computational Geometry problems, including closest pair, diameter,

    minimum spanning tree, facility location and other forms of clustering

 

  - extension of the above algorithms to spaces which are not normed

    via embeddings

 

  - efficient algorithms in general metric spaces, and

 

  - applications of the above techniques to problems outside of

    Computational Geometry

 

As a ``proof-of-concept'', I will present initial results of an ongoing

project on clustering the Web.

 

Refreshments to follow.

 

Email: talk-info@cs.washington.edu

Info: http://www.cs.washington.edu