faiss索引调研(四)—— faiss源码分析

https://zhuanlan.zhihu.com/c_159623040

1. faiss最大堆实现

和普通最大堆没什么区别。

pop:堆顶元素出列(放到最后一个位置,最后一个位置后面会置为无效),然后循环把子节点往上提(提上来大的那个子节点(左vs右))。

push:先放到最后一个位置,然后循环往上找到应该插入的位置,每次往上一步就把被对比的堆里面的原元素往下踢一个位。

2. faiss暴力搜索(找当前元素的最相近的k个元素)

循环遍历数组,建立最大堆。

亮点是计算距离的时候使用的是分段计算,把一个d维向量分开每一段计算距离。

3. faiss聚类

  1. 先随机初始化k个聚类中心;
  2. 用暴搜(用上面的方法)找出数组中每个向量所属的聚类中心。把聚类中心的向量求和并求均值作为新的聚类中心,对于空元素的聚类中心,找到另一个分裂中心拿来分裂;
  3. 循环步骤2知道达到迭代次数。

4. faiss倒排

索引 : 先聚类,然后遍历每个向量找到最近的1个聚类中心,把聚类中心的id和向量放到list中作为倒排表(ids和codes)。

搜索 :

  1. 粗查询:返回最近的nprobe个聚类中心以及对应的距离;
  2. 查询倒排表:对于当前查询向量的每个聚类中心:拉取聚类中心的倒排list,遍历list中的每个向量,和查询向量一一计算距离,将结果放入返回的最大堆
comments powered by Disqus