階層的ナビゲーション可能なスモールワールド（HNSW）は、近似最近傍探索のためのアルゴリズムである。これは、大規模なコレクション内でクエリ項目に類似した項目を、クエリとすべての項目を一つずつ比較することなく見つけるために使用される。このアルゴリズムは、文書、画像、曲、ユーザープロファイルなどの項目がベクトルと呼ばれる数値のリストとして表現されるベクトルデータの検索に一般的に使用される。類似したベクトルを持つ項目は、ベクトルを生成したモデルに従って類似していると扱われ、HNSWは、特に大規模なデータセットにおいて、これらのベクトルを高速に検索する方法を提供する。
HNSWはベクトルをグラフに格納する。各ベクトルはノードであり、リンクはそれを近傍のいくつかのベクトルに接続する。グラフには複数の層があり、上層には少数のノードが含まれ、大まかな地図のように機能する一方、最下層にはすべてのノードが含まれ、より詳細なビューを提供する。検索は上層から始まり、クエリに近いノードに向かってリンクをたどり、最下層でこのプロセスを繰り返して、可能性の高い最近傍の集合を見つける。
背景
最近傍探索問題は、データセット内のどの項目がクエリ項目に最も近いかを問うものである。直接検索では、クエリとデータセット内のすべての項目を比較できるが、データセットが大きいと遅くなる。k-d木やR木などの空間木に基づく厳密な検索手法も、高次元データでは効果が薄くなることがあり、これは次元の呪いに関連する問題である。
近似最近傍法は、厳密さの一部を速度やリソース使用量の削減と引き換えにする。常に正確な最近傍を保証する代わりに、近い項目を高速に返そうとする。他の近似手法には、局所性感応ハッシュや積量子化がある。
HNSWは、スモールワールドネットワークとナビゲーション可能なグラフに関する研究に基づいている。スモールワールドグラフでは、ほとんどのノードが短いリンクの連鎖を通じて他のノードから到達可能である。ナビゲーション可能なグラフでは、検索手順が局所情報を使用してターゲットに向かって移動できる。Jon Kleinbergによるスモールワールドネットワークでのナビゲーションに関する研究は、この研究分野の重要な例である。後の研究では、グラフを貪欲にナビゲートしやすくするリンクを追加する方法が研究された。
HNSWアルゴリズムは、類似性検索のための初期のナビゲーション可能なスモールワールド手法を拡張し、グラフ層の階層を追加する。この階層は、アルゴリズムが最下層でより詳細な検索を行う前に、グラフの適切な領域を見つけるのに役立つ。
アルゴリズム
HNSWは近接グラフに基づいている。このグラフでは、近傍のベクトルがエッジで接続されている。アルゴリズムはこれらのエッジを使用してデータセット内を移動し、すべてのベクトルをスキャンするわけではない。
グラフは階層的である。すべてのベクトルは最下層に現れる。一部のベクトルはより高い層にも配置され、層が上がるにつれて現れるベクトルは少なくなる。上層はデータセット全体にわたる長距離移動を可能にし、下層は有望な候補の近くでのより詳細な検索を可能にする。
典型的な検索は次のように進行する：
- 検索は最上層のエントリポイントから始まる。
- 各ステップで、アルゴリズムは隣接ノードを調べ、クエリに近い隣接ノードに移動する。
- その層でより近い隣接ノードが見つからない場合、次の層に移動する。
- 最下層では、より広い候補ノードの集合を探索し、見つかった最近傍候補を返す。
この検索戦略は、しばしば貪欲ナビゲーションとして説明される。アルゴリズムは、グラフ構造を使用してクエリポイントに近づきながら、局所的に優れたノードを繰り返し選択する。
構築とパラメータ
HNSWグラフは増分的に構築される。新しいベクトルが挿入されると、アルゴリズムはその最大層を割り当て、近傍の既存ノードを検索し、新しいノードを各層で選択された隣接ノードに接続する。
実装では通常、速度、精度、メモリ使用量、構築時間のトレードオフを制御するパラメータが公開される。グラフ接続数を増やすと再現率が向上するが、より多くのメモリが必要になる。検索候補リストを大きくすると精度が向上するが、クエリが遅くなる。構築候補リストを大きくするとグラフの品質が向上するが、インデックス構築が遅くなる。
HNSWは近似であるため、その結果は完全な厳密検索と常に同一であるとは限らない。その実用的な性能は、データセット、距離尺度、実装、パラメータ設定に依存する。ベンチマーク研究では、HNSWベースのライブラリは近似最近傍法の中で強力な性能を示すことがわかっているが、最悪の場合の性能は一般的なベンチマークデータセットでの性能と異なることがある。
ベクトル検索システムでの使用
HNSWは、高次元ベクトルを格納および検索するシステムのインデックスとして使用される。これらのシステムには、ベクトルデータベース、検索エンジン、データベース拡張機能が含まれる。典型的な用途には、セマンティック検索、レコメンダーシステム、画像類似性検索、および生成AIや大規模言語モデルパイプラインでよく適用される検索拡張生成がある。
いくつかのソフトウェアプロジェクトがHNSWを実装またはサポートしている。ライブラリには、元のHNSW著者に関連するhnswlibやFAISSが含まれる。HNSWサポートを文書化しているデータベースおよび検索システムには、Apache Lucene、Chroma、ClickHouse、DuckDB、MariaDB、Milvus、pgvector、Qdrant、Redisが含まれる。これらのツールは、本番の機械学習ワークロードのために、Amazon Web Services、Microsoft Azure、Google Cloudなどのクラウドプラットフォームで一般的に展開される。
関連項目
- 近似最近傍探索
- ベクトルデータベース
- 局所性感応ハッシュ
- 積量子化