HNSW Hierarchical Navigable Small World
Hierarchical Navigable Small World — het dominante graafgebaseerde algoritme voor benaderd zoeken naar nabije buren (approximate nearest neighbor) tussen vectoren. Bouwt een meerlagige ‘small world’-graaf waarin de zoektocht van grove naar fijne lagen springt. Snel en nauwkeurig, maar geheugenhongerig.
Werking: vectoren zijn verbonden in een graaf waarin elk knooppunt buren heeft; de bovenste laag is ijl (lange sprongen), de onderste dicht (fijnafstelling). Een zoekopdracht begint hoog, ‘glijdt’ richting het doel en verfijnt naar beneden → logaritmische zoektijd. Parameters: M (buren per knooppunt) en ef (zoekbreedte) bepalen de balans tussen snelheid, geheugen en nauwkeurigheid. Voordeel: uitstekende recall bij hoge snelheid, incrementele inserts. Nadeel: hoog geheugengebruik (de hele graaf in RAM) en een duurdere opbouw dan IVF. De standaardkeuze in pgvector, Qdrant, Weaviate en FAISS voor de meeste workloads. Te onderscheiden van IVFFlat (clustergebaseerd, minder geheugen maar meestal lagere recall). Het meestgebruikte vectorindextype in 2024.