faiss记录
#faiss#向量检索 2022-04-27

一、IndexFlatL2

1、核心特性

  • 暴力检索：遍历计算查询向量和索引中所有向量的欧氏距离，返回相似度最高的那个结果，确保结果精确度但效率较低。
  • 无预处理优化：不进行聚类、量化或压缩等优化处理，直接存储原始向量数据，内存占用和存储成线性关系。
  • 支持高维度：适用于任意维度的向量数据，例如文本嵌入、图像特征等

2、使用场景

  • 小规模数据集：数据量在百万级别以下的时候，计算开销可以接受。
  • 精度优先任务：算法基准测试，召回率验证等需要精确结果场景。
  • 其他索引参照基准baseline：常作为对比对象，验证其他近似索引（如IndexIVFFlat、IndexIVFPQ）的精度损失程度

如果需要在IndexFlatL2基础上提升效果，可以做：

  1. 用主成分分析PCA做数据降维
  2. 混合检索，通过数据量灵活切换IndexIVFFlat或者IndexIVFPQ
  3. GPU进行加速，并行计算

二、IndexIVFFlat

​ 聚类+倒排索引

​ 中大规模数据

2.1 核心原理

  • 倒排索引结构
    • 通过k均值对全量数据进行一个粗聚类，生成nlist个簇中心。
    • 查询时仅计算查询向量与最近nprobe个簇内的向量距离，大幅度减少计算量。

2.2 残差优化

​ 计算向量与中心节点的残差（即向量减去簇中心），存储残差相对位置而非原始向量。大幅度减少计算量。

残差优化可以理解为一种相对位置存储的策略，让距离计算更快。

具体过程如下：

1、聚类分群：

​ 所有向量通过聚类算法k均值分到不同的簇，每个簇都有一个中心点。

2、存储相对位置：

​ 假设某向量属于“簇A”，它的坐标是 [100, 200]，簇A的中心是 [90, 190]。这时不直接存储原始坐标 [100, 200]，而是存储它和中心点的‌相对位置‌（残差）：[100-90, 200-190] = [10, 10]。

3、查询时快速计算：

​ 计算相对位置的差异比计算从原点开始开始算，减少重复计算。

为什么更快呢？
  • 减少重复计算，查询时，大部分计算集中在簇中心和相对位置上，而不是所有原始数据。
  • 数值更小，计算更高效：残差通常比原始向量数值更小，计算时可能更快（尤其是涉及浮点运算时）。
类比理解：‌

​ 想象你在一个大型停车场找车：

  • 无残差优化‌：记住每辆车的绝对坐标（如“东经XXX，北纬XXX”），每次找车都要从地球原点开始算距离。

  • ‌残差优化‌：先记住你的车停在“A区”，然后记录它距离A区标志牌的位置（如“向北10米”）。找车时先定位到A区，再根据相对位置快速找到车。

三、IndexIVFPQ

聚类+乘积量化

超大规模数据/内存敏感

四、HNSW（Hierarchical Navigable Small World）

1
2
3
4
5
6
7
import faiss

d = 512  # 向量维度
M = 32   # 每层图的连接数（控制内存与精度）
index = faiss.IndexHNSWFlat(d, M)
index.add(data)  # 添加数据
index.hnsw.efSearch = 100  # 动态调整搜索深度（增大可提高精度）
  • M‌：每层图的连接数，越大精度越高但内存消耗增加（建议16-64）。
  • ‌efSearch‌：搜索时维护的候选队列大小，直接影响查询时间与精度。

‌一句话解释：‌

HNSW像建一座「多层交通枢纽」：

  • ‌高层（稀疏）‌：相当于‌高速公路‌，用少量关键连接快速跨区域导航（如北京→上海）
  • ‌底层（密集）‌：相当于‌城市道路‌，用密集连接精细搜索目标点（如上海浦东→某街道）

‌运作过程：‌

  1. ‌建造逻辑‌
    • ‌随机分层‌：每个数据点随机分配到不同层（高层概率低，底层概率高）
    • ‌层级连接‌：高层仅保留强关联节点（类似交通枢纽），底层保留所有细节路径
  2. ‌搜索逻辑‌
    • ‌从高层切入‌：像坐飞机快速跨省（跳过无关区域）
    • ‌逐层降落‌：每降一层增加连接密度，像换乘高铁→汽车→步行
    • ‌动态修正路径‌：每层用最近邻连接修正方向，避免绕远

‌优势对比：‌

结构 搜索方式 时间复杂度
单层稠密图 逐点遍历 O(N)
跳表 固定层级跳跃 O(logN)
‌HNSW‌ ‌动态跨层导航‌ ‌O(logN)‌（更稳定）

‌典型案例：‌ 假设在10亿人脸库中找人：

  • 高层：先对比「性别-年龄组」（快速排除90%数据）
  • 中层：筛选「发型-脸型」
  • 底层：精细比对「五官细节」

这种结构让搜索像「漏斗过滤」，越到底层越精准，总体速度比暴力搜索快100-1000倍。