faiss索引调研(四)—— faiss源码分析
https://zhuanlan.zhihu.com/c_159623040
1. faiss最大堆实现
和普通最大堆没什么区别。
pop:堆顶元素出列(放到最后一个位置,最后一个位置后面会置为无效),然后循环把子节点往上提(提上来大的那个子节点(左vs右))。
push:先放到最后一个位置,然后循环往上找到应该插入的位置,每次往上一步就把被对比的堆里面的原元素往下踢一个位。
2. faiss暴力搜索(找当前元素的最相近的k个元素)
循环遍历数组,建立最大堆。
亮点是计算距离的时候使用的是分段计算,把一个d维向量分开每一段计算距离。
3. faiss聚类
- 先随机初始化k个聚类中心;
- 用暴搜(用上面的方法)找出数组中每个向量所属的聚类中心。把聚类中心的向量求和并求均值作为新的聚类中心,对于空元素的聚类中心,找到另一个分裂中心拿来分裂;
- 循环步骤2知道达到迭代次数。
4. faiss倒排
索引 : 先聚类,然后遍历每个向量找到最近的1个聚类中心,把聚类中心的id和向量放到list中作为倒排表(ids和codes)。
搜索 :
- 粗查询:返回最近的nprobe个聚类中心以及对应的距离;
- 查询倒排表:对于当前查询向量的每个聚类中心:拉取聚类中心的倒排list,遍历list中的每个向量,和查询向量一一计算距离,将结果放入返回的最大堆