HNSW
Hierarchical Navigable Small World。ベクトルの近似最近傍探索で主流のグラフ型アルゴリズムだ。多層の「スモールワールド」グラフを粗い層から細かい層へたどる。高速で精度も高いが、メモリを食う。
仕組みはこうだ。ベクトルをノードとしてグラフでつなぎ、最上層は疎（長い跳躍）、最下層は密（細かい調整）にする。探索は上層から始まり、目標に向かって滑り降りながら絞り込むので、検索時間は対数オーダーになる。パラメータはM（ノードあたりの近傍数）とef（探索幅）で、速度・メモリ・精度のトレードオフを決める。
利点は高い再現率と速度、そして逐次的な挿入に強いこと。欠点はグラフ全体をRAMに載せるためメモリ消費が大きく、構築もIVFより重いことだ。pgvector、Qdrant、Weaviate、FAISSでは多くの用途で既定の選択肢になっている。クラスタ方式のIVFFlatはメモリが少なくて済むが、再現率は概ね劣る。2024年時点で最も一般的なベクトルインデックスだった。