HNSW Hierarchical Navigable Small World
Hierarchical Navigable Small World — den dominerande grafbaserade algoritmen för approximativ närmaste-granne-sökning bland vektorer. Bygger ett flerlagers "small world"-grafnät där sökningen hoppar från grovt till fint lager. Snabb och träffsäker, men minneshungrig.
Mekanik: vektorer länkas i en graf där varje nod har grannar; översta lagret är glest (långa hopp), nedersta tätt (finjustering). En sökning startar högt upp, "glider" mot målet och förfinar nedåt → logaritmisk söktid. Parametrar: M (antal grannar per nod) och ef (sökbredd) styr avvägningen hastighet/minne/träffsäkerhet. Vinst: utmärkt recall vid hög hastighet, inkrementella insättningar. Avvägning: hög minnesåtgång (hela grafen i RAM) och dyrare bygge än IVF. Standardval i pgvector, Qdrant, Weaviate, FAISS för de flesta arbetslaster. Skiljer sig från IVFFlat (klusterbaserat, mindre minne men oftast lägre recall). Den vanligaste vektorindex-typen 2024.