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 {
3
  int pq_codebook_size;
4
  int pq_dim;
5
  std::vector<T> pq_encoding_table;
6
  std::vector<T> rotation_matrix;
7
};

Fields

neighbors::vamana::index_params

Parameters used to build DiskANN index

1
struct index_params : cuvs::neighbors::index_params {
2
  uint32_t graph_degree;
3
  uint32_t visited_size;
4
  float vamana_iters;
5
  float alpha;
6
  float max_fraction;
7
  float batch_base;
8
  uint32_t queue_size;
9
  uint32_t reverse_batchsize;
10
  std::optional<codebook_params<float>> codebooks;
11
};

Fields

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;

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

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

Parameters

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

Parameters

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

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

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

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:

• L2

Usage example:

Parameters

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

Parameters

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

Parameters

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

Parameters

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

Parameters

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

Parameters

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

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

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

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

Returns

codebook_params<float>