Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Exact and Approximate Nearest Neighbor Queries in Euclidean Space
Speaker:Edgar Ramos
coming from:Max-Planck-Institut für Informatik, Saarbrücken, Germany
Speakers Bio:
Event Type:AG1 Advanced Mini-Course
Visibility:D1, D2
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Thursday, 23 July 98
Time:13:30
Duration:90 min
Location:Saarbrücken
Building:46.1
Room:024
Abstract
The nearest neighbor problem consists in constructing a data structure for a

data base P of n points in a metric space X so that given a query point q in X,
the point in P closest to q can be determined quickly. I consider only the case
in which X is the d-dimensional Euclidean space (with Euclidean metric).
Unfortunately, to achieve a fast query time an impractically large amount of
space is needed, and consequently there is interest in the approximate version
of the problem in which a parameter epsilon is specified and it is sufficient
to find a point in P no farther than the nearest neighbor by a factor 1+epsilon.
Because of the practical importance of the problem, there has been much work on
heuristics; however, I will concentrate on solutions that provide a performance
guarantee.

The main goal will be to present some recent work on approximate nearest neighbor
(third lecture) that achieves query time polynomial in d and log n while using
space polynomial in d and n (for constant epsilon). As a point of reference, I
will present previous work on the exact version (first lecture) and previous work
on the approximate version (second lecture).

Lecture 3: Approximate version: Algorithms of Indyk and Motwani and of
Kushilevitz, Ostrovsky and Rabani.

Contact
Name(s):Stefan Schirra
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Keywords:Nearest Neighbor Queries; Approximation Algorithms; Computational Geometry
Note:
Attachments, File(s):