Hierarchical Navigable Small Worldとは何ですか？

Hierarchical Navigable Small World（HNSW、「階層的ナビゲーション可能なスモールワールド」）は、コンピュータサイエンスや情報検索システムで大規模なデータセットを効率的に検索するために使用される強力なアルゴリズムです。ベクトルデータベースでデータを整理することで、高次元空間の特定のデータ点に近い最近傍点を見つけるという課題に対処します。

HNSW について詳しく説明する前に、ナビゲート可能なスモールワールドグラフの基礎概念を理解しておくことが重要です。これは HNSW の構成ブロックであるためです。

スモールワールドネットワークとスキップリストが検索精度を向上させる仕組み
HNSW の背景
HNSW の主要な概念
HNSW を構築する方法
プロセスを検索
グラフ構造
HNSW のユースケース
HNSW を構築する方法
結論

スモールワールドネットワークとスキップリストが検索精度を向上させる仕組み

ナビゲーション可能なスモールワールドグラフとは、ほとんどの点（または「ノード」）が、ほんの数ステップで任意の2点間を効率的に移動できるように接続されたネットワーク構造です。「スモールワールド」プロパティとして知られるこの特性は、大規模なネットワークであっても、限られた数のジャンプで離れたノードを接続できることを意味します。これは、ソーシャルネットワークに例えられます。何千人もの友人がいても、共通の知人を数人介するだけで、世界中の誰かとつながることができることがよくあります。この構造は、ソーシャルメディアや通信ネットワークのようなシステムにとって不可欠であり、点間を素早く移動することが優先順位となります。しかし、検索をさらに効率的にするために、特に膨大なデータセットでは、追加のレイヤーが導入されることがあります。

ここでスキップリストが役立ちます。スキップリストは、上位のレイヤーが大まかな接続を提供し、下位のレイヤーが具体的で詳細なリンクを含むように情報を整理することで、検索を高速化する階層型データ構造です。この階層型の設定により、検索では不要な手順を回避し、データセットの一部を「スキップ」して、関連情報をすばやく絞り込むことができます。

HNSW グラフは、スモールワールドのプロパティとスキップリストの階層的なレイヤー化の両方を組み合わせています。このアルゴリズムは、上位レイヤーを迅速で粒度の粗い探索に使用し、より細かい下位レイヤーで詳細な検索を処理することで、構造の段階性を活用します。HNSW は、近隣ノード間のデータ構造と距離メトリクスに基づいて最も類似したノードへのパスを最適化することで、大規模なデータセット内を効率的かつ正確にナビゲートできます。この粗粒度から詳細へと進む検索機能の組み合わせにより、HNSW は従来のアルゴリズムでは実行が困難な、複雑で高次元の検索タスクに対応する強力なツールとなります。

HNSW の背景

階層的ナビゲーション可能なスモールワールドは高次元の類似性検索に使用され、大規模な多次元データセット内の近傍を効率的に見つける能力で際立っています。2016年の HNSW 論文で初めて導入され、Apache Lucene プロジェクト内の1つを含め、複数の実装があります。

HNSW は、各レイヤーが簡略化されたナビゲーション可能なスモールワールドネットワークである、多層グラフ構造を作成することによって動作します。この構造により、主にスキップリストを使用することで、広大な高次元データ空間であっても、非常に高速かつ正確な検索が可能になります。その基盤は近似最近傍探索（ANN）に関連しています。ANN はベクトル類似性検索によく使用され、ツリー、ハッシュ、グラフの 3 つの異なるカテゴリに分けることができます。HNSW は、より具体的には近接性グラフとして分類できます。このグラフでは、2 つの頂点がその近接性に基づいてリンクされます（近い頂点ほどリンクされます）。

HNSW の主要な概念

HNSW は、スキップリストとナビゲーション可能なスモールワールドという2つのアルゴリズムを融合させた結果です。HNSW を理解するには、これらの構成アルゴリズムについての知識が不可欠です。スキップリストとスモールワールドの両方の複雑さについて深く掘り下げてみましょう。

スキップリストとは何ですか？

名前が示すように、スキップリストはリンクリストのデータ構造から着想を得ており、その拡張と見なすことができます。1990年に David Pugh によって考案されたスキップリストは、従来のリンクリストに代わる最適化された代替手段として機能します。

スキップリストが必要になるのは、リンクされたリストの O(n) 検索時間複雑性によるものです。これは、迅速な実行を優先するシナリオでは最適ではない可能性があります。そのため、より効率的なリンクされたリストのアルゴリズムが不可欠になります。スキップリストは、O(log n) の予想時間複雑性を誇り、ランダムアクセスシナリオでリンクされたリストを大幅に上回ります。各レベルに複数のノードを備えた階層構造により、最悪のスペース複雑性は O(n log n) になります。ここで、n はスキップリストの最下位レベルにあるノードの数を表します。

階層的ナビゲーション可能なスモールワールドの概念とは？

階層的ナビゲーション可能なスモールワールドとは、複雑な情報の階層をユーザーが簡単にナビゲートできるようにする、構造化および整理されたネットワークまたはシステムを指します。これは、特定のコンテンツを簡単に検索してアクセスできるように情報を整理し、表示するための方法です。

HNSW の「スモールワールド」プロパティは、エントリポイントに基づいて、少数のホップを使用してデータセット内の任意のデータポイントから他のデータポイントに到達する能力を指します。データポイントを注意深く整理し、それらの間に接続を作成することで、HNSW は高次元空間であっても検索プロセスがデータセットを効率的にトラバースできるようにします。

An illustration of a navigable small-world graph

HNSW を構築する方法

HNSW グラフでは、階層型グラフ構造を通じて効率的な近似最近傍探索（ANN）が可能になります。このアプローチでは、各レベルがその下位レベルを簡略化して表現する階層システムを作成することで、グラフ理論の力を活用し、大規模なデータセットを迅速かつ正確に探索します。

HNSW の構築には、HNSW インデックスの構築、ベクトルのクエリ、ベクトル検索の実行という3つの主要なステップが含まれます。

HNSWインデックス

HNSW インデックスの作成には、次のステップが含まれます。

階層の形成

レベルの割り当て

要素はランダムにレベルが割り当てられ、上位レベルほど要素が少なくなります。レベル分布は、指数関数的に減衰する確率に従います。このランダム化により、動的なデータセットを効率的に取り扱えるバランスの取れた構造が確保されます。

レイヤー構築

HNSW における確率的階層化（ノードがスキップリストのようにさまざまなレイヤーに分散）は、通常 mL と表記されるパラメーターによって管理されます。このパラメーターは、ノードが連続するレイヤーに現れる可能性を決定し、その確率はレイヤーが上がるにつれて指数関数的に減少します。各レイヤーはそのレベルの要素の近接グラフであり、対数的な複雑さの拡張が可能です。上位レイヤーはより広い概要を提供し、下位レイヤーはより詳細な情報を提供します。

要素の追加

貪欲検索

新しい要素は最上位のレイヤーから開始され、各レベルを通って下の最近傍の要素に接続されます。要素ごとの最大接続数（M）と動的リストサイズ（efConstruction）は、インデックスの品質と効率を制御する重要なパラメーターです。これらのパラメーターにより、各要素が適切に接続され、検索効率が向上します。

最適化

ヒューリスティック選択

これにより、多様で効果的な接続が確保され、グラフのバランスが保たれます。このヒューリスティックは、候補の接続を検査し、グラフ全体の接続性を維持するものだけを保持します。

スケール分離

スケール分離は距離別にリンクを分離してナビゲーションを改善し、より長いリンクを持つ上のレイヤーから開始して、より短いリンクを持つ下のレイヤーで検索を絞り込みます。この分離により、検索プロセスの効率が向上します。

HNSW での検索

一番上から開始

ランダムな高レベルのエントリーポイントから検索を開始します。

欲張り降下法

レイヤー間を移動し、次のレベルに降下する前に常にクエリベクトルに最も近い近傍に向かいます。このアプローチにより、アルゴリズムは検索スペースをすばやく絞り込み、クエリベクトルの方向に移動して、降下が発生するたびにますます密になるグラフに移動できます。

絞り込み

検索は下層に進むほど精度が上がり、効率的に最近傍を見つけることができます。下層では検索結果が絞り込まれ、高い精度が確保されます。

HNSW の階層的アプローチと慎重なパラメーター調整を組み合わせることで、特に高次元データにおける検索効率が大幅に向上します。

最上位のエントリーポイントから最下位レベルで最も近いベクトルまでたどる各軌跡は、それぞれ1つの候補探索を表します。$vectorSearch インターフェースで numCandidates と呼ばれる検索パラメーター efSearch は、探索するエントリーポイント/軌跡の数を制御します。これを増やすと、クエリベクトルに最も近い上位 k 個のベクトルが検出される可能性が高まります。

HNSW グラフでの挿入と削除により、エントリポイントと距離メトリクスに基づいて高次元データセットを処理する際の動的な適応性と堅牢性が確保されます。グラフ構築のために新しいノードが追加されると、アルゴリズムはまず、ノードが出現する位置とノードの最大数に応じて、その階層構造内の位置を決定します。このプロセスでは、パラメーター mL によって制御される確率的な階層化に基づいて、ノードの事前定義されたエントリーポイントを特定します。

ベクトルデータベースからノードを除去するプロセスには、現在のコード、次のレイヤー、または最上位レイヤー間のリンクリストに基づいて、階層の複数のレイヤーにわたる接続または削除された要素（特にその隣接ノード）の慎重なアップデートが含まれます。これは、アルゴリズムがベクトルデータベース内を走査する際の検索の複雑さの観点から、グラフの構造的な整合性とナビゲーション可能性を維持するために不可欠です。

以下は Python 実装の例です。

Code Snippet

class HNSW(_BaseIndex):

def __init__(self, L=5, mL=0.62, efc=10):
       self._L = L
       self._mL = mL
       self._efc = efc
       self._index = [[] for _ in range(L)]

def create(self, dataset):
       for v in dataset:
           self.insert(v)

def search(self, query, ef=1):
       if not self._index[0]:
           return []
       best_v = 0
       for graph in self._index:
           best_d, best_v = HNSW._search_layer(graph, best_v, query, ef=1)[0]
           if graph[best_v][2]:
               best_v = graph[best_v][2]
           else:
               return HNSW._search_layer(graph, best_v, query, ef=ef)

def _get_insert_layer(self):
       l = -int(np.log(np.random.random()) * self._mL)
       return min(l, self._L-1)

def insert(self, vec, efc=10):
       if not self._index[0]:
           i = None
           for graph in self._index[::-1]:
               graph.append((vec, [], i))
               i = 0
           return
       l = self._get_insert_layer()
       start_v = 0
       for n, graph in enumerate(self._index):
           if n < l:
               _, start_v = self._search_layer(graph, start_v, vec, ef=1)[0]
           else:
               node = (vec, [], len(self._index[n+1]) if n < self._L-1 else None)
               nns = self._search_layer(graph, start_v, vec, ef=efc)
               for nn in nns:
                  node[1].append(nn[1])
                  graph[nn[1]][1].append(len(graph))
               graph.append(node)
           start_v = graph[start_v][2]

プロセスを検索

HNSW メソッドの中核には、データ点をグラフ構造に階層的に組織化する仕組みがあります。上位レベルの点は、下位レベルの類似した点にすばやく到達するためのショートカットとして機能し、検索空間を削減します。これらのプロセスは HNSW の適応性を示しており、動的で高次元の類似性検索アプリケーションにおける堅牢な選択肢となっています。

階層構造とスモールワールド現象のプロパティを活用することで、HNSW は必要な距離計算の数を大幅に削減します。これにより、レコメンデーションシステムや類似性ベースの検索など、迅速な応答が不可欠なアプリケーションに最適です。

HNSW は非常にスケーラブルで、大規模なデータセットを効率的に取り扱うことができます。そのクエリパフォーマンスにより、データをより小さなセットに分割でき、エントリーポイントを考慮して並列処理とリソース利用率の向上が可能になります。HNSW は低次元空間と高次元空間の両方を効果的に取り扱うことができるため、類似性検索のためにさまざまなドメインに適用できる汎用性の高いアルゴリズムです。

HNSW 検索のチューニング

HNSW では、メモリ使用量の最適化、検索精度の向上、検索パフォーマンスと速度の両方の強化のために、いくつかのアルゴリズムが使用されています。検索結果をさらに洗練させるには、検索中に考慮される候補の数を増やすことで、レイテンシ（処理時間）とリコール（精度）のバランスを取ることができます。候補の母集団を大きくすることで、レイテンシがわずかに上昇するという代償はありますが、リコールを向上させることができ、ユーザーは必要に応じて精度を優先させることができます。

別の手法であるプリフィルタリングも、検索スペースを絞り込むことで検索効率を向上させることができます。プリフィルタリングでは、HNSW 検索が開始される前にフィルタリング手順を通じて初期候補リストが生成されるため、プロセスの合理化と不要な計算の削減に役立ちます。

ブルートフォース手法と比較すると、HNSW はスキップリストを使用していることにより、ベクトルデータベースにおける類似性検索のためのスケーラブルで効率的なソリューションとして際立っています。このように、用途に合わせたアルゴリズムと階層構造を組み合わせることで、HNSW は従来の検索アプローチよりも大幅に高速かつ高精度に、大規模で高次元のデータセットを取り扱うことができます。

グラフ構造

前述のとおり、HNSW はスモールワールドプロパティに基づいています。このプロパティでは、ほとんどのノードが数ホップで到達できるため、大規模なデータセットでも検索が効率的になります。

HNSW では、各点がそのレベル内の他の点および上位レベルに接続され、階層構造が作成されます。このグラフには、最近傍や距離などの接続情報とメタデータが保存され、パターン分析に役立ちます。優先順位付きキューやハッシュテーブルなどの追加のデータ構造は、挿入や削除などのタスクを効率化するのに役立ちます。

挿入と削除は、メモリ消費を考慮すると、特に高次元データセットを扱う際に、グラフの動的な適応性と堅牢性を維持するうえで重要な役割を果たします。ノード間の距離を測定するメトリクスとしてコサイン類似度を活用する HNSW は、最適値を見つけるために最上位レイヤーと次のレイヤー間で効率的な挿入と削除を行い、メモリ使用量またはメモリフットプリントも考慮しながら、高次元データセットにおける動的かつ正確な最近傍検索の機能を強化します。

挿入

新しいノードをグラフに導入すると、アルゴリズムは階層構造内でのその配置を調整します。これには、パラメータ mL によって制御される確率的な階層化メカニズムを通じて、ノードのエントリレイヤーを特定することが含まれます。そのレイヤーから開始し、挿入プロセスはそのレイヤー内で最も近い M 個の近傍ノードと新しいノードとの接続を確立します。

隣接ノードが Mmax 接続を超えると、超過接続はプルーニング（削減）されます。次に、ノードは同様の方法で次のレイヤーに進み、最下部のノードに到達するまで継続します。ここで Mmax0 は最大接続数を示します。

削除

グラフからノードを削除するには、接続の綿密なアップデートが必要であり、特にその近隣ノード間において階層の複数のレイヤーにまたがります。この綿密な処理は、グラフの構造的な整合性とナビゲート可能性を維持するために不可欠です。

HNSW の実装によっては、各レイヤー内の接続を保護するために異なる戦略を採用し、ノードが孤立したり、グラフから切断されたりしないようにするものがあります。このアプローチは、最近傍検索のためのグラフの継続的な効率と信頼性を保護します。

HNSW における挿入操作と削除操作はいずれも、グラフの階層的かつナビゲート可能な特性を維持しながら効率性を重視して設計されています。これらの特性は、アルゴリズムによる高速かつ正確な最近傍検索機能に不可欠な要素です。これらのプロセスは HNSW の適応性を際立たせ、動的で高次元の類似性検索アプリケーションに適した堅牢な選択肢として位置付けています。

HNSW のユースケース

階層的ナビゲーション可能なスモールワールドは、その汎用性と有効性により、さまざまな分野で大きな注目を集めています。HNSW に基づくクエリベクトルを実装すると、企業にいくつかのメリットがもたらされます。

直感的なナビゲーションの提供、検索時間の短縮、ユーザーエンゲージメントの向上によりユーザー体験を改善するだけでなく、検索エンジンが情報の組織と関連性をより適切に理解できるようになるため、コンテンツの見つけやすさの最適化にも役立ちます。HNSW の価値が実証されているアプリケーションとユースケースをいくつか見ていきましょう。

画像検索

HNSW は、画像を表す高次元の特徴ベクトルを高速かつスケーラブルに検索できるため、画像検索システムで広く使用されています。HNSW グラフを構築することで、画像を効率的にインデックスでき、サブリニアな時間計算量で最近傍を抽出できます。これにより、リバース画像検索エンジンやコンテンツベースの画像検索システムなど、リアルタイムの画像検索アプリケーションが実現します。

自然言語処理（NLP）

自然言語処理では、HNSW はセマンティック検索やドキュメント類似性タスクで有望な結果を示しています。テキストドキュメントを高次元ベクトルとして表現することで、HNSW は意味的に関連するドキュメントの効率的な検索を促進します。これは、類似ドキュメントの検索や関連する回答の生成が重要となるドキュメントのクラスター化、推奨システム、質問回答システムなどで役立ちます。

音楽の推奨

HNSW は、ユーザーの好みに基づいて曲やプレイリストを提案することを目的とする音楽レコメンデーションシステムで効果的に活用されています。曲をオーディオ特性を捉えた機能ベクトルとして表現することで、HNSW は類似した曲を高速に検索できます。効率的なベクトルデータベースとマルチレイヤー構造により、HNSW は大規模な音楽コレクションを取り扱い、ユーザーの視聴履歴や好みに基づくレコメンデーションを迅速に提供できます。

異常検知

異常検知は、不正検知、サイバーセキュリティ、ネットワークモニタリングなど、さまざまな分野で不可欠なタスクです。代表的な機能空間を使用して HNSW グラフを構築することで、最近傍との距離または類似度を測定して異常を検出できます。HNSW は、大規模なデータセットを取り扱い、近似最近傍探索を実行する能力により、異常検知システムの効率と精度を大幅に向上させます。

レコメンデーションシステム

HNSW は、共同フィルターアルゴリズムで利用されており、機能または評価ベクトルに基づいて類似のユーザーやアイテムを効率的に見つけることができます。HNSW グラフを構築することで、サブ線形時間計算量で類似性ベースの推奨事項を生成でき、大規模システムでリアルタイムのパーソナライズされた推奨事項が可能になります。こうした HNSW の活用により、推奨システムの精度とスケーラビリティが向上します。

HNSW を構築する方法

HNSW に基づくクエリベクトルの実装を検討している場合は、次の手順に従ってください。

コンテンツを評価し、情報にとって理にかなった多層構造を特定します。
主要カテゴリーとサブカテゴリーを作成し、論理的な組織構造を確保します。
ユーザーがカテゴリーとサブカテゴリー間を簡単に移動できるナビゲーションシステムを設計します。
ユーザーが特定のコンテンツを迅速に見つけられるようにする検索機能を実装します。
階層構造を定期的にレビュー・更新して、効果的に機能するようにします。

HNSW を作成すると大きなメリットが得られる一方で、ベクトル検索を実装する際には考慮すべき課題があります。ベクトル検索を実装する際、論理的で直感的な組織化を確保し、情報過多を避けながら、複雑さに対応しつつシンプルさを維持することは困難な場合があります。

高品質なクエリベクトルを確保するためには、ユーザーテストを実施してフィードバックを収集し、潜在的な問題を特定して必要な改善を行うことが不可欠です。定期的な評価と最適化は、挑戦を克服し、最適なユーザーエクスペリエンスを確保するための鍵です。

ナビゲーション可能なスモールワールドグラフの作成には、さまざまなツールやテクノロジーが役立ちます。WordPressなどのコンテンツ管理システムには、階層型ナビゲーション機能を提供するプラグインやテーマがあります。さらに、Adobe XD や Sketch などのユーザーエクスペリエンス（UX）デザインツールは、使いやすいインターフェースの設計とプロトタイピングに役立ちます。これらのリソースを活用すると、HNSW インデックスの作成とメンテナンスを簡素化できます。ナビゲーション可能なスモールワールドグラフで SEO を最適化するには、次のヒントをご検討ください。

各カテゴリーとサブカテゴリーに説明的でキーワードが豊富な見出しを使用します。
コンテンツの階層を反映する明確な URL 構造を作成します。
関連するカテゴリーとサブカテゴリー間の内部リンクを実装します。
画像を最適化し、コードを最小限に抑えることで、ページの読み込み速度を高速化します。
コンテンツを定期的にアップデートして最適化し、その関連性と有用性を確保します。

結論

HNSW は、ユーザーエクスペリエンスを大幅に向上させ、コンテンツの発見可能性を高め、SEO の取り組みを促進する可能性を秘めています。論理的で直感的な階層構造を実装することで、企業はユーザーが複雑な情報をナビゲートしやすくし、顧客満足度を高めることができます。ベクトルデータベースとベクトル検索ソリューションでは、多くの場合 HNSW アルゴリズムが使用されます。たとえば、MongoDB Atlas Vector Search は、Hierarchical Navigable Small World（HNSW）アルゴリズムを使用してセマンティック検索を実行します。Atlas Vector Search の近似最近傍探索クエリサポートを使用して、選択した製品に類似する結果を検索したり、画像を検索したりできます。

HNSW ベースのソリューションを理解して実装するために時間と労力を投資することで、ビジネスに大きな成長機会をもたらせる可能性があります。

HNSW の詳細と、MongoDB Atlas Vector Search を活用してセマンティック検索を実行する方法について、HNSW アルゴリズムを使用する近似最近傍探索クエリとともに学習します。

MongoDB Atlas を是非お試しください。

無料トライアル