This repository has been archived by the owner on Nov 17, 2021. It is now read-only.
forked from yahoojapan/NGT
-
Notifications
You must be signed in to change notification settings - Fork 0
/
README.jp
301 lines (256 loc) · 15.1 KB
/
README.jp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
NGT - Neighborhood Graph and Tree for Indexing
概要
大量（数百万から数千万データ）の高次元ベクトルデータ（数十～数千次元）に対して
高速な近似近傍検索を可能とするコマンド及びライブラリを提供します。
動作確認済み環境
CentOS release 6.x
ビルド及びインストール方法
$ unzip NGT-x.x.x.zip
$ cd NGT-x.x.x
$ mkdir build
$ cd build
$ cmake ..
$ make
$ make install
$ export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib64
共有メモリ利用
インデックスを共有メモリに配置することが可能です。共有メモリを利用することにより
複数のプロセスで同一のインデックスを利用する場合にメモリ使用量を抑制することが
可能です。また、大量のデータが登録されているインデックスの起動時の速度が
改善されます。共有メモリを利用するにはビルド時の変更が必要となりますので、
cmake実行時に以下のパラメータを追加してください。
$ cmake -DNGT_SHARED_MEMORY_ALLOCATOR=ON ..
注：ロック機能はありませんので、複数プロセスで同一のインデックスを利用する場合には
参照のみでご使用ください。
その他のビルドパラメータ
・NGT_GRAPH_CHECK_VECTOR=ON
検索時のアクセス済みノードのチェックをベクトルで行う指定です。500万オブジェクト
以下の比較的少ないオブジェクトの時には検索性能が向上します。
ngt コマンド
機能概要
大量（数百万から数千万データ）の高次元ベクトルデータ（数十～数千次元）に対して
高速な近傍検索を提供します。
形式
ngt コマンド [オプション] インデックス [データ]
create - 生成（登録）
指定されたインデックスを生成した上で指定されたデータをインデックスに登録します。
形式
ngt create -d 次元数 [-p スレッド数] [-b 一括処理数] [-i インデックスタイプ]
[-g グラフタイプ] [-t エッジ削減閾値] [-e 探索範囲] [-E エッジ数]
[-S 検索時エッジ数] [-o オブジェクトタイプ] [-d 次元数] [-D 距離関数]
[-n 登録データ数]
インデックス 登録データ
インデックス
生成するインデックス名を指定します。データを登録後、本インデックス名に拡張子を付与した
複数のファイルからなるインデックスが生成されます。
登録データ
登録するベクトルデータを指定します。１行が１オブジェクト（データ）で構成され、
各次元要素のデータはスペースまたはタブで区切られていなければなりません。
-d 次元数
登録データの次元数を指定します。登録データファイルの各行がすべて次元要素のみで構成されて
いる場合には指定不要ですが、次元要素に続き属性情報などが存在している場合にはこの次元数に
基づき後続データを無視します。
-p スレッド数（デフォルト=24、推奨値=コア数）
生成時の並列処理時に利用するスレッド数を指定します。
-b 一括処理数(デフォルト=推奨=200）
通常定数オブジェクトごとに一括登録処理を行います。その一括処理時のオブジェクト数を
指定します。通常指定する必要はありません。
-i インデックスタイプ(g|t)
グラフのみか、グラフに加えツリーを作成するかを選択します。
g ：グラフインデックスのみ生成します。検索時にグラフの探索起点をランダムに決定します。
t ：グラフインデックスに加えてツリーインデックスを生成します。検索時にツリーを用いて
グラフの探索起点を決定します。（デフォルト、推奨）
-g グラフタイプ
グラフインデックスのタイプを指定する。
a ：ANNG を生成します。 高速な登録が可能です。（デフォルト、推奨）
k ：KNNG を生成します。 極めて登録が低速です。（実験用なので非推奨）
b ：BKNNG を生成します。極めて登録が低速ですが、検索は最高性能です。（実験用なので
非推奨）
-t エッジ削減閾値（デフォルト=推奨値=0）
過剰エッジ削減処理を実行する判断基準となる増加エッジ量を指定します。ANNGを選択した時に
のみ過剰エッジ削減処理が利用可能となりますが、過剰エッジ削減処理はかなり重い処理なので、
メモリ消費量を可能な限り削減したいといった場合を除き利用する必要性はありません。
過剰エッジ削減処理自体を実行しない場合には0を指定します。
-e 探索範囲係数（デフォルト=推奨値=0.1）
ANNGやBKNNGを指定した場合には登録データ（ノード）からエッジで接続される近傍ノードは
検索によって獲得され、エッジで結合されます。その検索時の探索範囲の拡大係数です。
-E エッジ数（デフォルト=推奨値=10）
グラフ生成時の各ノードの初期エッジ数を指定します。インデックス生成終了時にANNGやBKNNG
では指定されたエッジ数以上のエッジが付与されますが、KNNGでは指定されたエッジ数となり
ます。
-S 検索時のエッジ数（デフォルト=推奨値=40）
インデックス生成に伴う検索時及び生成後の検索時に利用するエッジ数を指定します。seach
コマンドによる検索時においてエッジ数を指定しない場合にこの値が利用されます。グラフ上の
各ノードの実エッジ数よりも少ないエッジ数で検索する場合に指定します。ANNGやBKNNGでは
大量のエッジが生成される場合があり、エッジ数を制限することで検索性能が向上する傾向が
あります。エッジ数を制限しない（実エッジをすべて利用する）場合には0を指定します。
0を指定した場合にはインデックスの生成が比較的遅くなりますが、検索時には最も高い性能を
得られます。
-o オブジェクトタイプ
データオブジェクトの型を指定する。
c ：1バイト整数
f ：4バイト浮動小数点（デフォルト）
-D 距離関数
距離関数を指定します。
1 ：L1距離
2 ：L2距離（デフォルト）
a ：角度
h ：ハミング距離
-n 登録データ数
登録するデータ数を指定します。指定しない場合には指定されたファイル中のすべてのデータを
登録します。
append - 追加登録
指定された登録データを指定されたインデックスに追加登録します。
形式
ngt append [-p スレッド数] [-d 次元数] [-n 登録データ数] インデックス 登録データ
インデックス
既存のインデックス（インデックスファイルの拡張子を除いた部分）を指定します。
登録データ
登録するベクトルデータを指定します。１行が１オブジェクト（データ）で、各次元のデータは
スペース又はタブで区切られていなければなりません。
-p スレッド数（デフォルト=推奨値=24）
生成時の並列処理時に利用するスレッド数を指定します。
-d 次元数
登録データの次元数を指定します。登録データファイルの各行がすべて次元要素でのみ構成されて
いる場合には指定不要ですが、次元要素に続き属性情報などが存在している場合にはこの次元数に
基づき後続データを無視します。
-n 登録データ数
登録するデータ数を指定します。指定しない場合には指定されたファイル中のすべてのデータを
登録します。
search - 検索
指定されたクエリデータを用いてインデックスを検索します。
形式
ngt search [-i インデックスタイプ] [-e 探索範囲係数] [-n 検索数] [-E エッジ上限数]
[-r 検索半径] インデックス クエリデータ
インデックス
既存のインデックス名（インデックスファイルの拡張子を除いた部分）を指定します。
クエリデータ
クエリデータのファイル名を指定します。１行が１クエリデータであり、登録データと同様に
各次元のデータはスペース又はタブで区切られていなければなりません。複数クエリを与えた
場合には順次検索します。
-i インデックスタイプ(g|t)
グラフのみか、グラフに加えツリーを利用するかを選択します。
g ：グラフインデックスのみ利用します。ツリーが存在する場合でも指定が可能です。グラフの
探索起点をランダムに決定します。
t ：グラフインデックスに加えてツリーインデックスを利用します。ツリーが存在しない場合には
エラーとなります。ツリーを用いてグラフの探索起点を決定します。グラフのみの場合よりも
高速な検索が可能です。（デフォルト、推奨）
s ：インデックスを利用せずに線形探索を行います。
-e 探索範囲係数（デフォルト=推奨値=0.1）
探索範囲の拡大係数です。大きければ精度が高くなりますが遅くなり、小さければ精度は下がり
ますが速くなります。0～0.3の範囲内で調整することが望ましいですが、負の値も指定可能です。
-n 検索数（デフォルト：20）
検索結果数を指定します。
-E エッジ数制限（デフォルト=createで指定した値または40、推奨値=40）
検索時に利用するエッジ数を指定します。グラフ上の各ノードのエッジ数よりも小さいエッジ数で
検索する場合に指定します。ANNGやBKNNGでは大量のエッジが生成される場合があり、エッジ数
制限を指定することで検索性能が向上する傾向があります。エッジ数制限しない（実エッジを
すべて利用する）場合には0を指定します。
-r 検索半径（デフォルト=無限円）
検索範囲を円の半径で指定する。
remove - 削除
指定されたオブジェクトをインデックスから削除します。
形式
ngt remove [-d オブジェクトIDの指定方法] インデックス オブジェクトID
インデックス
既存のインデックス名（インデックスファイルの拡張子を除いた部分）を指定します。
オブジェクトID
削除対象のオブジェクトIDを指定します。
-d オブジェクトIDの指定方法(f|d)（デフォルト=f）
削除するオブジェクトIDの指定方法を指定します。fを指定した場合には後述のオブジェクト
IDの指定をファイルだとみなします。指定されたファイルには１行ごとに削除するIDが
１エントリずつ指定されていなければなりません。dを指定した場合には後述のオブジェクトIDの
指定はそのままオブジェクトIDの値だとみなし、削除します。
ngt コマンド使用例
生成・登録
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)
ライセンス
ヤフー株式会社はApacheライセンスバージョン2.0の下で本ソフトウェアを公開致します。
以下のサイトよりライセンスの内容をご確認頂けます。
http://www.apache.org/licenses/LICENSE-2.0
貢献者ライセンス同意(CLA)
本ソフトウェアへのソースコードのご提供者は以下の貢献者ライセンスに同意して頂きます。
https://gist.github.com/ydnjp/3095832f100d5c3d2592
なお、GitHub (https://github.com/yahoojapan/NGT) へのご提供の場合のみ、個別の同意書面なしに、
上記貢献者ライセンスに同意して頂いたと見なしますので、ご注意ください。
---
Copyright (C) 2015-2018 Yahoo! JAPAN Research