HNSW（Hierarchical Navigable Small World）は、高次元ベクトルデータを高速かつ高精度に探索するための近似最近傍探索アルゴリズムです。データを多層のグラフ構造で表現し、上層の粗い探索から下層の細かい探索へと段階的に絞り込むことで、大規模なベクトルデータベースにおいて優れた検索性能を発揮します。
HNSWとは
HNSWは、AIモデルが生成した高次元ベクトル間の類似性を高速に判定するための、グラフ型インデックスに基づく近似最近傍探索アルゴリズムです。
詳しく解説
HNSWは、スキップリストの概念をグラフ構造に応用した手法です。データをスモールワールドと呼ばれる、任意のノード同士が短いステップ数で到達できる複数のグラフ層（レイヤー）に分割して管理します。最上層はノード数が少なく、大まかな位置関係を把握するための粗いナビゲーションを行い、下層に行くにつれてノード密度が高くなり、詳細な探索（ベクトル検索）を可能にします。これにより、データの次元数が大きくなっても探索の計算量が対数時間に抑えられ、LLM（大規模言語モデル）のセマンティック検索やRAG（検索拡張生成）などの基盤技術として極めて重要な役割を果たしています。
具体例・使われ方
HNSWは、実世界の多様なベクトルデータベース（Milvus、Pinecone、Qdrant、Chromaなど）の内部エンジンとして採用されています。具体的な適用例としては、ECサイトにおける画像・商品の類似検索システム、数百万件以上の文書からユーザーの質問に類似した記述を瞬時に特定するQ&Aシステム、ユーザーの行動履歴に基づいたレコメンデーションエンジンなどが挙げられます。
似た用語との違い
従来の代表的なアルゴリズムであるIVF（倒置ファイルインデックス）と比べると、HNSWはインデックスの構築時間やメモリ消費量が大きくなる傾向があります。しかし、検索の精度と速度のトレードオフにおいては、HNSWの方が圧倒的に高速かつ高精度なベクトル検索が可能です。また、総当たりで全データとの距離を計算するブルートフォース検索は、100%の精度（完全な最近傍探索）を保証するものの、データ量に比例して検索時間が爆発的に増加するため、大規模データに対してはHNSWのような近似最近傍探索が必須となります。
注意点
HNSWの最大のデメリットは、メモリ消費量が非常に大きい点です。グラフ構造のリンク情報をすべてメモリ上に保持する必要があるため、データ量が増加すると大容量のRAMが求められます。また、インデックスの構築（グラフの生成・結合プロセス）に多くのCPUリソースと時間を要するため、リアルタイムにデータが頻繁に更新・追加されるシナリオでは、インデックスの再構築コストがボトルネックになることがあります。