faiss類似フィーチャーベクトル検索

1,2つの類似性計算方法をサポートする:L 2距離(すなわちヨーロッパ式距離)と点乗(正規化されたベクトル点乗すなわちcosine類似度);
2、圧縮データを符号化するかどうかによって2種類のアルゴリズムに分けることができ、圧縮アルゴリズムを使用して1台の機械で10億レベルのベクトル規模を処理することができる.
3スレッドが安全ではありません.ベクトルの並列追加や追加の並列検索はサポートされていません.パラレルサーチはCPUモードでのみサポートされます.
4,IndexIVFを継承したアルゴリズムのみがベクトルのremove()動作をサポートするが,連続記憶であるため,removeの時間的複雑度はO(n)であり,リストレコードが削除されたか残存するベクトルを別途維持することを提案する.
5,faissは一括検索に対して最適化を行った.
6,IndexPQ,IndexIVFFlat,IndexIVFPQ,IndexIVFPQRは訓練が必要である.
7、再訓練をサポートしないで、新しいインデックスを提案します.
8,32-bit浮動小数点タイプの入力データのみを受け入れる;
9、index=faissを使用する.index_factory(dim、「PCA 32、IVF 100、PQ 8」)という形式でインデックスを作成するのはより柔軟で、ここでタイプパラメータは、PCAを使用して元のベクトルを32次元に下げ、IVFを使用してインデックスを作成し、サブリスト(すなわちbucketバケツ)の個数を100とし、Product Quantizer(積算量子化)を使用して各ベクトルを8バイトに圧縮符号化すると解釈できる.に等しい

num_list = 64
dim = 64
bytes_per_vector = 8
bits_per_sub_vector = 8

quantizer = faiss.IndexFlatL2(dim)
index = faiss.IndexIVFPQ(quantizer, dim, num_list, bytes_per_vector, bits_per_sub_vector)

10、索引タイプの選択

正確な検索結果が必要な場合は、次元を下げないで、量子化しないで、Flatを使用します.同時に、Flatを使用すると、データが圧縮されず、同じサイズのメモリが消費されます.

メモリが緊張している場合は、PCAを使用して次元を下げ、PQ量子化符号化を行い、メモリの消費量を減らすことができ、最終的に消費されるメモリの大きさは約**に等しい.量子化符号化後のバイト数が64より大きい場合は、SQxをPQxに置き換えることをお勧めします.精度は同じですが、速度は速くなります.量子化符号化を容易にするためにOPQx_を用いることができるyまずベクトルを線形変換し、yは符号化後のバイト数xの倍数でなければならないが、次元dimと4*xより小さいことが望ましい.

総ベクトル個数Nが1百万未満の場合、IVFxの使用が推奨され、xの選択値は4*sqrt(N)と16*sqrt(N) の間にあり、トレーニングデータのサイズは少なくともxの30倍である.総ベクトル個数Nが1百万より大きく、1千万未満の場合、IMI 2 x 10を推奨し、実際の内部クラスタリング個数は2^(2*10)であり、64*2^10個のベクトルが訓練に参加する必要がある.総ベクトル個数Nが1千万より大きく、1億未満である場合、IMI 2 x 12の使用を推奨する.総ベクトル個数Nが1億より大きく、10億未満の場合、IMI 2 x 14の使用を推奨する.IMIメソッドはGPUをサポートしていない.

IndexIVFはaddを生まれつきサポートしています.with_idsメソッド、add_がサポートされていない場合with_idsメソッドのタイプは、IndexIDMapアシスト

を使用することができる.

index = faiss.IndexFlatL2(xb.shape[1]) 
ids = np.arange(xb.shape[0])
index.add_with_ids(xb, ids)  # this will crash, because IndexFlatL2 does not support add_with_ids
index2 = faiss.IndexIDMap(index)
index2.add_with_ids(xb, ids) # works, the vectors are stored in the underlying index

 
4、よくある質問:
暴力的な検索が遅く、解決方法:

export OMP_WAIT_POLICY=PASSIVE

 
参照先:
https://github.com/facebookresearch/faiss
https://github.com/facebookresearch/faiss/wiki/Troubleshooting
https://github.com/facebookresearch/faiss/wiki/FAQ