Overview

Faiss是Facebook AI Research开发的快速相似性搜索（similarity search）计算库。所谓的相似性搜索，就是进行向量间比对，如图示，图像经过特征提取转换成一个高维向量，通过将该向量和数据库中其他图像特征向量作一一比对，就能找出最相近的K个目标图像。不仅是图像，只要是可以用高维向量表征的，都可以做相似性搜索，如文字、音频等。

similarity search

向量比对就是计算两向量间的距离，Faiss提供了两种方法：欧几里得距离(L2)和向量点积(IP)，前者是默认方法，它的计算结果值越小表示向量越相近，后者则刚好相反，值越大表示两向量越相近。

因此，相似性搜索的过程可以简单地分为三个步骤：

计算目标向量（query）和数据库中所有向量（centroids）的L2或IP距离。
将距离值进行排序（L2采用升序排序，IP则采用降序排序），top-K个元素就是与query最相近的K个向量。
回到第一步，遍历余下的query。

IndexFlatL2

我们知道，如果数据库建立过索引，那查找起来就会飞快。Faiss也一样，需要先对数据库建立索引。Faiss支持的索引有很多，如IndexFlatL2, IndexIVFFlat, IndexIVFPQ和IndexIVFScalarQuantizer，本文介绍的是最基础的索引--IndexFlatL2，严格上讲，它不算真正意义上的索引，因为它会对数据库做全向量计算。

IndexFlatL2 tutorial

IndexFlatL2的用法很简单，add()负责为数据库建立索引，然后通过search()在数据库中为queries查找最接近的4个向量。详细的工作流程如下图所示：

两个向量间的距离，x和y的欧氏距离，拆解成了3部分：query的L2范数，centroids的L2范数以及query和centroids的矩阵乘。
centroids的L2范数在add()就已经计算好了，search()只需计算query和centroids的矩阵乘，然后再加上centroids的L2范数，即可得到每个query和数据库所有向量的相对距离。
接着对这些距离做排序后，就能到和query最相近的K个向量在数据库的index（centroids行号）。
如果需要得到目标向量的距离，只需再加上query的L2范数即可。（Option）

workflow of IndexFlatL2

Bitonic Sort

Bitonic Sort是并行排序算法，用于对向量距离进行排序。算法的思路是先把序列不断折半拆分，直到只有一个元素，然后再回溯回去两两resort成bitonic sequence，之所以是bitonic sequence，是因为对一个bitonic sequence做排序时，涉及到的swap是可以并行的。算法详解可以看https://www.youtube.com/watch?v=uEfieI0MumY，算法的GPU实现可以看https://arxiv.org/pdf/1702.08734.pdf.