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 <raft/neighbors/vamana.h>

Index build parameters#

typedef struct cuvsVamanaIndexParams *cuvsVamanaIndexParams_t#
cuvsError_t cuvsVamanaIndexParamsCreate(
cuvsVamanaIndexParams_t *params
)#

Allocate Vamana Index params, and populate with default values.

Parameters:

params – [in] cuvsVamanaIndexParams_t to allocate

Returns:

cuvsError_t

cuvsError_t cuvsVamanaIndexParamsDestroy(
cuvsVamanaIndexParams_t params
)#

De-allocate Vamana Index params.

Parameters:

params – [in] cuvsVamanaIndexParams_t to de-allocate

Returns:

cuvsError_t

struct cuvsVamanaIndexParams#
#include <vamana.h>

Supplemental parameters to build Vamana Index.

graph_degree: Maximum degree of graph; corresponds 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.

Public Members

cuvsDistanceType metric#

Distance type.

uint32_t graph_degree#

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

uint32_t visited_size#

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

float vamana_iters#

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

float alpha#

Alpha for pruning parameter

float max_fraction#

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

float batch_base#

Base of growth rate of batch sizes

uint32_t queue_size#

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

uint32_t reverse_batchsize#

Max batchsize of reverse edge processing (reduces memory footprint)

Index#

typedef cuvsVamanaIndex *cuvsVamanaIndex_t#
cuvsError_t cuvsVamanaIndexCreate(cuvsVamanaIndex_t *index)#

Allocate Vamana index.

Parameters:

index – [in] cuvsVamanaIndex_t to allocate

Returns:

cuvsError_t

cuvsError_t cuvsVamanaIndexDestroy(cuvsVamanaIndex_t index)#

De-allocate Vamana index.

Parameters:

index – [in] cuvsVamanaIndex_t to de-allocate

Returns:

cuvsError_t

cuvsError_t cuvsVamanaIndexGetDims(cuvsVamanaIndex_t index, int *dim)#

Get the dimension of the index.

Parameters:

  • index – [in] cuvsVamanaIndex_t to get dimension of

  • dim – [out] pointer to dimension to set

Returns:

cuvsError_t

struct cuvsVamanaIndex#
#include <vamana.h>

Struct to hold address of cuvs::neighbors::vamana::index and its active trained dtype.

Index build#

cuvsError_t cuvsVamanaBuild(
cuvsResources_t res,
cuvsVamanaIndexParams_t params,
DLManagedTensor *dataset,
cuvsVamanaIndex_t index
)#

Build Vamana index.

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 inserts 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: 

// Create cuvsResources_t
cuvsResources_t res;
cuvsResourcesCreate(&res);

// Assume a row-major dataset [n_rows, n_cols] is defined as `float* dataset`
cuvsVamanaIndexParams_t index_params;
cuvsVamanaIndexParamsCreate(&index_params);
index_params->metric = L2Expanded; // set distance metric
cuvsVamanaIndex_t index;
cuvsVamanaIndexCreate(&index);
cuvsVamanaBuild(res, index_params, dataset, index);

Parameters:
Returns:

cuvsError_t

Index serialize#

cuvsError_t cuvsVamanaSerialize(
cuvsResources_t res,
const char *filename,
cuvsVamanaIndex_t index,
bool include_dataset
)#

Save Vamana index to file.

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

Serialized Index is to be used by the DiskANN open-source repository for graph search.

// Create cuvsResources_t
cuvsResources_t res;
cuvsResourcesCreate(&res);

// create an index with `cuvsVamanaBuild`
cuvsVamanaSerialize(res, "/path/to/index", index, true);
Parameters:

  • res – [in] cuvsResources_t opaque C handle

  • filename – [in] the file prefix for where the index is saved

  • index – [in] cuvsVamanaIndex_t to serialize

  • include_dataset – [in] whether to include the dataset in the serialized index

Returns:

cuvsError_t