Computazione Distribuita di Approximate Nearest Neighbors

Abstract

Questo lavoro si pone l'obiettivo di essere una guida per utenti e aziende che necessitano di eseguire ricerche nearest neighbors efficienti e precise su dataset multi-dimensionali di grandi dimensioni. Per far ciò è stata introdotta una famiglia di algoritmi chiamati Approximate Nearest Neighbors, i quali permettono ricerche approssimate fornendo un trade-off tra precisione e velocità di ricerca. Il lavoro si concentra sullo studio delle librerie Free and Open Source più conosciute ed utilizzate e, per ognuna di esse, sono stati analizzati gli indici principali e più efficienti. Poiché queste soluzioni sono native su singola macchina e la loro capacità di scalare al crescere del dataset è limitata dalla quantità di RAM disponibile, sono state presentate anche soluzioni distribuite, le quali permettono di scalare in maniera orizzontale. Una volta studiato lo stato dell'arte è stato scritto del codice con lo scopo di eseguire le librerie su un dataset fornito da Wikimedia Foundation, composto da 6.4 millioni di immagini. Sono state, quindi, analizzate caratteristiche come la documentazione e la maturità di una libreria per quanto riguarda l'utilizzo in ambienti di produzione. In seguito a queste implementazioni sono stati eseguiti vari test cercando di coprire la maggior parte degli use-case, confrontando e descrivendo le capacità di ogni indice. Abbiamo, infine, scritto una guida in grado di rispondere alla maggior parte dei bisogni di utenti e aziende per la scelta delle librerie, degli indici e dei parametri da utilizzare a seconda del dataset di riferimento ottenendo precisione elevata e tempi di esecuzione nell'ordine di pochi millisecondi.

This work aims to be a guide for users and companies who need to perform efficient and precise nearest-neighbor searches on large multi-dimensional datasets. To do this we introduced a family of algorithms called Approximate Nearest Neighbors, which allow approximate searches by providing a trade-off between accuracy and search execution speed. The work focuses on the study of the best-known and most used Free and Open Source libraries and, for each of them, we analyzed the main and most efficient indexes. Since these solutions are native on a single machine and their ability to scale as the dataset grows is limited by the amount of available RAM, distributed solutions were also presented, which allow horizontal scaling. Once the state of the art had been studied, code was written to run the libraries on a dataset provided by the Wikimedia Foundation, made up of 6.4 million images. Characteristics such as the documentation and maturity of the libraries with regard to use in production environments were therefore analyzed. Following these implementations, various tests were performed trying to cover the majority of use cases, comparing and describing the capabilities of each index. Finally, we have written a guide capable of responding to most of the needs of users and companies for the choice of libraries, indexes and parameters to be used depending on the reference dataset, obtaining high accuracy and low execution times, in the order of a few milliseconds.