Faiss核心算法实现
Faiss是FAIR出品的一个用于向量k-NN搜索的计算库，其作用主要在保证高准确度的前提下大幅提升搜索速度。
Faiss 对一些基础的算法提供了非常高效的实现。
- 聚类Faiss提供了一个高效的k-means实现
- PCA降维算法
- PQ(ProductQuantizer)编码/解码：PQ优化了向量距离计算的过程，但是假如库里面的向量特别多，每一个查询向量依旧要进行很多次距离计算，效率依旧还是不够高
全量构建索引
- 原始向量文件
- Train
- Add
- Faiss索引文件
增量索引文件
- Faiss 索引文件
- Add
- Faiss 索引文件
Faiss本质上是一个向量（矢量）数据库，对于数据库来说，时空优化是两个永恒的主题，即在存储上如何以更少的空间来存储更多的信息，在搜索上如何以更快的速度来搜索出更准确的信息。
Faiss的核心原理
- Product Quantizer, 简称PQ.
- Inverted File System, 简称IVF.
IVF本身的原理比较简单粗糙，其目的是想减少需要计算距离的目标向量的个数，做法就是直接对库里所有向量做KMeans Clustering，假设簇心个数为1024，那么每来一个查询向量，首先计算其与1024个粗聚类簇心的距离，然后选择距离最近的top N个簇，只计算查询向量与这几个簇底下的向量的距离，计算距离的方法就是前面说的PQ，Faiss具体实现有一个小细节就是在计算查询向量和一个簇底下的向量的距离的时候，所有向量都会被转化成与簇心的残差，这应该就是类似于归一化的操作，使得后面用PQ计算距离更准确一点。使用了IVF过后，需要计算距离的向量个数就少了几个数量级，最终向量检索就变成一个很快的操作。
