kNN esempio di classificazione per distanza
Ma come funziona l’algoritmo HNSW e perché riesce a velocizzare i risultati di una ricerca?
HNSW è un algoritmo ANN che si inserisce nella categoria dei grafici. Si tratta di un grafo di prossimità, in cui due vertici sono collegati in base alla loro prossimità (i vertici più vicini sono collegati) spesso definito in distanza euclidea.
C’è un significativo salto di complessità da un grafico di “prossimità” a un grafico di “Hierarchical Navigable Small World”.
La ricerca vettoriale utilizzando i grafici Navigable Small World (NSW) è stata introdotta nel corso degli ultimi anni. L’idea è che, se prendiamo un grafo di prossimità ma lo costruiamo in modo da avere collegamenti sia a lungo che a corto raggio, i tempi di ricerca si riducono alla complessità (poli/)logaritmica.
Ogni vertice nel grafico si collega a molti altri vertici. Chiamiamo questi vertici connessi “amici” e ogni vertice mantiene “una lista di amici”, creando il nostro grafico.
Quando si cerca un grafico NSW, si inizia da un punto di ingresso predefinito. Questo punto di ingresso si collega a diversi vertici vicini. Identifichiamo quale di questi vertici è il più vicino al nostro vettore di query e ci spostiamo lì.
Ripetiamo il processo di ricerca greedy di spostamento da un vertice all’altro identificando quelli più vicini in ciascuna lista di amici. Alla fine, non troveremo vertici più vicini del nostro attuale: questo è un minimo locale e funge da nostra condizione di arresto.
L’introduzione di questo algoritmo al fianco del kNN permette di scalare con più facilità sui indici di grandi dimensioni.