向量检索

ANN(Approximate Nearest Neighbor)搜索的方法分为三大类：基于树的方法、哈希方法、矢量量化方法。

基于树的方法

基于树的方法采用树这种数据结构的方法来表达对全空间的划分，其中KD树和Annoy是两种经典的方法。

哈希方法

·         Local Sensitive Hashing

LSH开源工具包

·         LSHash

·         FALCONN

   FALCONN是经过了极致优化的LSH，其对应的论文为NIPS 2015 Practical and Optimal LSH for Angular Distance，FALCONN的索引构建过程非常快，百万量级的数据，维度如果是128维，其构建索引时间大概2-3min，实时搜索可以做到几毫秒的响应时间。另外谈一下数据规模问题。对于小数据集和中型规模的数据集(几个million-几十个million)， FALCONN和NMSLIB是一个非常不错的选择，如果对于大型规模数据集(几百个million以上)，基于矢量量化的Faiss是一个明智的选择。

   当然，FALCONN还不是很完善，比如对于数据的动态增删目前还不支持，具体的讨论可以参见Add a dynamic LSH table。其实这不是FALCONN独有的问题，NMSLIB目前也不支持。一般而言，动态的增删在实际应用场合是一个基本的要求，但是我们应注意到，增删并不是毫无限制的，在增删频繁且持续了一段时间后，这是的数据分布已经不是我们原来建索引的数据分布形式了，我们应该重新构建索引。在这一点上，Faiss支持数据的动态增删。

矢量量化方法

       矢量量化方法，即vector quantization，其具体定义为：将一个向量空间中的点用其中的一个有限子集来进行编码的过程。在矢量量化编码中，关键是码本的建立和码字搜索算法。比如常见的聚类算法，就是一种矢量量化方法。而在ANN近似最近邻搜索中，向量量化方法又以乘积量化(PQ, Product Quantization)最为典型。在之前的博文基于内容的图像检索技术的最后，对PQ乘积量化的方法做过简单的概要。在这一小节里，小白菜结合自己阅读的论文和代码对PQ乘积量化、倒排乘积量化(IVFPQ)做一种更加直观的解释。

·         PQ乘积量化

·         倒排乘积量化

高维空间最近邻逼近搜索算法评测

关于索引结构，有千千万万，而在图像检索领域，索引主要是为特征索引而设计的一种数据结构。关于ANN搜索领域的学术研究，Rasmus Pagh发起的大规模相似搜索项目ANN-Benchmarks、Faiss以及ann-benchmarks都有对一些主流的方法做过对比。虽然三个对比的框架对不同方法的性能均有出入，但一些主流方法的性能差异是可以达成共识的，比如基于图方法的ANN其召回率均要优于其他方法。在工业上，常用的索引方法主要以倒排、PQ及其变种、基于树的方法（比如KD树）和哈希（典型代表LSH和ITQ）为主流。

FAISS

         faiss库包含线性检索方法（BLAS库优化）、哈希方法的实现（LSH）及矢量量化方法的实现（PQ、IVFPQ）。faiss库的一大优势是支持索引的动态增删。

         faiss是为稠密向量提供高效相似度搜索和聚类的框架。由Facebook AI Research研发。 具有以下特性。

        1、提供多种检索方法

        2、速度快

        3、可存在内存和磁盘中

        4、C++实现，提供Python封装调用。

        5、大部分算法支持GPU实现

         Faiss具有以下特点：

        1，支持两种相似性计算方法：L2距离（即欧式距离）和点乘（归一化的向量点乘即cosine相似度）。

        2，按照是否编码压缩数据可以分为两类算法，使用压缩的算法可以在单台机器上处理十亿级别的向量规模。

        3，并非线程安全的——不支持并行添加向量或搜索与添加的并行；仅在CPU模式下支持并行搜索。

        4，只有继承了IndexIVF 的算法才支持向量的 remove() 操作，但由于是连续存储，remove的时间复杂度是 O(n)，建议另外维护一个列表记录被删除的或尚存的向量。

        5，faiss 针对批量搜索做了优化。

        6，IndexPQ, IndexIVFFlat, IndexIVFPQ, IndexIVFPQR 需要训练。

        7，不支持重新训练，建议新建一个索引。

        8，只接受 32-bit 浮点类型的输入数据。

挑一个合适的 Index

Faiss 提供了很多 Index，那么如何根据实际情况选择 Index 呢？

可以以下根据几个必要的问题，来找到自己合适的 Index 类型。

需要注意：

以下都通过 index_factory 字符串来表示不同 Index，如果需要参数，使用相应的 ParameterSpace 参数

1. 是否需要精确的结果？

使用 “Flat”

可以保证精确结果的唯一索引是 IndexFlatL2。

它为其他索引的结果提供基线。

它不压缩向量，但不会在它们之上增加开销。 它不支持添加id（add_with_ids），只支持顺序添加，因此如果需要 add_with_ids，请使用“IDMap,Flat”。

是否支持 GPU： yes

2. 是否关心内存？

请记住，所有Faiss索引都存储在RAM中。 以下的这些考虑是，如果我们不需要精确的结果而 RAM 又是限制因素，那么，我们就需要在内存的限制下，来优化精确-速度比（precision-speed tradeoff）。

如果不需要关心内存：“HNSWx”

如果你有大量的RAM或数据集很小，HNSW 是最好的选择，它是一个非常快速和准确的索引。 x 的范围是[4, 64]，它表示了每个向量的链接数量，越大越精确，但是会使用越多的内存。

速度-精确比（speed-accuracy tradeoff）可以通过 efSearch 参数来设置。 每个向量的内存使用是情况是（d * 4 + x * 2 * 4 ）。

HNSW 只支持顺序添加（不是add_with_ids），所以在这里再次使用 IDMap 作为前缀（如果需要）。 HNSW 不需要训练，也不支持从索引中删除矢量。

是否支持 GPU： no

如果有些担心内存：“…,Flat”

“…” 表示必须事先执行数据集的聚类。 在聚类之后，“Flat”只是将向量组织到不同桶中，因此它不会压缩它们，存储大小与原始数据集的大小相同。 速度和精度之间的权衡是通过 nprobe 参数设置的。

是否支持 GPU： yes（但是聚类方法也需要支持GPU）

如果相当关心内存：“PCARx,…,SQ8”

如果存储整个向量太昂贵，则执行两个操作：

使用尺寸为x的PCA以减小尺寸

每个矢量分量的标量量化为1个字节。

因此，总存储量是每个向量 x 个字节。

是否支持 GPU： no

如果非常关心内存：“OPQx_y,…,PQx”

PQx 代表了通过一个product quantizer压缩向量为 x 字节。 x 一般 <= 64，对于较大的值，SQ 通常是准确和快速的。

OPQ 是向量的线性变换，使其更容易压缩。 y是一个维度：

y是x的倍数（必需）

y <= d，d为输入向量的维度（最好）

y <= 4*x（最好）

是否支持 GPU： yes（注意：OPQ转换是在软件中完成的，但它不是性能关键）

3. 数据集有多大

这个问题用于选择聚类选项（就是上面的那些”…“）。 数据集聚集到存储桶中，在搜索时，只访问了一小部分存储桶（nprobe 个存储桶）。 聚类是在数据集矢量的代表性样本上执行的，通常是数据集的样本。 我们指出该样本的最佳大小。

如果向量数量低于1百万：”…,IVFx,…”

当数据集的数量为 N 时，那么 x 应该处于 4 * sqrt(N) 和 16 * sqrt(N) 之间。 这只是用k-means聚类向量。 你需要 30 * x 到 256 * x 的矢量进行训练（越多越好）。

是否支持 GPU： yes

如果向量数量位于1百万-1千万之间：”…,IMI2x10,…”

（这里x是文字x，而不是数字）

IMI在训练向量上执行具有2^10个质心的 k-means，但它在向量的前半部分和后半部分独立地执行。 这将簇的数量增加到 2^(2 * 10)。您将需要大约64 * 2 ^ 10个向量进行训练。

是否支持 GPU： no

如果向量数量位于1千万-1亿之间：”…,IMI2x12,…”

与上面相同，将10替换为12。

是否支持 GPU： no

如果向量数量位于1亿-10亿之间：”…,IMI2x14,…”

与上面相同，将10替换为14。

是否支持 GPU： no

索引方法汇总：

Faiss CPU的代码规范

没有public/private

Faiss中所有的C++对象结构，没有public/private概念，所有的字段都可以直接访问。

对象所有权

大部分情况下，Faiss对象都是可拷贝的。有一些例外的地方，对象A包含一个对象B的指针，在这种情况下，在A中有一个boolean类型的标志own_fields，这个标识用于指明当对象A被删除时对象B是否要被删除，构造时通常我们将该变量值设为false，即不是B的拥有者，当然如果在调用代码中失去了对B的引用，这可能会导致内存泄漏，所以如果我们想A在销毁时B跟着销毁，需要将其设为True，对于以下类的构造我们要注意：

Class                                       field

IndexIVF                               quantizer

IndexPreTransform                 chain

IndexIDMap                            index

IndexRefineFlat                    base_index

线程和异步调用

线程安全

Faiss CPU对于并发检索和其它不更改index的操作都是线程安全的，多线程改变index的函数需要实现互斥。

内部线程

Faiss本身有多种不同的内部线程，对于CPU的Faiss，index上3中基本操作（train，add，search）都是多线程的。线程是通过OpenMP，以及多线程的BLAS实现。我们可以通过环境变量OMP_NUM_THREADS或者调用omp_set_num_threads(10)方法。

如果查询或添加单个向量，Faiss是不会使用多线程的。

查询的性能

最好的提升查询QPS是进行批量提交。如果只是一个向量查询，那将只会在调用线程中执行。

内部线程的性能（OpenML）

调整OpenML线程数量对性能提升有时候并不是特别显著，在一些机器架构中，将线程数量设置的比内核数量稍微小点，有时候执行效率会更高。例如在Intel E5-2680 v2中，将线程数设置为20而不是默认的40，效果会更好。

如果使用OpenBLAS、BLAS实现，将线程策略设置为PASSIVE会更好：

export OMP_WAIT_POLICY=PASSIVE

异步搜索

对于包含以下一些计算的search操作，并行计算会更好：

·         单线程计算

·         等IO

·         GPU计算

对于Faiss CPU，和其他多线程计算（如其它searcher）并行化并没有什么帮助，因为这样反而会导致太多的线程从而降低正题性能。