Vamana#

VAMANA 是用于构建 DiskANN 向量搜索解决方案索引的基础图构建算法。DiskANN 和 Vamana 算法在发表的论文中有详细描述，高度优化的开源存储库包含许多用于索引构建和搜索的功能。在 cuVS 中，我们提供了一个针对 GPU 架构优化的 Vamana 算法版本，以加速图构建来生成 DiskANN 索引。从高层次上看，Vamana 算法的工作流程如下

1. 从一个空图开始，从 D 维向量数据集中选择一个中心向量并将其插入图中。
1. 迭代地将批量数据集向量插入图中，根据图遍历将每个插入的向量连接到其邻居。
1. 对于每个批次，创建反向边并修剪不必要的边。

论文中概述了许多算法细节，并且此实现中包含了许多针对 GPU 的优化。

cuVS 中 DiskANN 当前的实现仅包含‘内存中’图构建和将索引写入文件的序列化步骤。然后，开源 DiskANN 库可以使用此索引文件来执行高效搜索。未来的 cuVS 版本计划增加 DiskANN 的其他功能，包括 GPU 加速搜索和‘ssd’索引构建。

[ C++ API | Python API ]

与 CPU DiskANN 的互操作性#

‘vamana::serialize’ API 调用将索引以兼容 open-source DiskANN repositoriy 的格式写入文件。这使得可以使用 cuVS 加速索引构建，同时利用当前可用的高效基于 CPU 的搜索。

配置参数#

构建参数#

名称	默认值	描述
graph_degree	32	最终 Vamana 图的最大度数。图的内部表示包含每个节点此数量的边，但序列化将图压缩为‘CSR’格式，边数可能更少。
visited_size	64	每次遍历以插入新节点时保存的最大已访问节点数。这对应于论文中的‘L’参数。
vamana_iters	1	运行以改进图的迭代次数。每次迭代都涉及插入数据集中的每个向量。
alpha	1.2	定义修剪边程度的 Alpha 参数。
max_fraction	0.06	将作为单个批次插入的数据集的最大比例。较大的最大批次大小会降低图的质量，但会提高速度。
batch_base	2	批次大小增长率的基数。插入批次大小根据此参数指数级增长，直到达到 max_fraction。
queue_size	127	图遍历期间使用的候选队列结构的大小。必须是某个 x 的 (2^x)-1，且必须 > visited_size。

调优考量#

最常调优的两个超参数是 graph_degree 和 visited_size。尤其是在增加 graph_degree 时，创建图所需的时间会显著增加。然而，对于大型数据集，可能需要更大的图来实现极高的召回率搜索。

内存占用#

Vamana 构建的图存储在设备内存中。但是，为了序列化索引并将其写入文件供以后使用，必须将其移至主机内存。如果同时设置了 include_dataset 参数，则在调用 serialize 时数据集也必须驻留在主机内存中。

设备内存使用#

构建的索引将图表示为固定度数，总共存储 \(graph\_degree * n\_index\_vectors\) 条边。图构建还需要数据集位于设备内存中（或者在构建期间将其复制到设备）。此外，构建期间会使用设备内存进行排序并创建反向边。因此，所需的设备内存量取决于数据集本身，但其上限为以下各项的总和

向量数据集：\(n\_index\_vectors * n\_dims * sizeof(T)\)
输出图：\(graph\_degree * n\_index\_vectors * sizeof(IdxT)\)
临时内存：\(n\_index\_vectors * max\_fraction * (2 + graph\_degree) * sizeof(IdxT)\)