実データでのコマンド利用例

ここでは大規模な実データを利用して、NGTの2つの主要なグラフ形式（ANNG、ONNG）の使い方を紹介します。

データセットの生成

ngt のコマンドを用いてfasttextで生成された大規模データを検索する手順を説明しますので、まず、データセットの準備をします。以下のように fastText のデータをダウンロードした後、NGTの登録ファイルのフォーマットに変換します。

curl -O https://dl.fbaipublicfiles.com/fasttext/vectors-english/wiki-news-300d-1M-subword.vec.zip
zcat wiki-news-300d-1M-subword.vec.zip | tail -n +2 wiki-news-300d-1M-subword.vec | cut -d " " -f 2- > objects.ssv

これによりobjects.tsvが生成されます。次に3オブジェクトをクエリとします。

head -100000 objects.ssv | tail -3 > queries.ssv

ANNGインデックスの生成と検索

インデックスを生成します。距離関数にコサイン類似度を指定しています。

ngt create -d 300 -D c fasttext.anng objects.ssv

生成されたインデックスに対して検索します。

ngt search -n 5 fasttext.anng queries.ssv

検索結果は以下の通りです。

Query No.1
Rank    ID      Distance
1       999992  0
2       429438  0.164919
3       517746  0.177872
4       452136  0.182127
5       431584  0.183806
Query Time= 0.000446746 (sec), 0.446746 (msec)
Query No.2
Rank    ID      Distance
1       999993  0
2       999649  0.138547
3       961651  0.153957
4       687304  0.164225
5       608817  0.167914
Query Time= 0.000297313 (sec), 0.297313 (msec)
Query No.3
Rank    ID      Distance
1       999994  0
2       744059  0.188322
3       579115  0.188854
4       632605  0.205088
5       964311  0.206573
Query Time= 0.000316016 (sec), 0.316016 (msec)
Average Query Time= 0.000353358 (sec), 0.353358 (msec), (0.00106008/3)

高い精度が必要なときには、以下のようにデフォルト値の0.1より大きな値をsearchの search_range_coefficient に指定します。

ngt search -n 5 -e 0.15 fasttext.anng queries.ssv

精度を犠牲にしても高速な検索が必要であれば、 search_range_coefficient の値を小さくします。

ONNG生成用のANNGの生成

次に、より性能の向上が期待できるONNGを生成します。ONNGを生成する前にエッジが多いANNGを作成します。ONNGを生成するときにエッジが最適に削減されるので、エッジを多めにしておく必要があります。ただし、エッジが多すぎるとANNGの生成が遅くなります。以下は100のエッジでANNGを生成する例です。ほとんどのデータセットではエッジ数100は多すぎるので、データセットの検索精度を基にしてエッジ数を削減できます。

ngt create -d 300 -D c -E 100 -S -2 fasttext.anng objects.ssv

ANNGからONNGの生成

つぎに以下のreconstruct-graphコマンドによりANNGからONNGを生成します。

ngt reconstruct-graph -m S -o 10 -i 100 fasttext.anng fasttext.onng

-mに指定しているSはパスの最適化と検索時の動的エッジ数生成係数の最適化を行うことを意味しています。-o、-iにより出力エッジ数と入力エッジ数を設定しています。入力エッジ数はcreate時のエッジ数と同一の100を指定していますが、createで生成されたグラフの各ノードのエッジ数は指定したエッジ数よりも多くなりますので、入力エッジ数をcreate時のエッジ数より大きても構いません。

ONNGによる検索

ANNG同様に検索してみます。

ngt search -n 5 fasttext.onng queries.ssv

ANNGと比較して検索時間が遅くなる場合があるかもしれませんが、検索精度が上がっているはずです。したがって、ANNG で高い精度を得るためにはsearch_range_coefficient を大きしなければならず、結果としてANNGの検索時間はONNGよりも増大します。