グラフの種類
細かいことを気にせずNGTは利用できますが、より効果的な検索を実現するには次の2つのグラフの種別を理解していることが必要となります。
- ANNG：無向グラフ（無向エッジのみで構成されたグラフ）かつ連結グラフ（任意のノードから任意のノードへのパスが存在するグラフ）です。各ノードの入次数と出次数が同じです。NGTの基本となるグラフです。
- ONNG：高い検索性能を得られるようにエッジを最適化した有向グラフ（有向エッジで構成されたグラフ）です。ANNGから生成し、ANNGよりも高い性能を得られます。
なお、どちらのグラフも木構造型インデックスを併用して検索します。
以下のコマンドを例にANNGの生成を説明します。
ngt create -d 300 -D c -E 10 anng vecs.tsv
-Eで指定する値は新たに追加するノードに付与されるエッジ数です。ANNGは逐次にノードを追加するので、登録ノード数が増えるにしたがい既存ノードのエッジ数は増えます。登録様子を以下の図に示します。
エッジ数が多いと登録時間は増えますが、検索精度が向上します。同時に検索時間も増えるので、適度なエッジ数を指定する必要があります。ただし、検索時にはノードに付与されているエッジがすべて参照されるわけではなく、デフォルトで最大40のエッジしか参照しないようになっています。デフォルトの値40により検索精度と検索時間のバランスの取れた性能となります(PANNG)。このデフォルト値を変更する場合には-Sを用いて以下のように指定することができます。
ngt create -d 300 -D c -E 20 -S 50 anng
なお、Sで指定したエッジ数は固定値ですが、εの値からエッジ数を決定することもできます。この場合、Sに-2を指定することで、εからエッジ数を自動で算出するようになります。または、search コマンドの-Eで-2 を指定することでも参照エッジ数を自動で算出します。
ngt create -d 300 -D c -E 50 -S -2 anng
エッジ数を算出する関数の係数のデフォルト値は決まっていますが、インデックスを生成した後に以下のコマンドを実行することによって、その係数が最適化されます。このコマンドでは実際に検索時間を測定して最適化しますので、実際の利用環境で行うことが望ましいです。
ngt adjust-edge-size anng
次にONNGの生成を説明します。既に説明したように以下のコマンドでANNGからONNGを生成します。
ngt reconstruct-graph -m S -o 10 -i 100 anng onng
- 入出次数の調整
ONNGを生成する準備としてノードのみのグラフを用意します。このコマンド例からANNGの各ノードから短い順に10本の出力エッジを取得して、ONNGに付与します。また、ANNGの各ノードから100本の出力エッジを抽出し、逆向きにしてONNGに付与します。これでONNGの原形が生成されます。このエッジの再構成の様子を以下に示します。
-
パスの調整
次にショートカットできるエッジを削除します。詳細は論文をご参照ください -
参照エッジ数算出関数の最適化
前述のコマンドadjust-edge-sizeと同様の処理を行い、エッジ数を算出する関数の係数を最適化します。
以上で、ONNGが生成されます。