Study and testing of the Falconn++ algorithm

The problem of nearest-neighbour search (NNS) is one of the most studied topics of data analysis, seeing application in numerous fields, e.g., recommendation systems, web search, machine learning, and computer vision. There are several efficient solutions to address the problem of NNS in low dimensions, but to overcome the ”curse of dimensionality” and build efficient solutions for high dimensions, researchers have opted to use approximated approaches. This thesis analyses Falconn++, a locality-sensitive filtering algorithm for the problem of approximate nearest-neighbour search on angular distance. The strength of Falconn++ lies in a filtering mechanism based on the theory of concomitants of extreme order statistics (CEOs) that achieves higher quality candidates compared to previous hashing-based solutions.

La classe di problemi di nearest-neighbour search (NNS) è uno degli argomenti più studiati nell’analisi di dati, con applicazioni in numerosi ambiti quali recommendation systems, web search, machine learning e computer vision. Esistono diverse soluzioni efficienti al problema della NNS in basse dimensioni, ma per costruire soluzioni che affrontino il problema in grandi dimensioni, superando così la ”maledizione delle dimensioni”, la ricerca si è diretta verso approcci approssimati. In questa tesi analizziamo Falconn++, un algoritmo di locality-sensitive filtering per risolvere la classe di problemi di nearest-neighbour approssimato in distanza angolare. La caratteristica principale di Falconn++ è un meccanismo di filtraggio basato sulla teoria dei concomitanti dell’estremo ordine (CEOs) che garantisce candidati di miglior qualità rispetto alle precedenti soluzioni basate sull’hashing.