Hierarchical Navigable Small World (HNSW)

Hierarchical Navigable Small World (HNSW)は、高次元データの近似最近傍探索を効率的に行うためのアルゴリズムです。この手法は、データポイント間の距離に基づいて構築される階層的なグラフ構造を利用します。各層では、ポイントは小世界性質を持つように接続され、探索時には高い層から始めて徐々に下の層へと移動することで、効率的に目的の近傍を見つけ出します。このアプローチは、検索速度と精度のバランスを改善することを目指しています。

主要な論文

論文タイトル(和訳): 階層型ナビゲータブル小世界グラフを用いた効率的かつ堅牢な近似最近傍探索
著者: Yu. A. Malkov, D. A. Yashunin
バブリッシュ年: 2016/03/30 (最終改訂: 2018/08/14)
どういう論文？
- 近似K最近傍探索のための新しいグラフベースの手法を提案
先行研究と比べてどこがすごい？
- 高速でかつ高リコールの検索性能を実現
- 従来のベクトル専用手法を大きく上回る
技術や方法のポイントはどこ？
- 階層的な小世界グラフの構造を用いる
- グラフの階層は確率的に決定
- 距離スケールに応じたリンクの分離
どうやって有効と検証した？
- 様々なデータセットでの性能評価を実施
- 高リコールと高クラスタデータでの性能を示した
議論の内容は？
- アルゴリズムのスキップリスト構造との類似性
- 分散実装の可能性

用語

用語	説明
Steiner Tree Problem	与えられたグラフの特定の頂点（ターミナル）を最小全体コストで接続するネットワークを見つける問題。
Graph Theory	頂点とエッジからなるグラフを研究する数学の分野。
Approximation Algorithm	最適解を計算するのが難しい問題に対して、近似解を効率良く見つけ出すアルゴリズム。
Metric Embeddings	一つの距離空間を別の距離空間に埋め込むこと。このプロセスは、元の空間の距離を保存することを目指す。
NP-Complete	NP完全問題は、すべてのNP問題が多項式時間で還元可能な非決定性多項式時間で解ける問題のクラス。
APX-Hard	近似解を持つが、任意に近い精度で近似することができない（特定の条件下で）問題のクラス。
Polynomial Time	問題を解くのに必要な時間が入力サイズの多項式関数で表せる場合。
Vertex (Graph Theory)	グラフ理論において、エッジによって接続されるオブジェクト。ノードとも呼ばれる。
Edge (Graph Theory)	グラフ理論において、二つの頂点を接続する線分。
Weighted Graph	各エッジに重み（コスト、距離、または他の属性）が割り当てられたグラフ。
Root Vertex	有向グラフや木において、起点となる特定の頂点。
Terminals	スタイナー木問題において、接続が必要な特定の頂点の集合
Subgraph	元のグラフの頂点集合とエッジ集合のサブセットから成るグラフ。
Spanning Tree	元のグラフのすべての頂点を含み、サイクルを持たないサブグラフ。
NP-Complete Problems	すべてのNP問題が多項式時間で還元可能で、非決定性多項式時間で解ける問題のクラス。
Polynomial Time Approximation Scheme (PTAS)	問題の最適解に任意に近い解を多項式時間で提供するアルゴリズムのクラス。
Metric Space	距離関数によって距離が定義される空間。
Diameter (Graph Theory)	グラフ内の任意の二頂点間の最短経路の最大長。
Vertex Partition	グラフの頂点集合を複数の互いに排他的な部分集合に分割すること。
Induced Graph	元のグラフの頂点のサブセットに対応するエッジのみを含むサブグラフ。
Online Algorithm	入力が順番に与えられ、各ステップで即座に決定を下す必要があるアルゴリズム。
Approximation Factor	近似アルゴリズムが見つけた解と最適解の間の比率の上限。
Routing	ネットワーク内でデータパケットが送信元から目的地まで移動するパスを決定するプロセス。
Spanning Tree Protocol (STP)	ネットワーク内でループを防止するために使用されるプロトコルで、有向非巡回グラフを生成する。
Broadcasting (Networking)	ネットワーク上のすべてのノードにデータを一斉に送信するプロセス。
Metric Distance	距離空間における二点間の距離を測るための関数。
Sublinear Time Algorithm	入力サイズに対して線形未満の時間で動作するアルゴリズム。
Greedy Algorithm	各ステップで局所的に最適な選択を行い、全体の最適解を見つけるアルゴリズムのクラス。
Dynamic Programming	複雑な問題をより小さなサブプロブレムに分割し、それぞれを解いて最終的な解を構築する方法。
Graph Coloring	グラフの頂点を色分けする問題で、隣接する頂点が異なる色になるようにする。
Hamiltonian Path	グラフ内のすべての頂点を一度だけ通過するパス。
Eulerian Path	グラフ内のすべてのエッジを一度だけ通過するパス。
Graph Isomorphism	二つのグラフが頂点の対応関係によって互いに変換可能であることを示す関係。
Minimum Spanning Tree (MST)	グラフ内のすべての頂点を最小の総エッジ重みで接続するサブグラフ。
Graph Connectivity	任意の二頂点間にパスが存在するグラフの特性。
Shortest Path Problem	グラフ内の二頂点間で最も短いパスを見つける問題。
Vertex Cover	グラフ内のすべてのエッジが少なくとも一方の端点を含む頂点の集合。