Algoritmi per la ricerca per somiglianza in dati a bassa dimensionalità

Il problema del Near Neighbor (NN) è uno dei problemi più studiati nell’analisi dei dati, infatti negli ultimi decenni si è visto una enorme crescita nella ricerca di soluzioni che possano risolvere efficientemente il problema o in modo approssimato. Dato un insieme di dati rappresentati nello spazio e definito uno tra essi, la questione consiste nel individuare un dato che abbia una certa somiglianza al dato iniziale, ovvero trovare un dato che sia fisicamente vicino all’interno della rappresentazione. La ricerca per somiglianza risulta un problema alquanto interessante in quanto le diverse soluzioni vengono adoperate in molti settori. Infatti, il problema è soggetto di continuo studio poiché le soluzioni fin’ora trovate si dividono in due gruppi, bassa ed alta dimensionalità. In particolare, si sta cercando di trovare un algoritmo che possa unire le soluzioni delle due categorie. Questa tesi si concentra sul problema della bassa dimensionalità e si illustrano alcune soluzioni adoperate tutt’oggi.