NGT - グラフの探索起点の選択方法 -

高次元ベクトルデータの近傍検索（NGT）の研究開発を行っている。Yahoo! JAPAN研究所の岩崎です。前回はグラフインデックスによる近傍検索の基本について説明しました。基本部分だけでも高精度かつ高速な近傍検索ができますが、さらに高性能化する方法について説明します。ポイントは主に以下の3点です。

• グラフの探索起点の選択方法
• 検索ロジックの実装方法
• グラフインデックスの生成方法

最後のグラフインデックスの生成方法が最も重要である反面、分かりにくい部分でもあるので、分かり易いグラフの探索起点の決定方法から説明します。前回説明したように本手法ではグラフ上の探索起点ノードからクエリオブジェクトに向かってグラフを探索します。探索起点がクエリオブジェクトから遠いと探索時間が増大するので、クエリオブジェクトになるべく近い探索起点を選択することが重要です。主に以下のような探索起点の選択方法があります。

• ランダムなノード選択
• 代表ノード選択
• インデックスによる近傍ノード選択

ランダムなノード選択

最も単純な方法としては、ランダムに選択したノードを探索起点とする方法があります。この場合、クエリオブジェクトから遠いノードが偶然選択されると、探索に時間がかかることになります。そこで、ランダムに複数のノードを選択することで、遠いノードが選択される可能性を減らす対処を行ったりします。

代表ノード選択

複数の代表ノードをあらかじめ抽出しておき、代表ノードの中でクエリオブジェクトに最も近いノードを探索起点とします。グラフのノードをkmeansなどでクラスタリングして得られた各セントロイドに最も近いノードを代表ノードとします。代表ノードを増やせば、常に比較的近傍の探索起点を得られますが、代表ノードの数が増えすぎるとクエリオブジェクトに最も近い代表ノードを選択する処理に時間がかかってしまいます。

インデックスによる近傍ノード選択

クエリオブジェクトに近い探索起点のノードを選択するためだけにインデックスを用意します。この場合、時間をかけてまで、クエリに対する正確な最近傍ノードを得る必要はありません。とにかく高速に近傍ノードが得られれば良いです。そこでNGTではこの用途のためにツリー型インデックスであるvp-treeを拡張したインデックスを使っています。ツリー型インデックスでは、高次元のオブジェクトの検索に時間を要するのではないかと思われるかもしれませんが、クエリオブジェクトが属する部分空間をツリー構造のルートからリーフへ一直線にたどるだけなので、極めて高速に近傍ノードを取得することが可能です。その代わりに最近傍ノードが得られるとは限りません。

ツリー型インデックス

では、簡単にvp-tree（vantage point tree）を改良したNGTのツリー型インデックスについて説明します。vp-treeではvantage pointと呼ばれる基準点を中心とした超球の内側と外側で空間を分割します。一つのvantage pointに対して複数の半径を設定すれば、超球の数+1の空間に分割できます。つまり、vantage point とクエリオブジェクトの距離を一回計算することで1/(超球の数+1)の部分空間に絞り込めるので、他のツリー型インデックスに比べて少ない距離計算回数により空間の絞り込みができます。空間の分割例を下図に示します。ツリー構造の四角が空間全体を示すルートノードです。この例では空間全体を赤の同心円、オレンジの同心円、青の同心円により順に3分割することで部分空間へ細分化し、その部分空間の包含関係を示すツリー構造を生成します。なお、図はツリー構造の説明なので、実際のインデックスの生成手順とは異なります。

ツリー型インデックスによる探索起点選択

ツリー型インデックスを用いた探索起点の選択の様子を下図に示します。緑の点がクエリオブジェクトです。赤、オレンジ、青の順にクエリオブジェクトを包含する部分空間をたどります。たどり着いた最小の部分空間のオブジェクト、すなわち、たどり着いたツリー構造のリーフノードに関連付けられたオブジェクトがクエリオブジェクトの近傍オブジェクトであり、これをNGTではグラフの探索起点とします。NGTのツリー型インデックスでは各空間を4つの同心円により5分割しています。したがって単純計算で、8回計算するだけで1/5⁸=1/390,625となるので、1千万ノードあっても約25のノードに絞り込めます。

次回は検索ロジックの実装方法について解説します。

Yahoo! JAPAN研究所　岩崎雅二郎