[cs at parma seminars] Seminario di Informatica

[Gianfranco Rossi]

[Con preghiera di diffusione e scuse per l'eventuale ricezione di
copie multiple.]

------------------------------------------------------------------

DATA:
       Mercoledi' 22/12/2004, ore 11:30

RELATORE:
       Marco Pellegrini
       IIT - CNR
       Area della Ricerca
       Pisa

TITOLO
       Algoritmi efficienti per problemi di prossimita' in
       spazi Euclidei ad alta dimensione

LUOGO:
        Sala riunioni (I piano)
        Dipartimento di Matematica, Universita' di Parma
        C.so M.D'Azeglio 85/A, PARMA


SOMMARIO:

Dato un insieme (che puo' rappresentare un data base) di
n punti in uno spazio Euclideo d-dimensionale
possiamo definire un'intera classe di problemi
denominati problemi di prossimita' che coinvolgono properita'
metriche dell'insieme di punti. Un esempio tipico e' quello di
trovare in modo efficiente il punto del data base piu' vicino ad
un punto ulteriore dato. Tale situazione modella molti problemi
applicativi in data mining, pattern recognition, etc.
I metodi noti fino alla meta' degli anni '90
hanno prestazioni che si degradano in
modo sensibile al crescere della dimensione d dello spazio. Tale
situazione e' stata denomianta la "maledizione della
dimensionalita'". Negli ultimi  anni si sono trovati nuovi
algoritmi approssimati che riescono ad abbattere alcune delle
barriere di complessita' dovute alla dimensione. Nel colloquio
verranno mostrati alcuni dei risultati piu' interessanti scaturiti
dal lavoro di Piotr Indyk, Rajeev Motwani e Sariel Har-Peled.


RIF.:
Gianfranco Rossi
Dipartimento di Matematica
Universita' di Parma
Via M.D'Azeglio, 85/A
43100 PARMA (I)
http://www.math.unipr.it/~gianfr/