Faiss e la K-Nearest Neighbour Search

La k-Nearest Neighbour Search, nell’ambito dell’analisi dei dati, è un tipo di ricerca che si pone il problema di individuare i k elementi più vicini ad uno dato. Dal punto di vista teorico lo si può vedere come uno spazio vettoriale, formato da dei vettori di dimensione fissata, in cui si vuole individuare un numero k di vettori più vicini ad uno fornito. La k-NNS copre un problema molto ricorrente e viene sviluppata da diverse aziende tra le quali colossi delle Big Tech come Facebook e Google. La tesi prende in analisi Faiss che è l’algoritmo di k-NNS di Facebook. Faiss presenta una struttura incentrata sugli indici in cui ogni Index avrà delle caratteristiche specifiche per il salvataggio dei dati presenti nei vettori e il metodo di ricerca. Queste caratteristiche spaziano dalla compressione dei vettori per ridurre la dimensione al diverso modo di creazione della struttura di spazio vettoriale. La tesi pone accento sull’analisi degli indici Flat e HNSW.