HNSWLibは、近似最近傍探索のための階層的ナビゲーション可能な小世界（HNSW）アルゴリズムを実装した、ヘッダーのみのC++ライブラリです。このライブラリは、クエリ項目を個別にすべて比較することなく、大規模なベクトルデータのコレクションからクエリ項目に類似した項目を見つけるように設計されています。これは、速度とスケーラビリティが重要となる機械学習システム、人工知能アプリケーション、ベクトルデータベースで一般的に使用されています。
HNSWLibが実装するHNSWアルゴリズムは、ベクトルを多層グラフ構造に格納します。各ベクトルはノードとなり、リンクがそれを近傍のベクトルに接続します。上位層には少数のノードが含まれ、粗い地図として機能しますが、最下層には詳細な検索のためのすべてのノードが含まれます。検索は上位層で開始され、クエリに近いノードに向かってリンクをたどり、その後、下位層でこのプロセスを繰り返して、可能性の高い最近傍のセットを特定します。
背景
最近傍探索問題は、データセット内のどの項目がクエリ項目に最も近いかを問うものです。直接検索ではクエリをすべての項目と比較するため、大規模なデータセットでは遅くなります。k-d木やR木などの空間ツリーを使用する正確な方法は、次元の呪いにより高次元データでは効果を失います。近似最近傍法は、正確さと速度をトレードオフし、絶対的に最も近いものを保証するのではなく、近い項目を迅速に返します。
HNSWは、スモールワールドネットワークとナビゲーション可能なグラフに関する研究に基づいています。スモールワールドグラフでは、ほとんどのノードが短いリンクの連鎖で接続されています。ジョン・クラインズバーグによるスモールワールドネットワークのナビゲーションに関する研究は、貪欲にナビゲーションしやすいグラフにするリンクを追加する後の研究に影響を与えました。HNSWアルゴリズムは、以前のナビゲーション可能なスモールワールド手法を拡張し、グラフ層の階層を追加することで、詳細な検索の前に適切な領域を見つけやすくしています。
アルゴリズム
HNSWLibは、近傍のベクトルがエッジで接続された近傍グラフを使用します。アルゴリズムは、すべてのベクトルをスキャンするのではなく、これらのエッジを使用してデータセットを移動します。グラフは階層的です。すべてのベクトルは最下層に現れますが、一部のベクトルは層が上がるにつれてベクトル数が少なくなる上位層にも現れます。上位層は長距離の移動を可能にし、下位層は有望な候補の近くでの詳細な検索を可能にします。
典型的な検索は、最上位層のエントリポイントから開始されます。各ステップで、アルゴリズムは隣接ノードを調べ、クエリに近いノードに移動します。その層にこれ以上近い隣接ノードがない場合、次の層に降下します。最下層では、より広い候補セットを探索し、見つかった最も近い候補を返します。この貪欲なナビゲーションは、クエリポイントに近づくために局所的に優れたノードを繰り返し選択します。
構築とパラメータ
HNSWグラフは段階的に構築されます。新しいベクトルを挿入するとき、アルゴリズムはその最大層を割り当て、近くの既存ノードを検索し、新しいノードが現れる各層で選択された隣接ノードに接続します。実装では、速度、精度、メモリ使用量、構築時間のトレードオフを制御するパラメータが公開されています。グラフの接続数を増やすと再現率は向上しますが、より多くのメモリが必要になります。検索候補リストを大きくすると精度は向上しますが、クエリが遅くなります。構築候補リストを大きくするとグラフの品質は向上しますが、インデックス構築が遅くなります。
HNSWは近似であるため、結果は正確な検索と異なる場合があります。実際のパフォーマンスは、データセットの特性、距離尺度、実装品質、パラメータ設定に依存します。ベンチマーク研究では、HNSWベースのライブラリは近似最近傍法の中でも強力なパフォーマンスを発揮することがわかっていますが、最悪の場合のパフォーマンスは一般的なベンチマーク結果と異なることがあります。
ベクトル検索システムでの使用
HNSWLibは、高次元ベクトルを格納および検索するシステム（ベクトルデータベース、検索エンジン、データベース拡張機能を含む）のインデックスとして使用されます。典型的なアプリケーションには、セマンティック検索、レコメンダーシステム、画像類似性検索、検索拡張生成が含まれます。このライブラリは、元のHNSW著者に関連付けられており、本番環境で広く採用されています。
いくつかのソフトウェアプロジェクトがHNSWを実装またはサポートしています。ライブラリにはHNSWLibとFAISSが含まれます。HNSWサポートを文書化しているデータベースおよび検索システムには、Apache Lucene、Chroma、ClickHouse、DuckDB、MariaDB、Milvus、pgvector、Qdrant、Redisが含まれます。これらのシステムは、大規模言語モデル検索から生成AIパイプラインまでのアプリケーションで、高速な近似検索のためにHNSWを活用しています。
関連項目
- 近似最近傍探索
- ベクトルデータベース
- 局所性鋭敏型ハッシュ
- 積量子化