IVF_PQ

IVF_PQ 索引是一种 基于量化的 索引算法，用于高维空间中的近似近邻搜索。虽然速度不如某些基于图的方法，但 IVF_PQ 通常所需的内存要少得多，因此是大型数据集的实用选择。

概述

IVF_PQ 是 Inverted File with Product Quantization 的缩写，是一种结合索引和压缩的混合方法，用于高效的向量搜索和检索。它利用了两个核心组件 ：倒排文件 (IVF) 和 乘积量化 (PQ )。

倒排文件

IVF 就像在一本书中创建索引。你不用扫描每一页（或者，在我们的情况下，每一个向量），而是在索引中查找特定的关键词（群组），从而快速找到相关的页面（向量）。在我们的方案中，向量被归入簇，算法将在与查询向量接近的几个簇内进行搜索。

下面是其工作原理：

1. 聚类：使用 k-means 等聚类算法，将向量数据集划分为指定数量的簇。每个聚类都有一个中心点（聚类的代表向量）。

2. 分配：每个向量被分配到其中心点最接近的聚类中。

3. 倒排索引：创建一个索引，将每个聚类的中心点映射到分配给该聚类的向量列表中。

4. 搜索：搜索近邻时，搜索算法会将查询向量与集群中心点进行比较，并选择最有希望的集群。然后将搜索范围缩小到这些选定簇内的向量。

要了解更多技术细节，请参阅 IVF_FLAT。

PQ

乘积量化（PQ） 是一种针对高维向量的压缩方法，可显著降低存储需求，同时实现快速的相似性搜索操作。

PQ 过程包括以下几个关键阶段：

1. 维度分解：该算法首先将每个高维向量分解为 m 大小相等的子向量。这种分解将原始的 D 维空间转换为 m 不相交的子空间，其中每个子空间包含D/m维。参数 m 控制分解的粒度，并直接影响压缩比。

2. 子空间编码本生成：在每个子空间内，算法应用 k-means 聚类 来学习一组代表性向量（中心点）。汇总这些中心点就形成了该子空间的代码集。每个编码本中的中心点数量由参数 nbits 决定，其中每个 Codebook 包含 $2^{\textit{nbits}}$ 个中心点。例如，如果 nbits = 8，每个编码本将包含 256 个中心点。每个中心点都有一个唯一的索引，索引位数为 nbits。

3. 向量 量化：对于原始向量中的每个子向量，PQ 会使用特定的度量类型在相应的子空间内识别其最近的中心点。这一过程可有效地将每个子向量映射到编码本中与其最接近的代表向量。PQ 不存储完整的子向量坐标，只保留匹配中心点的索引。

4. 压缩表示：最终的压缩表示由 m 索引组成，每个子空间一个索引，统称为 PQ 编码。这种编码方式将存储需求从D × 32位（假设为 32 位浮点数）减少到m×nbits位，在保留近似向量距离能力的同时实现了大幅压缩。

有关参数调整和优化的更多详情，请参阅 索引参数。

说明

考虑一个使用 32 位浮点数的D = 128维向量。在 PQ 参数m = 64（子向量）和nbits = 8（因此每个子空间包含 k = 2⁸ = 256 个中心点）的情况下，我们可以比较存储需求：

• 原始向量：128 维 × 32 位 = 4,096 位

• PQ 压缩向量：64 个子向量 × 8 位 = 512 位

这意味着存储需求减少了 8 倍。

使用 PQ 计算距离

在使用查询向量进行相似性搜索时，PQ 可通过以下步骤实现高效的距离计算：

1. 查询预处理

• 将查询向量分解为 m 个子向量，与原始 PQ 分解结构相匹配。

• 对于每个查询子向量及其相应的编码本（包含 $2^{\textit{nbits}}$ 个中心点），计算并存储与所有中心点的距离。

• 这将生成 m 查找表，其中每个表都包含 $2^{\textit{nbits}}$ 个距离值。

2. 距离近似

对于任何由 PQ 代码表示的数据库向量，其与查询向量的近似距离计算如下：

• 对于 m 的每个子向量，使用存储的中心点索引从相应的查找表中检索预先计算的距离。

• 将这些 m 距离相加，得出基于特定度量类型（如欧氏距离）的近似距离。

IVF + PQ

IVF_PQ 索引结合了 IVF 和 PQ 的优势，可加快搜索速度。这一过程分为两个步骤：

1. 利用 IVF 进行粗过滤：IVF 将向量空间划分为簇，缩小了搜索范围。该算法不评估整个数据集，而只关注与查询向量最接近的簇。

2. 与 PQ 进行细粒度比较：在选定的簇内，PQ 使用压缩和量化的向量表示来快速计算近似距离。

控制 IVF 和 PQ 算法的参数对 IVF_PQ 索引的性能影响很大。调整这些参数对特定数据集和应用获得最佳结果至关重要。有关这些参数以及如何调整 参数 的详细信息，请参阅 索引参数。

建立索引

要在 Milvus 中的向量字段上建立 IVF_PQ 索引，请使用 add_index() 方法，指定 index_type、metric_type 以及索引的附加参数。

Python

Python

from pymilvus import MilvusClient

client = MilvusClient(uri="http://localhost:19530")
index_params = client.prepare_index_params()
index_params.add_index(
    field_name="your_vector_field_name",
    index_type="IVF_PQ",
    index_name="vector_index",
    metric_type="L2",
    params={
        "m": 4
    },
)

client.create_index(
    collection_name="your_collection_name",
    index_params=index_params,
)

Java

Java

import io.milvus.v2.common.IndexParam;
import io.milvus.v2.service.index.request.CreateIndexReq;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
import java.util.Collections;

Map<String, Object> extraParams = new HashMap<>();
extraParams.put("m", 4);
IndexParam indexParam = IndexParam.builder()
    .fieldName("your_vector_field_name")
    .indexName("vector_index")
    .indexType(IndexParam.IndexType.IVF_PQ)
    .metricType(IndexParam.MetricType.L2)
    .extraParams(extraParams)
    .build();

client.createIndex(CreateIndexReq.builder()
    .collectionName("your_collection_name")
    .indexParams(Collections.singletonList(indexParam))
    .build());

Node.js

JavaScript

await client.createIndex({
  "collection_name": "your_collection_name",
  "field_name": "your_vector_field_name",
  "index_name": "vector_index",
  "index_type": "IVF_PQ",
  "metric_type": "L2",
  "params": {
    "m": 4
  }
});

Go

Go

idx := index.NewGenericIndex("", map[string]string{
    "index_type": "IVF_PQ",
    "metric_type": "L2",
    "m": "4",
})
task, err := client.CreateIndex(
    ctx,
    milvusclient.NewCreateIndexOption(
        "your_collection_name",
        "your_vector_field_name",
        idx,
    ).WithIndexName("vector_index"),
)
if err != nil {
    panic(err)
}
if err := task.Await(ctx); err != nil {
    panic(err)
}

cURL

Shell

curl --request POST \
  --url "http://localhost:19530/v2/vectordb/indexes/create" \
  --header "Authorization: Bearer root:Milvus" \
  --header "Content-Type: application/json" \
  --data '{
  "collectionName": "your_collection_name",
  "indexParams": [
    {
      "fieldName": "your_vector_field_name",
      "indexName": "vector_index",
      "indexType": "IVF_PQ",
      "metricType": "L2",
      "params": {
        "m": 4
      }
    }
  ]
}'

在此配置中

• index_type：要建立的索引类型。在本例中，将值设为 IVF_PQ。

• metric_type：用于计算向量间距离的方法。支持的值包括 COSINE,L2, 和 IP。有关详情，请参阅 度量类型。

• params：用于建立索引的附加配置选项。

• m：将向量分割成的子向量个数。

要了解 IVF_PQ 索引可用的更多构建 参数，请参阅 索引构建参数。

配置好索引参数后，可直接使用 create_index() 方法或在 create_collection 方法中传递索引参数来创建索引。有关详情，请参阅 创建 Collection。

在索引上搜索

建立索引并插入实体后，就可以在索引上执行相似性搜索。

Python

search_params = {
    "params": {
        "nprobe": 10, # Number of clusters to search
    }
}

res = MilvusClient.search(
    collection_name="your_collection_name", # Collection name
    anns_field="vector_field", # Vector field name
    data=[[0.1, 0.2, 0.3, 0.4, 0.5]],  # Query vector
    limit=3,  # TopK results to return
    search_params=search_params
)

在此配置中

• params：在索引上搜索的其他配置选项。

• nprobe：要搜索的集群数量。

要了解 IVF_PQ 索引可用的更多搜索 参数，请参阅 特定于索引的搜索参数。

索引参数

本节概述了用于建立索引和在索引上执行搜索的参数。

索引建立参数

下表列出了 建立索引 时可在 params 中配置的参数。

	参数	说明	值范围	调整建议
IVF	nlist	在索引创建过程中使用 k-means 算法创建的簇数。	类型：整数 范围：[1, 65536] 默认值：128	nlist 值越大，创建的簇越精细，召回率越高，但会增加索引构建时间。请根据数据集大小和可用资源进行优化。大多数情况下，我们建议在此范围内设置值：[32, 4096].
PQ	m	在量化过程中将每个高维向量分成的子向量数（用于量化）。	类型：整数 范围：[1, 65536] 默认值：无	增大 m 可以提高准确率，但也会增加计算复杂度和内存占用。m 必须是向量维数(D) 的除数，以确保正确分解。通常推荐的值是m = D/2。 在大多数情况下，我们建议在此范围内设置一个值：[D/8，D]。
	nbits	用于以压缩形式表示每个子向量中心点索引的比特数。它直接决定了每个编码本的大小。每个 Codebook 包含 2nbits 个中心点。例如，如果 nbits 设置为 8，则每个子向量将由一个 8 位的中心点索引表示。这样，该子向量的编码本中就有28（256）个可能的中心点。	类型：整数 范围：[1, 24] 默认值：8	nbits 值越大，编码本越大，可能会更精确地表示原始向量。不过，这也意味着要使用更多比特来存储每个索引，从而导致压缩率降低。在大多数情况下，我们建议在此范围内设置一个值：[1, 16].

特定于索引的搜索参数

下表列出了在 search_params.params 中 对索引进行搜索 时可以配置的参数。

	参数	说明	值范围	调整建议
IVF	nprobe	搜索候选集群的集群数。	类型：整数 范围：[1, nlist] 默认值：8	数值越大，搜索的簇数越多，搜索范围扩大，召回率提高，但代价是查询延迟增加。设置 nprobe 与 nlist 成比例，以平衡速度和准确性。 在大多数情况下，我们建议您在此范围内设置值：[1，nlist]。