Neighborhood Graph and Tree for Indexing High-dimensional Data with Quantization
ngtq - 大規模高次元ベクトルデータの近傍検索
$ ngtq command [option] index [data]
注: CygWin といった POSIXLY_CORERECT が設定されている環境では、コマンドの前にオプションを指定しなければなりません。
$ ngtq [option] command index [data]
十億件以上もの高次元ベクトルデータ(数十~数千次元)に対して高速な近傍検索を提供します。
command is one of:
指定されたインデックスを生成した上で指定されたデータをインデックスに登録します。
$ ngtq create -d no_of_dimensions [-p no_of_threads] [-o object_type] [-n no_of_registration_data]
[-C global_codebook_size] [-c local_codebook_size] [-N no_of_divisions]
[-L local_centroid_creation_mode]
index registration_data
index
生成するインデックス名を指定します。データを登録後、本インデックス名のディレクトリが生成されてその中に複数のファイルからなるインデックスが生成されます。
registration_data
登録するベクトルデータを指定します。1行が1オブジェクト(データ)で構成され、各次元要素のデータはスペースまたはタブで区切られていなければなりません。距離関数はL2のみが利用可能です。
-d no_of_dimensions
登録データの次元数を指定します。
-p no_of_threads (default = 24, recomended value = number of cores)
生成時の並列処理時に利用するスレッド数を指定します。
-o object_type
データオブジェクトの型を指定する。
- c: 1バイト整数 (一部未実装)
- f: 4バイト浮動小数点(デフォルト、推奨)
-n no_of_registration_data
Specifies the number of data items to be registered. If not specified, all data in the specified file will be registered.
-C global_codebook_size
グローバルコード(セントロイド)の数を指定します。
-c local_codebook_size
ローカルコード(セントロイド)の数を指定します。
-N no_of_divisions
ローカルベクトルデータ(残差データ)を生成するためのベクトルデータの分割数を指定します。
-L local_centroid_creation_mode
ローカルセントロイドを生成するモードを指定します。
- d: 指定された登録データの先頭をローカルセントロイドとして使用します。
- k: kmeans を使用してローカルセントロイドを生成します。
指定された登録データを指定されたインデックスに追加登録します。
$ ngtq append [-n no_of_registration_data] index registration_data
index
既存のインデックスを指定します。
registration_data
登録するベクトルデータを指定します。1行が1オブジェクト(データ)で、各次元のデータはスペース又はタブで区切られていなければなりません。
-n no_of_registration_data
登録するデータ数を指定します。指定しない場合には指定されたファイル中のすべてのデータを登録します。
指定されたクエリデータを用いてインデックスを検索します。
$ ngtq search [-n no_of_search_results] [-e search_range_coefficient] [-m mode]
[-r search_radius] [-E approximate-expansion] index query_data
index
既存のインデックス名を指定します。
query_data
クエリデータのファイル名を指定します。1行が1クエリデータであり、登録データと同様に各次元のデータはスペース又はタブで区切られていなければなりません。複数クエリを与えた場合には順次検索します。
-n no_of_search_results (default: 20)
検索結果数を指定します。
-e search_range_coefficient (default = recomended value = 0.1)
グローバルコードブックを検索する時の探索範囲の拡大係数です。大きければ精度が高くなりますが遅くなり、小さければ精度は下がりますが速くなります。0~0.3の範囲内で調整することが望ましいですが、負の値も指定可能です。
-m search_mode (r|e|l|c|a)
検索モードを
- a: 近似距離を用いて検索します。
- c: 近似距離を用いて検索します。計算済みローカル距離がキャッシュされることで検索時間が削減されます。(推奨)
- l: ローカル距離のルックアップテーブルによる近似距離を用いて検索します。
- e: 正確な距離を用いて検索します。ローカルコードブックを利用しません。
- r: 近似距離を用いて絞り込んだ後に正確な距離を用いて検索します。(正確な距離が必要な場合には推奨)
-E approximate_expansion
検索結果に対する近似検索結果の割合を指定します。例えば、割合が10で検索結果数が20の場合近似検索結果数は200となります。