HNSW
Hierarchical Navigable Small World: l'algoritmo a grafo dominante per la ricerca approssimata dei vicini più prossimi tra vettori. Costruisce un grafo «small world» a più livelli in cui la ricerca scende dai livelli grossolani a quelli fini. Veloce e preciso, ma vorace di memoria.
Meccanismo: i vettori sono collegati in un grafo in cui ogni nodo ha dei vicini; il livello superiore è rado (salti lunghi), quello inferiore denso (rifinitura). La ricerca parte dall'alto, «plana» verso il bersaglio e affina scendendo, con tempo logaritmico. I parametri M (vicini per nodo) ed ef (ampiezza della ricerca) regolano il compromesso tra velocità, memoria e accuratezza. Pregi: ottimo recall ad alta velocità, inserimenti incrementali. Costo: molta memoria (l'intero grafo in RAM) e una costruzione più onerosa rispetto a IVF. È la scelta predefinita in pgvector, Qdrant, Weaviate e FAISS per la maggior parte dei carichi. Da non confondere con IVFFlat (basato su cluster, meno memoria ma di solito recall inferiore). Nel 2024 era il tipo di indice vettoriale più diffuso.