グラフの種類
細かいことを気にせずNGTは利用できますが、より効果的な検索を実現するには次の2つのグラフの種別を理解していることが必要となります。
- ANNG：無向グラフ（無向エッジのみで構成されたグラフ）かつ連結グラフ（任意のノードから任意のノードへのパスが存在するグラフ）です。各ノードの入次数と出次数が同じです。NGTの基本となるグラフです。
- ONNG：高い検索性能を得られるようにエッジを最適化した有向グラフ（有向エッジで構成されたグラフ）です。ANNGから生成し、ANNGよりも高い性能を得られます。ただし、ONNGからはオブジェクトが削除できません。
なお、どちらのグラフも木構造型インデックスを併用して検索します。
以下のコマンドを例に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
これらの値を御自身のデータセットに合わせて調整することは難しいですので、最適化用のコマンドが用意されています。
次に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と同様の処理を行い、エッジ数を算出する関数の係数を最適化します。 -
メモリプリフェッチ最適化
検索時のメモリプリフェッチのサイズとオフセットを最適化します。 -
精度テーブル生成
精度テーブルは精度からepsilonへのルックアップテーブルです。検索時に期待精度が指定された時に、指定された精度から検索に不可欠なepsilonをこのテーブルにより変換します。
以上で、ONNGの生成と最適化が完了します。