向量检索学习记录

1、Faiss

Faiss是一个用于高效相似搜索和密集向量聚类的库；（支持单个/多个GPU）
官方文档：Home · facebookresearch/faiss Wiki · GitHub
- 安装（如果编译有问题，有些选项需要关下，比如GPU, Python，Test 在CMakeList.txt中
- -DFAISS_ENABLE_GPU=OFF; -DFAISS_ENABLE_PYTHON=OFF
- 安装参考：faiss/INSTALL.md at main · facebookresearch/faiss · GitHub
feature
- 能够在向量集合中搜索query向量的1st,2nd,3rd,4th....xth近邻
- 支持批量检索
- 用精度换速度。使用速度快10倍或内存少10倍的方法，在10%的情况下给出不正确的结果
- 使用最大内积搜索而不是最小欧式距离(L2)搜索；对其他类型的距离（L1、Linf等）搜索支持也有限
  - 各种距离参考：简单理解机器学习中的L1距离，L2距离，L-Inf距离-CSDN博客
- 返回查询点给定半径内的所有元素（range search）
- 索引数据存储在磁盘上而不是内存里？？？
- 索引二进制向量而不是浮点数向量
- ignore a subset of index vectors according to a predicate on the vector ids.
站在巨人的肩膀上，实现了如下算法 Home · facebookresearch/faiss Wiki · GitHub
- https://ieeexplore.ieee.org/abstract/document/1238663 在大型数据集中进行非穷举搜索的关键
- 基于PQ量化压缩的最近邻搜索
- IndexIVFPQR
- 等等

预训练：2步 cluster(聚类) + assign(分配) （假设原始向量为128维，切分4段，每段32维度，假设聚类中心数nlist为256）
- cluster-1 把集合中每个128维向量的切分成4个32维的；
- cluster-2 在切分完的每个32维向量组内进行聚类，得到256个聚类中心点（一般是固定的）

assign-1 由于nlist取256，那么每个聚类中心可以用8bit表示（2^8 == 256）；
assign-2 那么每个128维的原始向量经过量化编码之后就可以用4个8位表示，如上图右侧
- 有128维压缩成了4维，4维中的每一维数字代表的是当前段所属的聚类中心id

对于量化后向量集合进行检索的方式有2种；ADC(非对称距离)及SDC(对称距离)，后面的讲解是ADC的检索方式：
- query向量也切分为预训练中的4段，每段计算与预训练好的256个中心的距离【此处为4*256次32维向量的距离运算】，得到query向量与256个聚类中心距离的表； 4*256
- 此时，库的向量已经被量化成4个簇心 ID（assign-2中说的），而query向量的4段子向量与各自的256个簇心距离已经预计算好了，所以在计算两个向量的时候只用查4次表【由于有N个待对比向量，所以此处是4*N次查表】；
- 比如库里的某个向量被量化成了[124, 56, 132, 222], 那么首先查表得到query向量第一段子向量与其ID为124的簇心的距离，然后再查表得到query向量第二段子向量与其ID为56的簇心的距离......最后就可以得到四个距离d1、d2、d3、d4，query向量跟库里向量的距离d = d1+d2+d3+d4。
- 效率对比：所以在提出的例子里面，使用PQ只用4×256次32维向量距离计算加上4xN次查表，而最原始的暴力计算则有N次128维向量距离计算，很显然随着向量个数N的增加，后者相较于前者会越来越耗时；

IVFPQ(Inverted File + PQ)（传统PQ的检索加速，本质：空间分割+快速定位x个子空间+在x个子空间内进行遍历）
- PQ搜索过程中，会进行全空间遍历，即会遍历库里的全部向量并进行距离计算及查表【4*256次32维向量的距离运算 + 4*N次查表】，效率还可以提高
- IVFPQ优化本质：将全局遍历锁定为感兴趣区域，则可以避免不必要的全局计算及排序；

向量检索介绍【硬核系统设计】分布式向量检索引擎_哔哩哔哩_bilibili
百度智能云团队分享（IVF-PQ）：向量检索在大模型应用场景的技术和实践
IVFPQ详细讲解：ANN之乘积量化PQ-CSDN博客
HNSW https://zhuanlan.zhihu.com/p/673027535
- nmslib 对标faiss，在hnsw索引类型，表现优于faiss：探索NMSLIB：高效近似最近邻搜索库的宝藏-CSDN博客
通用向量检索介绍十分钟带你入门向量检索技术_nsw算法-CSDN博客
faiss 原理解析
- Github 15K！亿级向量相似度检索库Faiss 原理+应用-CSDN博客
- https://zhuanlan.zhihu.com/p/149420699
- https://zhuanlan.zhihu.com/p/357414033
faiss源码解析
- https://zhuanlan.zhihu.com/p/79589005
经典向量检索算法
- https://zhuanlan.zhihu.com/p/712991028