根据应用场景选择索引

Milvus 目前支持的向量索引类型大都属于 ANNS(Approximate Nearest Neighbors Search,近似最近邻搜索)。ANNS 的核心思想是不再局限于只返回最精确的结果项,而是仅搜索可能是近邻的数据项,即以牺牲可接受范围内的精度的方式提高检索效率。

根据实现方式,ANNS 向量索引可分为四大类:

  • 基于树的索引

  • 基于图的索引

  • 基于哈希的索引

  • 基于量化的索引

下表将目前 Milvus 支持的索引进行了归类:

Milvus 支持的索引 索引分类 适用场景
FLAT N/A
  • 查询数据规模小
  • 需要 100% 的召回率。
IVF_FLAT 基于量化的索引
  • 高速查询
  • 要求高召回率
IVF_SQ8 基于量化的索引
  • 高速查询
  • 磁盘和内存资源有限
  • 查询召回率低于 IVF_FLAT
IVF_PQ 基于量化的索引
  • 超高速查询
  • 磁盘和内存资源有限
  • 可以接受偏低的查询召回率
RNSG 基于图的索引
  • 高速查询
  • 要求尽可能高的召回率
  • 建索引耗时长
HNSW 基于图的索引
  • 高速查询
  • 要求尽可能高的召回率
  • 内存空间大
ANNOY 基于树的索引
  • 低维向量空间

索引概览

FLAT

对于需要 100% 召回率且数据规模相对较小(百万级)的向量相似性搜索应用,FLAT 索引是一个很好的选择。FLAT 是指对向量进行原始文件存储,是唯一可以保证精确的检索结果的索引。FLAT 的结果也可以用于对照其他召回率低于 100% 的索引产生的结果。

FLAT 之所以精准是因为它采取了详尽查询的方法,即对于每个查询,目标输入都要与数据集中的每个向量进行比较。因此 FLAT 是列表中查询速度最慢的,而且不适合查询大量的向量数据。Milvus 中没有 FLAT 索引的参数,使用它不需要数据训练,也不需要占用额外的磁盘空间。

IVF_FLAT

IVF_FLAT 它通过聚类方法把空间里的点划分至 nlist 个单元,然后比较目标向量与所有单元中心的距离,选出 nprobe 个最近单元。然后比较这些被选中单元里的所有向量,得到最终的结果,极大地缩短了查询时间。

通过调整 nprobe,可以找到特定场景下查询准确性和查询速度之间的理想平衡。IVF_FLAT 性能测试结果表明,随着目标输入向量的数量(nq)和需要检索的集群数量(nprobe)的增加,查询时间也急剧增加。

IVF_FLAT 是最基础的 IVF 索引,存储在各个单元中的数据编码与原始数据一致。

  • 建索引参数

    参数 说明 取值范围
    nlist 聚类单元数 [1, 65536]
  • 查询参数

    参数 说明 取值范围
    nprobe 查询取的单元数 [1, 65536]

IVF_SQ8

由于 IVF_FLAT 未对原始的向量数据做任何压缩,IVF_FLAT 索引文件的大小与原始数据文件大小相当。例如 sift-1b 数据集原始数据文件的大小为 476 GB,生成的 IVF_FLAT 索引文件大小有 470 GB 左右,若将全部索引文件加载进内存,就需要 470 GB 的内存资源。

当磁盘或内存、显存资源有限时,IVF_SQ8 是一个更好的选择。它通过对向量进行标量量化(scalar quantization),能把原始向量中每个FLOAT(4 字节)转为UINT8(1 字节),从而可以把磁盘及内存、显存资源的消耗量减少为原来的 1/4 至 1/3。同样以 sift-1b 数据集为例,生成的 IVF_SQ8 索引文件只有 140 GB。

  • 建索引参数

    参数 说明 取值范围
    nlist 聚类单元数 [1, 65536]
  • 查询参数

    参数 说明 取值范围
    nprobe 查询取的单元数 [1, nlist]

IVF_PQ

PQ(Product Quantization,乘积量化)会将原来的高维向量空间均匀分解成 m 个低维向量空间的笛卡尔积,然后对分解得到的低维向量空间分别做矢量量化。最终每条向量会存储在 m × nbits 个 bit 位里。乘积量化能将全样本的距离计算转化为到各低维空间聚类中心的距离计算,从而大大降低算法的时间复杂度。

IVF_PQ 是先对向量做乘积量化,然后进行 IVF 索引聚类。其索引文件甚至可以比 IVF_SQ8 更小,不过同样地也会导致查询时的精度损失。

不同版本的建索引参数和查询参数设置不同,请根据使用的 Milvus 版本查看相应的参数信息。

  • 建索引参数

    参数 说明 取值范围
    nlist 聚类单元数  [1, 65536]
    m 乘积量化因子个数 dim ≡ 0 (mod m)
    nbits 分解后每个低维向量的存储位数 (可选) [1, 16](默认 8)
  • 查询参数

    参数 说明 取值范围
    nprobe 查询取的单元数 [1, nlist]

RNSG

RNSG(Refined Navigating Spreading-out Graph)是一种基于图的索引算法。它把全图中心位置设为导航点,然后通过特定的选边策略来控制每个点的出度(小于等于 out_degree),使得搜索时既能减少内存使用,又能快速定位到目标位置附近。

RNSG 的建图流程如下:

  1. 为每个点精确寻找 knng 个最近邻结点。
  2. knng 个最近邻结点为基础迭代至少 search_length 次,以选出 candidate_pool_size 个可能的最邻近结点。
  3. 在选出的 candidate_pool_size 个结点里按择边策略构建每个点的出边。

RNSG 的查询流程与建图流程类似,以导航点为起点至少迭代 search_length 次以得到最终结果。

  • 建索引参数

    参数 说明 取值范围
    out_degree 结点的最大出度 [5, 300]
    candidate_pool_size 结点出边候选池   [50, 1000]
    search_length 查询迭代次数   [10, 300]
    knng 预计算最近邻结点数   [5, 300]
  • 查询参数

    参数 说明 取值范围
    search_length 查询迭代次数 [10, 300]

HNSW

HNSW(Hierarchical Small World Graph)是一种基于图的索引算法。它会为一张图按规则建成多层导航图,并让越上层的图越稀疏,结点间的距离越远;越下层的图越稠密,结点间的距离越近。搜索时从最上层开始,找到本层距离目标最近的结点后进入下一层再查找。如此迭代,快速逼近目标位置。

为了提高性能,HNSW 限定了每层图上结点的最大度数 M 。此外,建索引时可以用 efConstruction,查询时可以用 ef 来指定搜索范围。

  • 建索引参数

    参数 说明 取值范围
    M 结点的最大度数 [4, 64]
    efConstruction 搜索范围 [8, 512]
  • 查询参数

    参数 说明 取值范围
    ef 搜索范围 [top_k, 32768]

Annoy

Annoy(Approximate Nearest Neighbors Oh Yeah)是一种用超平面把高维空间分割成多个子空间,并把这些子空间以树型结构存储的索引方式。

在查询时,Annoy 会顺着树结构找到距离目标向量较近的一些子空间,然后比较这些子空间里的所有向量(要求比较的向量数不少于 search_k 个)以获得最终结果。显然,当目标向量靠近某个子空间的边缘时,有时需要大大增加搜索的子空间数以获得高召回率。因此,Annoy 会使用 n_trees 次不同的方法来划分全空间,并同时搜索所有划分方法以减少目标向量总是处于子空间边缘的概率。

  • 建索引参数

    参数 说明   取值范围
    n_trees 空间划分的方法数 [1, 1024]
  • 查询参数

    参数 说明 取值范围
    search_k 搜索的结点数。-1 表示用全数据量的 5% {-1} ∪ [top_k, n × n_trees]

常见问题

Milvus 中 FLAT 索引和 IVF_FLAT 索引的原理比较?

把 FLAT 和 IVF_FLAT 做比较,可以这么估算:

已知 IVF_FLAT 索引是把向量分成 nlist 个单元。假设用默认的 nlist = 16384,搜索的时候是先用目标向量和这 16384 个中心点计算距离,得到最近的 nprobe 个单元,再在单元里计算最近向量。而 FLAT 是每条向量和目标向量计算距离。

所以当总的向量条数约等于 nlist 时,两者的计算量相当,性能也差不多。而随着向量条数达到 nlist 的 2 倍、3 倍、n 倍之后,IVF_FLAT 的优势就越来越大。

可参阅 如何选择索引类型

参考文献

该页面是否对你有帮助?
评价成功!