Vamana#

Vamana 是著名的 DiskANN 向量搜索解决方案背后的图构造算法。cuVS 实现的 Vamana/DiskANN 是该算法的定制 GPU 加速版本，旨在利用 NVIDIA GPU 缩短索引构建时间。

#include <cuvs/neighbors/vamana.hpp>

namespace cuvs::neighbors::vamana

索引构建参数#

struct index_params : public cuvs::neighbors::index_params#
#include <vamana.hpp>

用于构建 DiskANN 索引的参数。

graph_degree：图的最大度；对应于文献中 Vamana 算法的 R 参数。visited_size：Vamana 算法期间每次搜索访问的最大节点数。大致对应于文献中的 L 参数。vamana_iters：所有向量插入图的次数。如果 > 1，所有向量将被重新插入以提高图质量。max_fraction：最大批处理大小占总数据集大小的该分数。值越大，构建速度越快，但图质量越低。alpha：用于确定剪枝的积极程度。

索引#

template<typename T, typename IdxT>
struct index : public cuvs::neighbors::index#
#include <vamana.hpp>

Vamana 索引。

索引在设备内存中存储数据集和 Vamana 图。

模板参数:

  • T – 数据元素类型

  • IdxT – 向量索引的类型（表示 dataset.extent(0)）

索引构建#

uint32_t graph_degree = 32

输出图的最大度对应于原始 Vamana 文献中的 R 参数。

uint32_t visited_size = 64#

每次搜索访问的最大节点数对应于 Vamana 文献中的 L 参数

uint32_t vamana_iters = 1#

Vamana 向量插入迭代次数（每次迭代插入所有向量）。

float alpha = 1.2#

用于剪枝参数的 Alpha 值

float max_fraction = 0.06#

每次分批插入的最大数据集比例。* 更大的最大批处理会降低图质量，但提高速度

float batch_base = 2#

批处理大小增长率的基数

uint32_t queue_size = 127#

候选队列结构的大小 - 应为 (2^x)-1

uint32_t reverse_batchsize = 1000000#

反向边处理的最大批处理大小（减少内存占用）

inline cuvs::distance::DistanceType metric() const noexcept

用于聚类的距离度量。

inline IdxT size() const noexcept

索引的总长度（向量数）。

inline uint32_t dim() const noexcept

数据的维度。

inline uint32_t graph_degree() const noexcept

图的度

inline const cuvs::neighbors::dataset<int64_t> &data(
) const noexcept

数据集 [size, dim]

inline raft::device_matrix_view<const IdxT, int64_t, raft::row_major> graph(
) const noexcept

vamana 图 [size, graph-degree]

inline IdxT medoid() const noexcept#

返回被选为中心点的向量 ID。

index(const index&) = delete
index(index&&) = default
index &=delete operator= (const index &)
index &=default operator= (index &&)
~index() = default
inline index(
raft::resources const &res,
cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Expanded
)

构造一个空索引。

template<typename data_accessor, typename graph_accessor>
inline index(
raft::resources const &res,
cuvs::distance::DistanceType metric,
raft::mdspan<const T, raft::matrix_extent<int64_t>, raft::row_major, data_accessor> dataset,
raft::mdspan<const IdxT, raft::matrix_extent<int64_t>, raft::row_major, graph_accessor> vamana_graph,
IdxT medoid_id
)#

从数据集和 vamana 图构造索引

inline void update_graph(
raft::resources const &res,
raft::device_matrix_view<const IdxT, int64_t, raft::row_major> new_graph
)

用新图替换现有图。

由于新图是设备数组，我们存储对其的引用，调用方有责任确保 knn_graph 在索引的生命周期内保持有效。

inline void update_graph(
raft::resources const &res,
raft::host_matrix_view<const IdxT, int64_t, raft::row_major> new_graph
)

用新图替换现有图。

我们在设备上创建图的副本。索引管理此副本的生命周期。

cuvs::neighbors::vamana::index<float, uint32_t> build(
raft::resources const &res,
const cuvs::neighbors::vamana::index_params &params,
raft::device_matrix_view<const float, int64_t, raft::row_major> dataset
)#

从数据集构建索引以实现高效的 DiskANN 搜索。

构建利用基于 Vamana 插入的算法创建图。该算法从空图开始，迭代插入批处理节点。每个批处理都涉及对每个要插入的向量执行贪婪搜索，并将其以及与搜索过程中遍历的所有节点的边一起插入。还插入反向边并应用 robustPrune 以提高图质量。index_params 结构控制最终图的度。

支持以下距离度量

  • L2

使用示例

  using namespace cuvs::neighbors;
  // use default index parameters;
  vamana::index_params index_params;
  // create and fill index from a [N, D] dataset;
  auto index = vamana::build(res, index_params, dataset);
  // write index to file to be used by CPU-based DiskANN search (cuVS does not yet support
search) vamana::serialize(res, filename, index);

参数:

  • res – [in]

  • params – [in] 构建索引的参数

  • dataset – [in] 到行主序矩阵 [n_rows, dim] 的矩阵视图（设备）

返回:

构建的 vamana 索引

cuvs::neighbors::vamana::index<float, uint32_t> build(
raft::resources const &res,
const cuvs::neighbors::vamana::index_params &params,
raft::host_matrix_view<const float, int64_t, raft::row_major> dataset
)#

从数据集构建索引以实现高效的 DiskANN 搜索。

构建利用基于 Vamana 插入的算法创建图。该算法从空图开始，迭代插入批处理节点。每个批处理都涉及对每个要插入的向量执行贪婪搜索，并将其以及与搜索过程中遍历的所有节点的边一起插入。还插入反向边并应用 robustPrune 以提高图质量。index_params 结构控制最终图的度。

支持以下距离度量

  • L2

使用示例

  using namespace cuvs::neighbors;
  // use default index parameters;
  vamana::index_params index_params;
  // create and fill index from a [N, D] dataset;
  auto index = vamana::build(res, index_params, dataset);
  // write index to file to be used by CPU-based DiskANN search (cuVS does not yet support
search) vamana::serialize(res, filename, index);

参数:

  • res – [in]

  • params – [in] 构建索引的参数

  • dataset – [in] 到行主序矩阵 [n_rows, dim] 的矩阵视图（主机）

返回:

构建的 vamana 索引

cuvs::neighbors::vamana::index<int8_t, uint32_t> build(
raft::resources const &res,
const cuvs::neighbors::vamana::index_params &params,
raft::device_matrix_view<const int8_t, int64_t, raft::row_major> dataset
)#

从数据集构建索引以实现高效的 DiskANN 搜索。

构建利用基于 Vamana 插入的算法创建图。该算法从空图开始，迭代插入批处理节点。每个批处理都涉及对每个要插入的向量执行贪婪搜索，并将其以及与搜索过程中遍历的所有节点的边一起插入。还插入反向边并应用 robustPrune 以提高图质量。index_params 结构控制最终图的度。

支持以下距离度量

  • L2

使用示例

  using namespace cuvs::neighbors;
  // use default index parameters;
  vamana::index_params index_params;
  // create and fill index from a [N, D] dataset;
  auto index = vamana::build(res, index_params, dataset);
  // write index to file to be used by CPU-based DiskANN search (cuVS does not yet support
search) vamana::serialize(res, filename, index);

参数:

  • res – [in]

  • params – [in] 构建索引的参数

  • dataset – [in] 到行主序矩阵 [n_rows, dim] 的矩阵视图（设备）

返回:

构建的 vamana 索引

cuvs::neighbors::vamana::index<int8_t, uint32_t> build(
raft::resources const &res,
const cuvs::neighbors::vamana::index_params &params,
raft::host_matrix_view<const int8_t, int64_t, raft::row_major> dataset
)#

从数据集构建索引以实现高效的 DiskANN 搜索。

构建利用基于 Vamana 插入的算法创建图。该算法从空图开始，迭代插入批处理节点。每个批处理都涉及对每个要插入的向量执行贪婪搜索，并将其以及与搜索过程中遍历的所有节点的边一起插入。还插入反向边并应用 robustPrune 以提高图质量。index_params 结构控制最终图的度。

支持以下距离度量

  • L2

使用示例

  using namespace cuvs::neighbors;
  // use default index parameters;
  vamana::index_params index_params;
  // create and fill index from a [N, D] dataset;
  auto index = vamana::build(res, index_params, dataset);
  // write index to file to be used by CPU-based DiskANN search (cuVS does not yet support
search) vamana::serialize(res, filename, index);

参数:

  • res – [in]

  • params – [in] 构建索引的参数

  • dataset – [in] 到行主序矩阵 [n_rows, dim] 的矩阵视图（主机）

返回:

构建的 vamana 索引

cuvs::neighbors::vamana::index<uint8_t, uint32_t> build(
raft::resources const &res,
const cuvs::neighbors::vamana::index_params &params,
raft::device_matrix_view<const uint8_t, int64_t, raft::row_major> dataset
)#

从数据集构建索引以实现高效的 DiskANN 搜索。

构建利用基于 Vamana 插入的算法创建图。该算法从空图开始，迭代插入批处理节点。每个批处理都涉及对每个要插入的向量执行贪婪搜索，并将其以及与搜索过程中遍历的所有节点的边一起插入。还插入反向边并应用 robustPrune 以提高图质量。index_params 结构控制最终图的度。

支持以下距离度量

  • L2

使用示例

  using namespace cuvs::neighbors;
  // use default index parameters;
  vamana::index_params index_params;
  // create and fill index from a [N, D] dataset;
  auto index = vamana::build(res, index_params, dataset);
  // write index to file to be used by CPU-based DiskANN search (cuVS does not yet support
search) vamana::serialize(res, filename, index);

参数:

  • res – [in]

  • params – [in] 构建索引的参数

  • dataset – [in] 到行主序矩阵 [n_rows, dim] 的矩阵视图（设备）

返回:

构建的 vamana 索引

cuvs::neighbors::vamana::index<uint8_t, uint32_t> build(
raft::resources const &res,
const cuvs::neighbors::vamana::index_params &params,
raft::host_matrix_view<const uint8_t, int64_t, raft::row_major> dataset
)#

从数据集构建索引以实现高效的 DiskANN 搜索。

构建利用基于 Vamana 插入的算法创建图。该算法从空图开始，迭代插入批处理节点。每个批处理都涉及对每个要插入的向量执行贪婪搜索，并将其以及与搜索过程中遍历的所有节点的边一起插入。还插入反向边并应用 robustPrune 以提高图质量。index_params 结构控制最终图的度。

支持以下距离度量

  • L2

使用示例

  using namespace cuvs::neighbors;
  // use default index parameters;
  vamana::index_params index_params;
  // create and fill index from a [N, D] dataset;
  auto index = vamana::build(res, index_params, dataset);
  // write index to file to be used by CPU-based DiskANN search (cuVS does not yet support
search) vamana::serialize(res, filename, index);

参数:

  • res – [in]

  • params – [in] 构建索引的参数

  • dataset – [in] 到行主序矩阵 [n_rows, dim] 的矩阵视图（主机）

返回:

构建的 vamana 索引

索引序列化#

void serialize(
raft::resources const &handle,
const std::string &file_prefix,
const cuvs::neighbors::vamana::index<float, uint32_t> &index,
bool include_dataset = true
)#

将索引保存到文件。

匹配 DiskANN 开源仓库使用的文件格式，实现跨兼容性。

#include <raft/core/resources.hpp>
#include <cuvs/neighbors/vamana.hpp>

raft::resources handle;

// create a string with a filepath
std::string file_prefix("/path/to/index/prefix");
// create an index with `auto index = cuvs::neighbors::vamana::build(...);`
cuvs::neighbors::vamana::serialize(handle, file_prefix, index);
参数:

  • handle – [in] raft 句柄

  • file_prefix – [in] 索引文件的路径和名称前缀

  • index – [in] Vamana 索引

  • include_dataset – [in] 是否序列化数据集

void serialize(
raft::resources const &handle,
const std::string &file_prefix,
const cuvs::neighbors::vamana::index<int8_t, uint32_t> &index,
bool include_dataset = true
)#

将索引保存到文件。

匹配 DiskANN 开源仓库使用的文件格式，实现跨兼容性。

#include <raft/core/resources.hpp>
#include <cuvs/neighbors/vamana.hpp>

raft::resources handle;

// create a string with a filepath
std::string file_prefix("/path/to/index/prefix");
// create an index with `auto index = cuvs::neighbors::vamana::build(...);`
cuvs::neighbors::vamana::serialize(handle, file_prefix, index);
参数:

  • handle – [in] raft 句柄

  • file_prefix – [in] 索引文件的路径和名称前缀

  • index – [in] Vamana 索引

  • include_dataset – [in] 是否序列化数据集

void serialize(
raft::resources const &handle,
const std::string &file_prefix,
const cuvs::neighbors::vamana::index<uint8_t, uint32_t> &index,
bool include_dataset = true
)#

将索引保存到文件。

匹配 DiskANN 开源仓库使用的文件格式，实现跨兼容性。

#include <raft/core/resources.hpp>
#include <cuvs/neighbors/vamana.hpp>

raft::resources handle;

// create a string with a filepath
std::string file_prefix("/path/to/index/prefix");
// create an index with `auto index = cuvs::neighbors::vamana::build(...);`
cuvs::neighbors::vamana::serialize(handle, file_prefix, index);
参数:

  • handle – [in] raft 句柄

  • file_prefix – [in] 索引文件的路径和名称前缀

  • index – [in] Vamana 索引

  • include_dataset – [in] 是否序列化数据集