Neighborhood Graph and Tree for Indexing High-dimensional Data
トップ / インストール / コマンド / ライセンス / 関連文献 / About Us
ngt - 高次元ベクトルデータ近傍検索
$ ngt command [option] index [data]
注： CygWin といった POSIXLY_CORRECT が設定されている環境では、コマンドの前にオプションを指定しなければなりません。
$ ngt [option] command index [data]
大量（数百万から数千万データ）の高次元ベクトルデータ（数十～数千次元）に対して高速な近傍検索を提供します。
command:
指定されたインデックスを生成した上で指定されたデータをインデックスに登録します。
$ ngt create -d no_of_dimensions [-p no_of_threads] [-b no_of_batch_processes]
[-i index_type] [-g graph_type] [-t edge_reduction_threshold]
[-e search_range_coefficient] [-E no_of_edges] [-S no_of_edges_at_search_time]
[-o object_type] [-D distance_function] [-n no_of_registration_data]
index [registration_data]
index
生成するインデックス名を指定します。データを登録後、本インデックス名のディレクトリが生成されてその中に複数のファイルからなるインデックスが生成されます。
registration_data
登録するベクトルデータを指定します。１行が１オブジェクト（データ）で構成され、各次元要素のデータはスペースまたはタブで区切られていなければなりません。省略するとインデックスの初期化のみ行います。
-d no_of_dimensions
登録データの次元数を指定します。登録データファイルの各行がすべて次元要素のみで構成されている場合には指定不要ですが、次元要素に続き属性情報などが存在している場合にはこの次元数に基づき後続データを無視します。
-p no_of_threads （デフォルト=24、推奨値=コア数）
生成時の並列処理時に利用するスレッド数を指定します。
-b no_of_batch_processes (デフォルト=推奨=200）
通常定数オブジェクトごとに一括登録処理を行います。その一括処理時のオブジェクト数を指定します。通常指定する必要はありません。
-i index_type (g|t)
グラフのみか、グラフに加えツリーを作成するかを選択します。
- g: グラフインデックスのみ生成します。検索時にグラフの探索起点ノードをランダムに決定します。
- t: グラフインデックスに加えてツリーインデックスを生成します。検索時にツリーを用いてグラフの探索起点ノードを決定します。（デフォルト、推奨）
-g graph_type
グラフインデックスのタイプを指定します。
- a: ANNG を生成します。 高速な登録が可能です。（デフォルト、推奨）
- k: KNNG を生成します。 極めて登録が低速です。（実験用なので非推奨）
- b: BKNNG を生成します。極めて登録が低速ですが、検索は高速です。（実験用なので非推奨）
-t edge_reduction_threshold（デフォルト=推奨値=0）
過剰エッジ削減処理を実行する判断基準となる増加エッジ量を指定します。ANNGを選択した時にのみ過剰エッジ削減処理が利用可能となりますが、過剰エッジ削減処理はかなり重い処理なので、メモリ消費量を可能な限り削減したいといった場合を除き利用する必要性はありません。過剰エッジ削減処理自体を実行しない場合には0を指定します。
-e search_range_coefficient （デフォルト=推奨値=0.1） ANNGやBKNNGを指定した場合には登録データ（ノード）からエッジで接続される近傍ノードは検索によって獲得され、エッジで結合されます。その検索時の探索範囲の拡大係数です。
-E no_of_edges (default = 10)
グラフ生成時の各ノードの初期エッジ数を指定します。インデックス生成終了時にANNGやBKNNGでは指定されたエッジ数以上のエッジが付与されますが、KNNGでは指定されたエッジ数となります。
-S no_of_edges_at_search_time （デフォルト=40） インデックス生成に伴う検索時及び生成後の検索時に利用するエッジ数を指定します。seachコマンドによる検索時においてエッジ数を指定しない場合にこの値が利用されます。グラフ上の各ノードの実エッジ数よりも少ないエッジ数で検索する場合に指定します。ANNGやBKNNGでは大量のエッジが生成される場合があり、エッジ数を制限することで検索性能が向上する傾向があります。エッジ数を制限しない（実エッジをすべて利用する）場合には0を指定します。
-o object_type
データオブジェクトの型を指定します。
- c: 1バイト整数
- f: 4バイト浮動小数点（デフォルト）
- h: 2バイト浮動小数点
- q: 1バイトスカラー量子化
-D distance_function
距離関数を指定します。
- 1: L1距離
- 2: L2距離（デフォルト）
- a: 角度
- A: 正規化角度。指定されたデータを正規化した上で保存します。
- c: コサイン類似度
- C: 正規化コサイン類似度。指定されたデータを正規化した上で保存します。
- h: ハミング距離。データオブジェクトの型は1バイト整数を指定してください。
- j: ジャッカード距離。データオブジェクトの型は1バイト整数を指定してください。
- p: ポアンカレ距離
- l: ローレンツ距離
- i: 内積。最大内積検索です。検索時に得られる距離は内積の値ではないのでご注意ください。
-n no_of_registration_data
登録するデータ数を指定します。指定しない場合には指定されたファイル中のすべてのデータを登録します。
指定された登録データを指定されたインデックスに追加登録します。
$ ngt append [-p no_of_threads] [-d no_of_dimensions] [-n no_of_registration_data]
index registration_data
index
既存のインデックスを指定します。
registration_data
登録するベクトルデータを指定します。１行が１オブジェクト（データ）で、各次元のデータはスペース又はタブで区切られていなければなりません。
-p no_of_threads（デフォルト=推奨値=24）
生成時の並列処理時に利用するスレッド数を指定します。
-d no_of_dimensions
登録データの次元数を指定します。登録データファイルの各行がすべて次元要素でのみ構成されている場合には指定不要ですが、次元要素に続き属性情報などが存在している場合にはこの次元数に基づき後続データを無視します。
-n no_of_registration_data
登録するデータ数を指定します。指定しない場合には指定されたファイル中のすべてのデータを登録します。
指定されたクエリデータを用いてインデックスを検索します。
$ ngt search [-i index_type] [-e search_range_coefficient] [-n no_of_searches]
[-E max_no_of_edges] [-r search_radius] index query_data
index
既存のインデックス名を指定します。
query_data
クエリデータのファイル名を指定します。１行が１クエリデータであり、登録データと同様に各次元のデータはスペース又はタブで区切られていなければなりません。複数クエリを与えた場合には順次検索します。
-i index_type (g|t|s)
グラフのみか、グラフに加えツリーを利用するかを選択します。
- g: グラフインデックスのみ利用します。ツリーが存在する場合でも指定が可能です。グラフの探索起点をランダムに決定します。
- t: グラフインデックスに加えてツリーインデックスを利用します。ツリーが存在しない場合にはエラーとなります。ツリーを用いてグラフの探索起点を決定します。グラフのみの場合よりも高速な検索が可能です。（デフォルト、推奨）
- s: インデックスを利用せずに線形探索を行います。
-e search_range_coefficient （デフォルト=推奨値=0.1） 探索範囲の拡大係数です。大きければ精度が高くなりますが遅くなり、小さければ精度は下がりますが速くなります。0～0.3の範囲内で調整することが望ましいですが、負の値も指定可能です。
-n no_of_searches（デフォルト：20） 検索結果数を指定します。
-E max_no_of_edges（デフォルト=createで指定した値または40） 検索時に利用するエッジ数を指定します。グラフ上の各ノードのエッジ数よりも小さいエッジ数で検索する場合に指定します。ANNGやBKNNGでは大量のエッジが生成される場合があり、エッジ数制限を指定することで検索性能が向上する傾向があります。エッジ数制限しない（実エッジをすべて利用する）場合には0を指定します。
-r search_radius （デフォルト=無限円）
検索範囲を円の半径で指定する。
指定されたオブジェクトをインデックスから削除します。
$ ngt remove [-d object_id_specification_method] index object_id
index
既存のインデックス名を指定します。
object_id
削除対象のオブジェクトIDを指定します。
-d object_id_specification_method (f|d) （デフォルト=f） 削除するオブジェクトIDの指定方法を指定します。fを指定した場合には後述のオブジェクトIDの指定をファイルだとみなします。指定されたファイルには１行ごとに削除するIDが１エントリずつ指定されていなければなりません。dを指定した場合には後述のオブジェクトIDの指定はそのままオブジェクトIDの値だとみなし、削除します。
指定されたインデックスのグラフ中の長いエッジを削減します。このコマンドにより検索時間が短縮されますが、性能向上には以下の reconstruct graph のパス最適化の利用をお勧めします。
$ ngt prune -e no_of_forcedly_pruned_edges -s no_of_selectively_pruned_edge index
index
既存のインデックス名を指定します。
-e no_of_forcedly_pruned_edges
各ノードに付与できる最大エッジ数を指定します。各ノードについて指定された数以上のエッジは長い順に強制的に削除します。
-s no_of_selectively_pruned_edge
削除対象としないエッジ数（ランク）を指定します。各ノードについて短い順にエッジを並べた時のランクが指定数を越えて、かつ、そのエッジの代替パスが存在する場合に、そのエッジを削除します。
no_of_forcedly_pruned_edgesはno_of_selectively_pruned_edgesより大きくなければなりません。
指定されたインデックスからグラフを再構成したインデックスを生成します。
$ ngt reconstruct-graph [-m shortcut_mode] [-s search_optimization_mode] [-I graph_type] -o no_of_outgoing_edges -i no_of_incoming_edges input_index reconstructed_index
input_index
既存のインデックス名を指定します。
reconstructed_index
再構成されるインデックス名を指定します。
-o no_of_outgoing_edges
再構成されるグラフに付与する入力グラフの各ノードの出エッジ数を指定します。この値は再構成されるグラフの出次数の下限値となります。
-i no_of_incoming_edges
再構成されるグラフに付与する入力グラフの各ノードの出エッジ数を指定します。ただし、出エッジの方向を反転した上で再構成されるグラフに付与されます。この値は再構成されるグラフの入次数の下限値となります。
-m mode
グラフのショートカット削減のモードを指定します。
- S: ショートカット削減あり（デフォルト）
- s: ショートカット削減なし
-s mode
Specify the mode of the search parameter optimization.
- s: 探索エッジパラメータ最適化
- p: プリフェッチパラメータ最適化
- a: 精度テーブル生成
- -: 上記すべて（デフォルト）
-I graph_type 既存のグラフのタイプを指定します。ANNG以外のグラフではANNGに変換してから再構成します。
- a: ANNG
- o: ANNG以外
128次元１バイト整数型データのインデックスの生成
$ cd (NGT_TOP_DIR)
$ ngt create -d 128 -o c index ./data/sift-dataset-5k.tsv
Data loading time=0.160748 (sec) 160.748 (msec)
# of objects=5000
Index creation time=0.379659 (sec) 379.659 (msec)
ファイルで指定された3クエリによる近傍検索
$ cd (NGT_TOP_DIR)
$ ngt search -n 20 index ./data/sift-query-3.tsv
Query No.1
Rank ID Distance
1 3031 239.332
2 4079 240.002
3 3164 244.504
4 3718 246.763
5 157 251.094
6 2422 251.185
7 1313 251.34
8 379 252.446
9 3521 260.158
10 2594 261.132
11 4627 262.381
12 2159 263.471
13 3519 264.909
14 1764 265.136
15 4400 266.156
16 2717 266.914
17 3168 269.637
18 4236 270.673
19 4700 272.725
20 679 272.973
Query Time= 0.000472 (sec), 0.472 (msec)
Query No.2
Rank ID Distance
1 2726 291.983
2 924 296.987
3 3638 298.585
4 858 300.376
5 1453 306.805
6 174 307.789
7 2992 308.485
8 2980 308.93
9 1525 309.49
10 244 309.816
11 910 310.446
12 3310 310.585
13 2433 311.482
14 1633 311.735
15 3761 312.44
16 407 313.252
17 4546 313.876
18 697 315.108
19 34 315.563
20 2189 316.193
Query Time= 0.000478 (sec), 0.478 (msec)
Query No.3
Rank ID Distance
1 762 194.286
2 1046 212.695
3 4906 215.244
4 2905 216.539
5 4142 219.479
6 1879 219.616
7 4398 223.352
8 3842 223.468
9 233 224.127
10 2794 224.366
11 2476 224.804
12 1848 225.803
13 3364 226.561
14 4098 226.74
15 3023 228.884
16 4113 229.325
17 1036 232.852
18 1740 233.144
19 2302 233.818
20 2440 233.91
Query Time= 0.00018 (sec), 0.18 (msec)
Average Query Time= 0.000376667 (sec), 0.376667 (msec), (0.00113/3)
関連文献のインデックス生成手順
$ ngt create -i t -g a -S 0 -e 0.1 -E no_of_edges -d dimensionality_of_data -o data_type -D distatnce_type anng-index vector-data.dat
$ ngt reconstruct-graph -m S -o outdegree -i indegree anng-index onng-index
e.g.
$ ngt create -i t -g a -S 0 -e 0.1 -E 100 -d 128 -o c -D 2 anng-index vector-data.dat
$ ngt reconstruct-graph -m S -o 10 -i 120 anng-index onng-index
$ ngt create -i g|t -g a -S 0 -e 0.1 -E no_of_edges -d dimensionality_of_data -o data_type -D distatnce_type panng-index vector-data.dat
$ ngt prune -e no_of_forcedly_pruned_edges -s no_of_selectively_pruned_edges panng-index
e.g.
$ ngt create -i t -g a -S 0 -e 0.1 -E 10 -d 128 -o c -D 2 panng-index vector-data.dat
$ ngt prune -e 60 -s 30 panng-index
$ ngt create -i t -g a -S 0 -e 0.1 -E no_of_edges(k) -d dimensionality_of_data -o data_type -D distance_type anngt-index vector-data.dat
e.g.
$ ngt create -i t -g a -S 0 -e 0.1 -E 16 -d 128 -o c -D 2 anngt-index vector-data.dat
$ ngt create -i g -g a -S 0 -e 0.1 -E no_of_edges(k) -d dimensionality_of_data -o data_type -D distance_type anng-index vector-data.dat
e.g.
$ ngt create -i g -g a -S 0 -e 0.1 -E 16 -d dimensionality_of_data -o data_type -D distance_type anng-index vector-data.dat
$ ngt create -i g -g k -S 0 -E no_of_edges(k) -d dimensionality_of_data -o data_type -D distance_type knng-index vector-data.dat
e.g.
$ ngt create -i g -g k -S 0 -E 20 -d 128 -o c -D 2 knng-index vector-data.dat