Neighbors Vamana

Source header: cuvs/neighbors/vamana.hpp

Vamana index build parameters

neighbors::vamana::codebook_params

Parameters used to build quantized DiskANN index; to be generated using

deserialize_codebooks()

1 template <typename T = float>
2 struct codebook_params { ... };

Fields

Name	Type	Description
`pq_codebook_size`	`int`
`pq_dim`	`int`
`pq_encoding_table`	`std::vector<T>`
`rotation_matrix`	`std::vector<T>`

neighbors::vamana::index_params

Parameters used to build DiskANN index

1 struct index_params : cuvs::neighbors::index_params { ... };

Fields

Name	Type	Description
`graph_degree`	`uint32_t`	Maximum degree of graph; corresponds to the R parameter of Vamana algorithm in the literature.
`visited_size`	`uint32_t`	Maximum number of visited nodes per search during Vamana algorithm. Loosely corresponds to the L parameter in the literature.
`vamana_iters`	`float`	The number of times all vectors are inserted into the graph. If > 1, all vectors are re-inserted to improve graph quality.
`alpha`	`float`	Used to determine how aggressive the pruning will be.
`max_fraction`	`float`	The maximum batch size is this fraction of the total dataset size. Larger gives faster build but lower graph quality.
`batch_base`	`float`	Base of growth rate of batch sizes *
`queue_size`	`uint32_t`	Size of candidate queue structure - should be (2^x)-1
`reverse_batchsize`	`uint32_t`	Max batchsize of reverse edge processing (reduces memory footprint)
`codebooks`	`std::optional<codebook_params<float>>`	Codebooks and related parameters

Vamana index type

neighbors::vamana::index

Vamana index.

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

1 template <typename T, typename IdxT>
2 struct index : cuvs::neighbors::index { ... };

neighbors::vamana::index::metric

Distance metric used for clustering.

1 [[nodiscard]] constexpr inline auto metric() const noexcept -> cuvs::distance::DistanceType;

Returns

cuvs::distance::DistanceType

neighbors::vamana::index::size

Total length of the index (number of vectors).

1 [[nodiscard]] constexpr inline auto size() const noexcept -> IdxT;

Returns

IdxT

neighbors::vamana::index::dim

Dimensionality of the data.

1 [[nodiscard]] constexpr inline auto dim() const noexcept -> uint32_t;

Returns

uint32_t

neighbors::vamana::index::graph_degree

Graph degree

1 [[nodiscard]] constexpr inline auto graph_degree() const noexcept -> uint32_t;

Returns

uint32_t

neighbors::vamana::index::data

Dataset [size, dim]

1 [[nodiscard]] inline auto data() const noexcept -> const cuvs::neighbors::dataset<int64_t>&;

Returns

const cuvs::neighbors::dataset<int64_t>&

neighbors::vamana::index::quantized_data

Quantized dataset [size, codes_rowlen]

1 [[nodiscard]] inline auto quantized_data() const noexcept
2 -> raft::device_matrix_view<const uint8_t, int64_t, raft::row_major>;

Returns

raft::device_matrix_view<const uint8_t, int64_t, raft::row_major>

neighbors::vamana::index::graph

vamana graph [size, graph-degree]

1 [[nodiscard]] inline auto graph() const noexcept
2 -> raft::device_matrix_view<const IdxT, int64_t, raft::row_major>;

Returns

raft::device_matrix_view<const IdxT, int64_t, raft::row_major>

neighbors::vamana::index::medoid

Return the id of the vector selected as the medoid.

1 [[nodiscard]] inline auto medoid() const noexcept -> IdxT;

Returns

IdxT

neighbors::vamana::index::index

1 index(const index&)                    = delete;

Parameters

Name	Direction	Type	Description
`arg1`		`const index&`

Returns

void

Additional overload: neighbors::vamana::index::index

Construct an empty index.

1 index(raft::resources const& res,
2 cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Expanded)
3 : cuvs::neighbors::index(),

Parameters

Name	Direction	Type	Description
`res`		`raft::resources const&`
`metric`		`cuvs::distance::DistanceType`	Default: `cuvs::distance::DistanceType::L2Expanded`.

Returns

void

Additional overload: neighbors::vamana::index::index

Construct an index from dataset and vamana graph

1 template <typename data_accessor, typename graph_accessor>
2 index(raft::resources const& res,
3 cuvs::distance::DistanceType metric,
4 raft::mdspan<const T, raft::matrix_extent<int64_t>, raft::row_major, data_accessor> dataset,
5 raft::mdspan<const IdxT, raft::matrix_extent<int64_t>, raft::row_major, graph_accessor>
6 vamana_graph,
7 IdxT medoid_id)
8 : cuvs::neighbors::index(),

Parameters

Name	Direction	Type	Description
`res`		`raft::resources const&`
`metric`		`cuvs::distance::DistanceType`
`dataset`		`raft::mdspan<const T, raft::matrix_extent<int64_t>, raft::row_major, data_accessor>`
`vamana_graph`		`raft::mdspan<const IdxT, raft::matrix_extent<int64_t>, raft::row_major, graph_accessor>`
`medoid_id`		`IdxT`

Returns

void

neighbors::vamana::index::update_graph

Replace the graph with a new graph.

1 void update_graph(raft::resources const& res,
2 raft::device_matrix_view<const IdxT, int64_t, raft::row_major> 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.

Parameters

Name	Direction	Type	Description
`res`		`raft::resources const&`
`new_graph`		`raft::device_matrix_view<const IdxT, int64_t, raft::row_major>`

Returns

void

Additional overload: neighbors::vamana::index::update_graph

Replace the graph with a new graph.

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

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

Parameters

Name	Direction	Type	Description
`res`		`raft::resources const&`
`new_graph`		`raft::host_matrix_view<const IdxT, int64_t, raft::row_major>`

Returns

void

neighbors::vamana::index::update_quantized_dataset

Replace the current quantized dataset with a new quantized dataset.

1 void update_quantized_dataset(
2 raft::resources const& res,
3 raft::device_matrix_view<const uint8_t, int64_t, raft::row_major> new_quantized_dataset);

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

Parameters

Name	Direction	Type	Description
`res`	in	`raft::resources const&`
`new_quantized_dataset`	in	`raft::device_matrix_view<const uint8_t, int64_t, raft::row_major>`	the new quantized dataset for the index

Returns

void

Vamana index build functions

neighbors::vamana::build

Build the index from the dataset for efficient DiskANN search.

1 auto build(raft::resources const& res,
2 const cuvs::neighbors::vamana::index_params& params,
3 raft::device_matrix_view<const float, int64_t, raft::row_major> dataset)
4 -> cuvs::neighbors::vamana::index<float, uint32_t>;

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:

Usage example:

Parameters

Name	Direction	Type	Description
`res`	in	`raft::resources const&`
`params`	in	`const cuvs::neighbors::vamana::index_params&`	parameters for building the index
`dataset`	in	`raft::device_matrix_view<const float, int64_t, raft::row_major>`	a matrix view (device) to a row-major matrix [n_rows, dim]

Returns

cuvs::neighbors::vamana::index<float, uint32_t>

Additional overload: neighbors::vamana::build

Build the index from the dataset for efficient DiskANN search.

1 auto build(raft::resources const& res,
2 const cuvs::neighbors::vamana::index_params& params,
3 raft::host_matrix_view<const float, int64_t, raft::row_major> dataset)
4 -> cuvs::neighbors::vamana::index<float, uint32_t>;

The following distance metrics are supported:

Usage example:

Parameters

Name	Direction	Type	Description
`res`	in	`raft::resources const&`
`params`	in	`const cuvs::neighbors::vamana::index_params&`	parameters for building the index
`dataset`	in	`raft::host_matrix_view<const float, int64_t, raft::row_major>`	a matrix view (host) to a row-major matrix [n_rows, dim]

Returns

cuvs::neighbors::vamana::index<float, uint32_t>

Additional overload: neighbors::vamana::build

Build the index from the dataset for efficient DiskANN search.

1 auto build(raft::resources const& res,
2 const cuvs::neighbors::vamana::index_params& params,
3 raft::device_matrix_view<const int8_t, int64_t, raft::row_major> dataset)
4 -> cuvs::neighbors::vamana::index<int8_t, uint32_t>;

The following distance metrics are supported:

Usage example:

Parameters

Name	Direction	Type	Description
`res`	in	`raft::resources const&`
`params`	in	`const cuvs::neighbors::vamana::index_params&`	parameters for building the index
`dataset`	in	`raft::device_matrix_view<const int8_t, int64_t, raft::row_major>`	a matrix view (device) to a row-major matrix [n_rows, dim]

Returns

cuvs::neighbors::vamana::index<int8_t, uint32_t>

Additional overload: neighbors::vamana::build

Build the index from the dataset for efficient DiskANN search.

1 auto build(raft::resources const& res,
2 const cuvs::neighbors::vamana::index_params& params,
3 raft::host_matrix_view<const int8_t, int64_t, raft::row_major> dataset)
4 -> cuvs::neighbors::vamana::index<int8_t, uint32_t>;

The following distance metrics are supported:

Usage example:

Parameters

Name	Direction	Type	Description
`res`	in	`raft::resources const&`
`params`	in	`const cuvs::neighbors::vamana::index_params&`	parameters for building the index
`dataset`	in	`raft::host_matrix_view<const int8_t, int64_t, raft::row_major>`	a matrix view (host) to a row-major matrix [n_rows, dim]

Returns

cuvs::neighbors::vamana::index<int8_t, uint32_t>

Additional overload: neighbors::vamana::build

Build the index from the dataset for efficient DiskANN search.

1 auto build(raft::resources const& res,
2 const cuvs::neighbors::vamana::index_params& params,
3 raft::device_matrix_view<const uint8_t, int64_t, raft::row_major> dataset)
4 -> cuvs::neighbors::vamana::index<uint8_t, uint32_t>;

The following distance metrics are supported:

Usage example:

Parameters

Name	Direction	Type	Description
`res`	in	`raft::resources const&`
`params`	in	`const cuvs::neighbors::vamana::index_params&`	parameters for building the index
`dataset`	in	`raft::device_matrix_view<const uint8_t, int64_t, raft::row_major>`	a matrix view (device) to a row-major matrix [n_rows, dim]

Returns

cuvs::neighbors::vamana::index<uint8_t, uint32_t>

Additional overload: neighbors::vamana::build

Build the index from the dataset for efficient DiskANN search.

1 auto build(raft::resources const& res,
2 const cuvs::neighbors::vamana::index_params& params,
3 raft::host_matrix_view<const uint8_t, int64_t, raft::row_major> dataset)
4 -> cuvs::neighbors::vamana::index<uint8_t, uint32_t>;

The following distance metrics are supported:

Usage example:

Parameters

Name	Direction	Type	Description
`res`	in	`raft::resources const&`
`params`	in	`const cuvs::neighbors::vamana::index_params&`	parameters for building the index
`dataset`	in	`raft::host_matrix_view<const uint8_t, int64_t, raft::row_major>`	a matrix view (host) to a row-major matrix [n_rows, dim]

Returns

cuvs::neighbors::vamana::index<uint8_t, uint32_t>

Vamana serialize functions

neighbors::vamana::serialize

Save the index to file.

1 void serialize(raft::resources const& handle,
2 const std::string& file_prefix,
3 const cuvs::neighbors::vamana::index<float, uint32_t>& index,
4 bool include_dataset = true,
5 bool sector_aligned  = false);

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

Parameters

Name	Direction	Type	Description
`handle`	in	`raft::resources const&`	the raft handle
`file_prefix`	in	`const std::string&`	prefix of path and name of index files
`index`	in	`const cuvs::neighbors::vamana::index<float, uint32_t>&`	Vamana index
`include_dataset`	in	`bool`	whether or not to serialize the dataset Default: `true`.
`sector_aligned`	in	`bool`	whether output file should be aligned to disk sectors of 4096 bytes Default: `false`.

Returns

void

Additional overload: neighbors::vamana::serialize

Save the index to file.

1 void serialize(raft::resources const& handle,
2 const std::string& file_prefix,
3 const cuvs::neighbors::vamana::index<int8_t, uint32_t>& index,
4 bool include_dataset = true,
5 bool sector_aligned  = false);

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

Parameters

Name	Direction	Type	Description
`handle`	in	`raft::resources const&`	the raft handle
`file_prefix`	in	`const std::string&`	prefix of path and name of index files
`index`	in	`const cuvs::neighbors::vamana::index<int8_t, uint32_t>&`	Vamana index
`include_dataset`	in	`bool`	whether or not to serialize the dataset Default: `true`.
`sector_aligned`	in	`bool`	whether output file should be aligned to disk sectors of 4096 bytes Default: `false`.

Returns

void

Additional overload: neighbors::vamana::serialize

Save the index to file.

1 void serialize(raft::resources const& handle,
2 const std::string& file_prefix,
3 const cuvs::neighbors::vamana::index<uint8_t, uint32_t>& index,
4 bool include_dataset = true,
5 bool sector_aligned  = false);

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

Parameters

Name	Direction	Type	Description
`handle`	in	`raft::resources const&`	the raft handle
`file_prefix`	in	`const std::string&`	prefix of path and name of index files
`index`	in	`const cuvs::neighbors::vamana::index<uint8_t, uint32_t>&`	Vamana index
`include_dataset`	in	`bool`	whether or not to serialize the dataset Default: `true`.
`sector_aligned`	in	`bool`	whether output file should be aligned to disk sectors of 4096 bytes Default: `false`.

Returns

void

Vamana codebook functions

neighbors::vamana::deserialize_codebooks

Construct codebook parameters from input codebook files

1 auto deserialize_codebooks(const std::string& codebook_prefix, const int dim)
2 -> codebook_params<float>;

Expects pq pivots file at “ $\{codebook_prefix\}_pq_pivots.bin" and rotation matrix file at "$ {codebook_prefix}_pq_pivots.bin_rotation_matrix.bin”.

Parameters

Name	Direction	Type	Description
`codebook_prefix`	in	`const std::string&`	path prefix to pq pivots and rotation matrix files
`dim`	in	`const int`	dimension of vectors in dataset

Returns

codebook_params<float>