• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

faiss笔记

开发技术 开发技术 4小时前 2次浏览

faiss没有windows的版本,只支持mac++linux

一、简单介绍

1. 当向量规模很大的时候,普通的暴力索引IndexFlatL2搜索很慢,而IndexIVFFlat索引可以建立倒排索引,即使用K-means建立聚类中心,然后通过查询最近的聚类中心,然后比较聚类中的所有向量得到相似的向量;用k-nn的话,索引结果会受k和数据规模影响。

2. 像IndexFlatL2IndexIVFFlat这种索引都会全量存储所有的向量到内存,faiss提供基于Product Quantizer(乘积量化)的压缩算法编码向量大小到指定的字节数。此时,存储的向量时压缩过的,查询的距离也是近似的。用法类似于

quantizer = faiss.IndexFlatL2(d)          # 先建一个普通的索引,作为一个容器quantizer

index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)  # 这里是将容器中的向量使用乘积量化压缩为8Byte的;d:维数;m:向量段数

 

3. faiss定义了两种衡量相似度的方法(metrics),分别为faiss.METRIC_L2、faiss.METRIC_INNER_PRODUCT,一个是欧式距离,一个是向量内积。

 

4. faiss中的参数含义:nlist:聚类中心的个数;k:查找最相似的k个向量,即K-NN;index.nprobe:查找聚类中心的个数,默认为1个

具体用法和C++用法参考官方代码和具体代码实现就可以;


二、数据的预处理(https://blog.csdn.net/xiaoxu2050/article/details/84982478)

用index_factory可以直接用指定的字符串表达构建索引

Index *index_factory (int d, const char *description_in, MetricType metric);
description = "IVF100,PQ8";  // 示例,具体字符表达

 

 

index_factory:index_factory通过字符串来创建索引,字符串包括三部分:预处理、倒排、编码。
预处理支持:

  PCA:PCA64表示通过PCA降维到64维(PCAMatrix实现);PCAR64表示PCA后添加一个随机旋转。
  OPQ:OPQ16表示为数据集进行16字节编码进行预处理(OPQMatrix实现),对PQ索引很有效但是训练时也会慢一些。
倒排支持:

  IVF:IVF4096表示使用粗量化器IndexFlatL2将数据分为4096份
  IMI:IMI2x8表示通过Mutil-index使用2x8个bits(MultiIndexQuantizer)建立2^(2*8)份的倒排索引。
  IDMap:如果不使用倒排但需要add_with_ids,可以通过IndexIDMap来添加id
编码支持:

  Flat:存储原始向量,通过IndexFlat或IndexIVFFlat实现
  PQ:PQ16使用16个字节编码向量,通过IndexPQ或IndexIVFPQ实现
  PQ8+16:表示通过8字节来进行PQ,16个字节对第一级别量化的误差再做PQ,通过IndexIVFPQR实现
如:

index = index_factory(128, "OPQ16_64,IMI2x8,PQ8+16")

即:处理128维的向量,使用OPQ来预处理数据,16是OPQ内部处理的blocks大小,64为OPQ后的输出维度;使用multi-index建立65536(2^16)和倒排列表;编码采用8字节PQ和16字节refine的Re-rank方案。

 

OPQ是非常有效的,除非原始数据就具有block-wise的结构如SIFT。

 

 三、索引归纳

有add_with_ids的索引类别:IndexIVFFlat/IndexPQ/IndexIVFPQ等

需要训练的索引:大部分索引需要训练的步骤。IndexFlatL2没有

 

四、选择合适的索引

(一) 、是否需要确切结果
是:“Flat”
只有IndexFlatL2或者IndexFlatIP能够保证生成确切的结果。通常情况下它是用来生成其他索引的基线的。"Flat"不会压缩向量,也不会增加额外的开销。不支持add_with_ids功能,只是支持顺序添加。如果需要使用add_with_ids,可以使用“IDMap, Flat”。Flat的索引不需要训练,也没有参数

(二)、是否关注内存的占用
1、不关心,使用“HNSWx”
如果数据集很小或者内存很大,基于图的方法HNSW是最好的选择,这种索引方法即快又准。x的取值在[0,64]之间,表示每个向量的连接数,x的值越大结果越准确,但是占用内存越多。通过设置efSearch参数可以权衡速度和准确度。每个向量会占用内存为(d*4 + x*2*4) bytes的内存

Supported on GPU: no

2、有点关心,使用"...,Flat"
...表示首先要对数据集进行聚类处理。聚类后,"Flat"将向量组织到相应桶里,过程不存在向量压缩,占用内存数和原始数据大小相同。可以修改nproce参数设置探测桶的数量,权衡检索速度和准确率。

Supported on GPU: yes (but see below, the clustering method must be supported as well)

3、比较重要,使用"PCARx,...,SQ8"
如果存储整个向量太过昂贵,这类索引会执行两类操作:

使用PCA进行降维,x为降维后的向量维度
使用标量量化,原向量每个维度都会映射到1Byte
因此该索引输出向量占用x Bytes的内存。

Supported on GPU: no

4、非常重要,使用"OPQx_y,...,PQx"
PQx是使用乘积量化器压缩向量,输出x Byte的编码,通常x值小于64,x值越大越准确,检索速度越快。

OPQ是对向量进行线性变换预处理,这样会更容易压缩,y是输出维度,要求如下:

y必须是x的倍数
y最好要小于输出向量的维度d
y最好小于4*x
Supported on GPU: yes (note: the OPQ transform is done in software, but it is not performance critical)

(三)、需要索引数据集有多大?
这个问题的答案将会决定选择的聚类算法(即如何设定上面...部分)。数据集会被聚类成桶,搜索的时候只有访问一部分的桶。通常情况只会对数据集的代表性样本进行聚类,也就是数据的抽样。这里会说明抽样本的最佳大小。

少于1M的向量 "...,IVFx,..."
x为聚类中心点的数量,取值大小在【4*sqrt(N), 16*sqrt(N)】之间,其中N是数据集的大小。该索引只是使用k-means做向量聚类,需要使用30*x到256*x的向量做训练,越多越好。引支持使用GPU

1M - 10M: "...,IMI2x10,..."
IMI也是使用K-means方法,生成2^10个中心点,不同的是IMI分别对向量的前半部分和后半部分进行聚类处理。这样生成桶的数量变成2^(2*10)个。训练时需要大概64*2^10向量。引不支持使用GPU

10M - 100M: "...,IMI2x12,..."
和上面类似,只是将10变成12。

100M - 1B: "...,IMI2x14,..."
和上面类似,只是将10变成14

 

更多内容:https://github.com/facebookresearch/faiss/wiki


程序员灯塔
转载请注明原文链接:faiss笔记
喜欢 (0)