Adam Chow's Life Journals

Appearance

IVFPQ ​

IVFPQ全称为「Inverted File System with Product Quantization 」，IVFPQ = IVF + PQ，由「倒排文件系统」和「乘积量化」两种技术协同合作实现FAISS极致的查询性能，这种方法既减少了需要搜索的向量数量(通过IVF)，又减少了查询向量和子空间中每个向量的距离计算复杂度(通过PQ两阶段的「预结算阶段」和「查表阶段」)。

IVFPQ图例：

[向量空间]
   |
   |--- [IVF区域1] -- 质心1
   |       |--- [PQ编码向量1]
   |       |--- [PQ编码向量2]
   |       ...
   |
   |--- [IVF区域2] -- 质心2
   |       |--- [PQ编码向量1]
   |       |--- [PQ编码向量2]
   |       ...
   ...

具体例子： 假设我们有100万个向量，使用1000个区域：

  • 传统方法：需要计算100万次距离。
  • IVFPQ方法：
    • 找到10个最近的桶（假设每个桶平均有1000个向量）。
    • 只需对这10,000个向量使用PQ方法计算距离即可。
  • 这将搜索空间减少了99%，同时PQ还能进一步加速距离计算。

倒排文件系统 (IVF) ​

IVF的核心思想是将向量空间（m条向量组成的超大型向量空间）划分为k个小区域（N条向量组成的小型向量子空间，N一般远小于m），每个区域有一个中心点（称为质心），作为一种粗粒度的索引。

  1. 索引构建阶段：
  • 使用K-means等聚类算法生成一定数量的质心。
  • 将每个待索引向量分配到与其在向量空间中「距离」最近的质心所对应的子空间中。 索引构建阶段的伪代码：
对于每个向量 x:
    找到最近的质心 i
    将 x 添加到子空间 i 中
  1. 搜索阶段：
  • 对于查询向量q，找到最近的t个质心（通常t远小于k）。
  • 只在这T个区域中进行精确搜索，使用PQ方法计算距离，这大大减少了搜索空间。 搜索阶段的伪代码：
1. 找到距离 q 最近的 t 个质心
2. 对于这 t 个区域中的每个向量:
    使用PQ方法计算与 q 的近似距离
3. 返回最相似的top-k个结果

乘积量化 (PQ) ​

PQ的核心思想是将高维向量分解为多个子向量，然后对每个子向量空间进行独立量化。

我们以一个1024维的向量举例：

  1. 向量分解： 一个1024维的向量可以被分解为8个128维的子向量。
[1024维向量] = [128维子向量1] + [128维子向量2] + ... + [128维子向量8]
  1. 子空间量化： 对于每个128维子空间，我们创建一个包含256个聚类中心的「codebook」，每个子向量都用其最近的聚类中心来表示。
[128维子向量] → [8位编码] (表示256个聚类中心中的一个)
  1. 压缩存储： 原始的1024维浮点向量（假设每个维度用4字节表示）需要4096字节存储。使用PQ后，我们只需要存储8个8位的编码（总空8个子向量，每个子向量用子空间的8位编码的聚类中心表示），总共8字节。
4096字节 → 8字节 (压缩率为512:1)
  1. 距离计算：
  • 4.1. 预计算表： 对于查询向量q，我们预先计算它的每个子向量与对应codebook中所有聚类中心的距离。
距离表[i][j] = distance(q的第i个子向量, 第i个codebook的第j个中心)，其中 i = [0, 7]，j = [0，255]
  • 4.2. 近似距离计算： 对于精搜区域中的向量x，其和查询向量q的距离可以通过查表并求和得到。
approximate_distance(q, x) = sum(距离表[i][x的第i个子向量的编码] for i in range(8))，其中 i = [0, 7]，x的第i个子向量的编码 = [0，255]
  1. 计算复杂度分析：
  • 原始方法：常规欧氏距离计算
距离 = sqrt((q[0] - x[0])^2 + (q[1] - x[1])^2 + ... + (q[1023] - x[1023])^2)

对于每个向量，这需要1024次减法，1024次平方，1023次加法和1次开方操作。

  • PQ方法： 对于查询向量q，我们预先计算它的每个子向量与对应codebook中所有聚类中心的距离（一次性计算）。
对于i从0到7:
    对于j从0到255:
        距离表[i][j] = distance(q的第i个子向量, 第i个codebook的第j个聚类中心)

对于数据库中的向量x，它在索引阶段已经被表示为8个编码 [c1, c2, ..., c8]，其中ci = [1, 256]。于是，近似距离计算变为：

近似距离 = 距离表[0][c1] + 距离表[1][c2] + ... + 距离表[7][c8]

这只需要8次查表操作和7次加法。 6. PQ过程图示：

Query Vector          :  [q1|q2|q3|...|q8]
                          |  |  |      |
                          v  v  v      v
Distance Lookup Table :  [T1|T2|T3|...|T8]
                          |  |  |     |
                          v  v  v     v
Indexed Vectors       :  [c1|c2|c3|...|c8]  (ci是子空间中某个聚类中心的编码)

Approximate Distance = T1[c1] + T2[c2] + T3[c3] + ... + T8[c8]
  1. 具体例子： 假设我们有，查询向量q = [1.2, 3.4, 5.6, 7.8]，我们将4维向量分成2个2维子向量，Codebook 1 = {[1, 3], [2, 4]}，Codebook 2 = {[5, 7], [6, 8]}。
  • 预计算步骤：
距离表[0][0] = distance([1.2, 3.4], [1, 3]) = 0.447
距离表[0][1] = distance([1.2, 3.4], [2, 4]) = 1.131
距离表[1][0] = distance([5.6, 7.8], [5, 7]) = 0.894
距离表[1][1] = distance([5.6, 7.8], [6, 8]) = 0.447
  • 如果数据库中有一个向量x被编码为[0, 1]，意味着：1）x的前两维最接近[1, 3]；2）x的后两维最接近[6, 8]。
  • 计算x与q的近似距离：
近似距离 = 距离表[0][0] + 距离表[1][1] = 0.447 + 0.447 = 0.894

这个过程只需要2次查表和1次加法，而不是原来的4次减法，4次平方，3次加法和1次开方。

总结 ​

IVF在IVFPQ中提供了一个粗粒度的过滤机制，显著减少了需要详细比较的向量数量。它与PQ的高效距离计算相结合，使得在大规模数据集上进行「近似最近邻搜索（Approximate Nearest Neighbor Search，简称ANN）」变得非常高效。这种方法牺牲了一些精度，换来了显著的速度提升，特别适合处理大规模高维数据。

HNSW ​

HNSW全称为「Hierarchical Navigable Small World」，是Faiss中另一种高效的高纬向量索引方法，特别适用于海量高维向量的近似最近邻搜索。

HNSW建立了一个多层图结构，每一层都是一个近似的"小世界"图：

[顶层] (稀疏连接)
|
v 
[中间层] (中等连接)
|
v 
[底层] (密集连接)

每个节点代表一个向量，节点间的边表示相似性连接。

  1. 图的构建过程： 从底层开始，逐层向上构建：
1. 插入新节点
2. 在当前层找到最近邻的节点
3. 与其建立连接
4. 概率性地决定是否将节点提升到上一层

示意图：

[L2]    o---o
         \ /
[L1]    o-o-o
        |/ \|
[L0]  o-o-o-o-o
  1. 图的搜索过程： 从顶层开始，逐层向下搜索:
1. 在当前层找到最近的节点
2. 向下一层移动，以上一层找到的节点为起点
3. 重复上述过程直到达到底层
4. 在底层进行细粒度搜索

示意图：

[L2]    o---●
         \ /
[L1]    o-●-o
        |/ \|
[L0]  o-●-●-●-o

(● 表示搜索路径)
  1. 关键特性
  • 多层结构
    • 顶层: 长距离连接，快速定位大致区域。
    • 底层: 短距离连接，精确定位最近邻。
  • 小世界性质
    • 每个节点都有一些远距离连接，保证了搜索的高效性。
  • 可导航性
    • 通过贪婪搜索就能快速找到近似最近邻。

IVFPQ vs HNSW ​

  1. IVFPQ (Inverted File System with Product Quantization)

角色：

  • 大规模向量检索的主要方法之一
  • 适合需要高压缩率的场景

优势：

  • 极高的压缩率，可以显著减少内存使用
  • 适合非常大的数据集（数百万到数十亿规模）
  • 查询速度很快，尤其是在GPU上

劣势：

  • 相比HNSW，召回率可能略低
  • 需要较多的参数调优

适用场景：

  • 超大规模数据集
  • 内存受限的环境
  • 对查询速度和内存使用有平衡要求的应用
  1. HNSW (Hierarchical Navigable Small World)

角色：

  • 高性能、高精度的近似最近邻搜索方法
  • 适合需要高召回率的场景

优势：

  • 非常高的查询速度
  • 高召回率，接近暴力搜索的精度
  • 支持动态插入
  • 对数据分布不敏感

劣势：

  • 内存消耗较大，不适合超大规模数据集
  • 构建索引时间可能较长

适用场景：

  • 中等规模数据集（百万级别）
  • 需要高召回率的应用
  • 对查询延迟要求极高的场景
  1. 在Faiss中的使用

IVFPQ:

  • 通常用于IndexIVFPQ类
  • 适合GPU加速
  • 可以与其他技术如IMI (Inverted Multi-Index) 结合使用

HNSW:

  • 通常用于IndexHNSW类
  • 主要在CPU上使用
  • 可以与其他量化方法（如PQ）结合，形成如IndexHNSWPQ
  1. 选择建议

  • 数据规模：

    • 数十亿级别 → IVFPQ
    • 百万级别 → HNSW 或 IVFPQ 都可以，取决于其他需求

  • 内存限制：

    • 严格 → IVFPQ
    • 宽松 → HNSW

  • 召回率要求：

    • 极高 → HNSW
    • 平衡 → IVFPQ

  • 查询速度要求：

    • 极快 → HNSW
    • 快速但可以牺牲一些精度 → IVFPQ