|
CS Seminar: Marco Pellegrini, December 22, 2004
- Speaker
-
Dr. Marco Pellegrini,
Istituto di Informatica e Telematica (IIT)
- CNR,
Pisa, Italy.
- Date and Time
-
Wednesday, December 22, 2004 at 11:30
- Place
-
Sala Riunioni,
Dipartimento di Matematica,
Università di Parma,
Via D'Azeglio 85/A,
I-43100 Parma
- Title
-
Algoritmi efficienti per problemi di prossimità
in spazi Euclidei ad alta dimensione
- Abstract
-
Dato un insieme (che può rappresentare un data base) di
n punti in uno spazio Euclideo d-dimensionale
possiamo definire un'intera classe di problemi denominati problemi di
prossimità che coinvolgono proprietà metriche
dell'insieme di punti. Un esempio tipico è quello di trovare in
modo efficiente il punto del data base più vicino ad un punto
ulteriore dato. Tale situazione modella molti problemi applicativi in
data mining, pattern recognition, etc. I metodi noti fino alla
metà degli anni '90 hanno prestazioni che si degradano in modo
sensibile al crescere della dimensione d dello spazio. Tale
situazione è stata denomianta la "maledizione della
dimensionalità". Negli ultimi anni si sono trovati nuovi
algoritmi approssimati che riescono ad abbattere alcune delle barriere
di complessità dovute alla dimensione. Nel colloquio verranno
mostrati alcuni dei risultati più interessanti scaturiti dal
lavoro di Piotr Indyk, Rajeev Motwani e Sariel Har-Peled.
- Contact Person
-
Gianfranco Rossi
[Page last updated on December 15, 2004, 20:30:21.]
|