CAGRA#
CAGRA，即 (C)UDA (A)NN (GRA)ph-based（基于 CUDA ANN 图），是一种基于图的索引，它大致基于流行的可导航小世界图 (NSG) 算法，但从头开始专门为 GPU 构建。CAGRA 通过首先构建训练点的 kNN 图，然后移除邻居之间的冗余路径来构建扁平图表示。
CAGRA 算法有两个基本步骤：* 1. 构建 kNN 图 * 2. 从 kNN 图中修剪冗余路径。
可以使用 I-force 构建初始 kNN 图。这将生成最准确的图，但会非常慢，我们发现在实践中 kNN 图不需要非常准确，因为修剪步骤有助于提高索引的整体召回率。cuVS 提供了 IVF-PQ 和 NN-Descent 策略来构建初始 kNN 图，这些策略可以在索引构建期间的索引参数对象中选择。
[ C API | C++ API | Python API | Rust API ]
与 HNSW 的互操作性#
cuVS 提供了将 CAGRA 图转换为 HNSW 图的功能，这使得 GPU 仅用于构建索引，而 CPU 可用于搜索。
过滤注意事项#
CAGRA 支持过滤搜索，并在分支 25.02 中改进了 multi-CTA 算法，以便在过滤率高达 90% 或更高的情况下提供合理的召回率和性能。
为了在过滤搜索中获得适当的召回率，需要根据过滤率设置搜索参数，但由于用户很难做到这一点，CAGRA 根据过滤率启发式地内部自动调整 itopk_size。如果要禁用此自动调整，请将搜索参数之一 filtering_rate 设置为 0.0，itopk_size 将不会自动调整。
配置参数#
构建参数#
名称 |
默认值 |
描述 |
|---|---|---|
compression |
None |
对于大型数据集，可以使用乘积量化压缩原始向量，以便将其放置在设备上。这会降低召回率，但在搜索后可以使用优化重排序步骤来弥补丢失的召回率。 |
graph_build_algo |
‘IVF_PQ’ |
用于构建图的构建算法 |
graph_build_params |
None |
指定对应图构建算法的显式构建参数 |
graph_degree |
32 |
最终 CAGRA 图的度。图中的所有顶点都将具有此度。在搜索期间，较大的图度允许更充分地探索搜索空间并提高召回率，但代价是搜索更多顶点。 |
intermediate_graph_degree |
64 |
在优化成最终 CAGRA 图之前的初始 knn 图的度。较大的值会增加初始图的连通性，以便在修剪后表现更好。较大的值会增加设备内存使用量并增加初始 knn 图构建的时间。 |
guarantee_connectivity |
False |
使用度约束最小生成树来保证初始 knn 图是连通的。这可以在某些数据集上提高召回率。 |
attach_data_on_build |
True |
数据集是否应在构建索引后附加到索引？将其设置为 |
搜索参数#
名称 |
默认值 |
描述 |
|---|---|---|
itopk_size |
64 |
搜索期间保留的中间搜索结果数量。此值需要 >=k。这是调整搜索性能的主要旋钮。 |
max_iterations |
0 |
搜索期间的最大迭代次数。默认是自动选择。 |
max_queries |
0 |
同时执行的最大搜索查询数（批大小）。默认是自动选择。 |
team_size |
0 |
用于计算每个距离的 CUDA 线程数。可以是 4、8、16 或 32。默认是自动选择。 |
search_width |
1 |
在每次迭代中选择作为搜索起点的顶点数量。 |
min_iterations |
0 |
要执行的最小搜索迭代次数 |
调优注意事项#
最常调优的 3 个超参数是 graph_degree、intermediate_graph_degree 和 itopk_size。
内存占用#
CAGRA 构建一个最终位于主机上的图，同时需要保留原始数据集（可以在主机或设备上）。
可以使用 IVFPQ 或 NN-DESCENT 来构建图（增加了上述相应构建算法中计算的峰值内存使用量）。
数据集在设备上（图在主机上）：#
索引内存占用（设备）： \(n\_index\_vectors * n\_dims * sizeof(T)\)
索引内存占用（主机）： \(graph\_degree * n\_index\_vectors * sizeof(T)`\)
数据集在主机上（图在主机上）：#
索引内存占用（主机）： \(n\_index\_vectors * n\_dims * sizeof(T) + graph\_degree * n\_index\_vectors * sizeof(T)\)
构建峰值内存使用量：#
使用 NN-descent / IVF-PQ 构建时，构建过程包含两个阶段：(1) 构建初始/（中间）图，然后 (2) 优化图。关键输入参数是 n_vectors、intermediate_graph_degree、graph_degree。第一阶段（构建）的内存使用量取决于所选方法。最大的分配是图 (n_vectors*intermediate_graph_degree)，但它存储在主机内存中。通常，第二阶段（优化）使用最多的设备内存。峰值内存使用量在修剪步骤 (graph_core.cuh/optimize) 优化期间达到：设备峰值内存使用量公式：\(n\_vectors * (4 + (sizeof(IdxT) + 1) * intermediate_degree)`\)
使用 out-of-core IVF-PQ 构建的峰值内存使用量：#
Out-of-core CAGA 构建包括 IVF-PQ 构建、IVF-PQ 搜索、CAGRA 优化。请注意，这些步骤是按顺序执行的，因此它们不是叠加的。
IVF-PQ 构建
IVF-PQ 搜索（设备上最大批大小为一次 1024 个向量）