Vamana#

Vamana is the graph construction algorithm behind the well-known DiskANN vector search solution. The cuVS implementation of Vamana/DiskANN is a custom GPU-acceleration version of the algorithm that aims to reduce index construction time using NVIDIA GPUs.

#include <cuvs/neighbors/vamana.hpp>

namespace cuvs::neighbors::vamana

Index build parameters#

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

Parameters used to build DiskANN index.

graph_degree: Maximum degree of graph; correspods to the R parameter of Vamana algorithm in the literature. visited_size: Maximum number of visited nodes per search during Vamana algorithm. Loosely corresponds to the L parameter in the literature. vamana_iters: The number of times all vectors are inserted into the graph. If > 1, all vectors are re-inserted to improve graph quality. max_fraction: The maximum batch size is this fraction of the total dataset size. Larger gives faster build but lower graph quality. alpha: Used to determine how aggressive the pruning will be.

Index#

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

Vamana index.

The index stores the dataset and the Vamana graph in device memory.

Template Parameters:

  • T – data element type

  • IdxT – type of the vector indices (represent dataset.extent(0))

Index build#

uint32_t graph_degree = 32

Maximum degree of output graph corresponds to the R parameter in the original Vamana literature.

uint32_t visited_size = 64#

Maximum number of visited nodes per search corresponds to the L parameter in the Vamana literature

uint32_t vamana_iters = 1#

Number of Vamana vector insertion iterations (each iteration inserts all vectors).

float alpha = 1.2#

Alpha for pruning parameter

float max_fraction = 0.06#

Maximum fraction of dataset inserted per batch. * Larger max batch decreases graph quality, but improves speed

float batch_base = 2#

Base of growth rate of batch sizes

uint32_t queue_size = 127#

Size of candidate queue structure - should be (2^x)-1

uint32_t reverse_batchsize = 1000000#

Max batchsize of reverse edge processing (reduces memory footprint)

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

Distance metric used for clustering.

inline IdxT size() const noexcept

Total length of the index (number of vectors).

inline uint32_t dim() const noexcept

Dimensionality of the data.

inline uint32_t graph_degree() const noexcept

Graph degree

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

Dataset [size, dim]

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

vamana graph [size, graph-degree]

inline IdxT medoid() const noexcept#

Return the id of the vector selected as the medoid.

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
)

Construct an empty index.

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
)#

Construct an index from dataset and vamana graph

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

Replace the graph with a new graph.

Since the new graph is a device array, we store a reference to that, and it is the caller’s responsibility to ensure that knn_graph stays alive as long as the index.

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

Replace the graph with a new graph.

We create a copy of the graph on the device. The index manages the lifetime of this copy.

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
)#

Build the index from the dataset for efficient DiskANN search.

The build utilities the Vamana insertion-based algorithm to create the graph. The algorithm starts with an empty graph and iteratively iserts batches of nodes. Each batch involves performing a greedy search for each vector to be inserted, and inserting it with edges to all nodes traversed during the search. Reverse edges are also inserted and robustPrune is applied to improve graph quality. The index_params struct controls the degree of the final graph.

The following distance metrics are supported:

  • L2

Usage example: 

  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);

Parameters:

  • res – [in]

  • params – [in] parameters for building the index

  • dataset – [in] a matrix view (device) to a row-major matrix [n_rows, dim]

Returns:

the constructed vamana index

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
)#

Build the index from the dataset for efficient DiskANN search.

The build utilities the Vamana insertion-based algorithm to create the graph. The algorithm starts with an empty graph and iteratively iserts batches of nodes. Each batch involves performing a greedy search for each vector to be inserted, and inserting it with edges to all nodes traversed during the search. Reverse edges are also inserted and robustPrune is applied to improve graph quality. The index_params struct controls the degree of the final graph.

The following distance metrics are supported:

  • L2

Usage example: 

  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);

Parameters:

  • res – [in]

  • params – [in] parameters for building the index

  • dataset – [in] a matrix view (host) to a row-major matrix [n_rows, dim]

Returns:

the constructed vamana index

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
)#

Build the index from the dataset for efficient DiskANN search.

The build utilities the Vamana insertion-based algorithm to create the graph. The algorithm starts with an empty graph and iteratively iserts batches of nodes. Each batch involves performing a greedy search for each vector to be inserted, and inserting it with edges to all nodes traversed during the search. Reverse edges are also inserted and robustPrune is applied to improve graph quality. The index_params struct controls the degree of the final graph.

The following distance metrics are supported:

  • L2

Usage example: 

  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);

Parameters:

  • res – [in]

  • params – [in] parameters for building the index

  • dataset – [in] a matrix view (device) to a row-major matrix [n_rows, dim]

Returns:

the constructed vamana index

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
)#

Build the index from the dataset for efficient DiskANN search.

The build utilities the Vamana insertion-based algorithm to create the graph. The algorithm starts with an empty graph and iteratively iserts batches of nodes. Each batch involves performing a greedy search for each vector to be inserted, and inserting it with edges to all nodes traversed during the search. Reverse edges are also inserted and robustPrune is applied to improve graph quality. The index_params struct controls the degree of the final graph.

The following distance metrics are supported:

  • L2

Usage example: 

  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);

Parameters:

  • res – [in]

  • params – [in] parameters for building the index

  • dataset – [in] a matrix view (host) to a row-major matrix [n_rows, dim]

Returns:

the constructed vamana index

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
)#

Build the index from the dataset for efficient DiskANN search.

The build utilities the Vamana insertion-based algorithm to create the graph. The algorithm starts with an empty graph and iteratively iserts batches of nodes. Each batch involves performing a greedy search for each vector to be inserted, and inserting it with edges to all nodes traversed during the search. Reverse edges are also inserted and robustPrune is applied to improve graph quality. The index_params struct controls the degree of the final graph.

The following distance metrics are supported:

  • L2

Usage example: 

  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);

Parameters:

  • res – [in]

  • params – [in] parameters for building the index

  • dataset – [in] a matrix view (device) to a row-major matrix [n_rows, dim]

Returns:

the constructed vamana index

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
)#

Build the index from the dataset for efficient DiskANN search.

The build utilities the Vamana insertion-based algorithm to create the graph. The algorithm starts with an empty graph and iteratively iserts batches of nodes. Each batch involves performing a greedy search for each vector to be inserted, and inserting it with edges to all nodes traversed during the search. Reverse edges are also inserted and robustPrune is applied to improve graph quality. The index_params struct controls the degree of the final graph.

The following distance metrics are supported:

  • L2

Usage example: 

  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);

Parameters:

  • res – [in]

  • params – [in] parameters for building the index

  • dataset – [in] a matrix view (host) to a row-major matrix [n_rows, dim]

Returns:

the constructed vamana index

Index serialize#

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

Save the index to file.

Matches the file format used by the DiskANN open-source repository, allowing cross-compatibility.

#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);
Parameters:

  • handle – [in] the raft handle

  • file_prefix – [in] prefix of path and name of index files

  • index – [in] Vamana index

  • include_dataset – [in] whether or not to serialize the dataset

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
)#

Save the index to file.

Matches the file format used by the DiskANN open-source repository, allowing cross-compatibility.

#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);
Parameters:

  • handle – [in] the raft handle

  • file_prefix – [in] prefix of path and name of index files

  • index – [in] Vamana index

  • include_dataset – [in] whether or not to serialize the dataset

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
)#

Save the index to file.

Matches the file format used by the DiskANN open-source repository, allowing cross-compatibility.

#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);
Parameters:

  • handle – [in] the raft handle

  • file_prefix – [in] prefix of path and name of index files

  • index – [in] Vamana index

  • include_dataset – [in] whether or not to serialize the dataset