navigable

定義

グラフの上を辺づたいに辿るだけで、目的の点まで少ない手数で到達できる性質を指す語。HNSW などの近似最近傍探索は、この性質を持つ小世界グラフを多層に重ね、全点との距離計算を避けて検索を高速化している。全探索の代わりに構造を作って歩く、という発想を表す。

論文題名での読み方

HNSWの構造説明

この語が出てくる解説

• 【実装】ベクトルDBを自作する — 線形走査からHNSWへEfficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• ハッシュと近傍探索 — ベクトル検索の下地Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• グラフアルゴリズムを1から — 最短経路とその応用Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs