cs@parma

Home

People

Projects

Publications

Seminars

Software

Links

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.]

Page maintained by
Enea Zaffanella

Home | People | Projects | Publications | Seminars | Software | Links