Bruteforce

The bruteforce method is running the KNN algorithm. It performs an extensive search, and in contrast to ANN methods produces an exact result.

#include <cuvs/neighbors/bruteforce.hpp>

namespace cuvs::neighbors::bruteforce

Index

template<typename T, typename DistT = T>
struct index : public cuvs::neighbors::index

#include <brute_force.hpp>

Brute Force index.

The index stores the dataset and norms for the dataset in device memory.

Template Parameters:

T – data element type

Public Functions

index(raft::resources const &handle)

Construct an empty index.

Constructs an empty index. This index will either need to be trained with build or loaded from a saved copy with deserialize

index(

raft::resources const &res,

raft::host_matrix_view<const T, int64_t, raft::row_major> dataset_view,

std::optional<raft::device_vector<DistT, int64_t>> &&norms,

cuvs::distance::DistanceType metric,

DistT metric_arg = 0.0,

)

Construct a brute force index from dataset

Constructs a brute force index from a dataset. This lets us precompute norms for the dataset, providing a speed benefit over doing this at query time. This index will copy the host dataset onto the device, and take ownership of any precaculated norms.

index(

raft::resources const &res,

raft::device_matrix_view<const T, int64_t, raft::row_major> dataset_view,

std::optional<raft::device_vector<DistT, int64_t>> &&norms,

cuvs::distance::DistanceType metric,

DistT metric_arg = 0.0,

)

Construct a brute force index from dataset

Constructs a brute force index from a dataset. This lets us precompute norms for the dataset, providing a speed benefit over doing this at query time. This index will store a non-owning reference to the dataset, but will move any norms supplied.

index(

raft::resources const &res,

raft::device_matrix_view<const T, int64_t, raft::row_major> dataset_view,

std::optional<raft::device_vector_view<const DistT, int64_t>> norms_view,

cuvs::distance::DistanceType metric,

DistT metric_arg = 0.0,

)

Construct a brute force index from dataset

This class stores a non-owning reference to the dataset and norms. Having precomputed norms gives us a performance advantage at query time.

index(

raft::resources const &res,

raft::device_matrix_view<const T, int64_t, raft::col_major> dataset_view,

std::optional<raft::device_vector<DistT, int64_t>> &&norms,

cuvs::distance::DistanceType metric,

DistT metric_arg = 0.0,

)

Construct a brute force index from dataset

Constructs a brute force index from a dataset. This lets us precompute norms for the dataset, providing a speed benefit over doing this at query time. This index will store a non-owning reference to the dataset, but will move any norms supplied.

index(

raft::resources const &res,

raft::device_matrix_view<const T, int64_t, raft::col_major> dataset_view,

std::optional<raft::device_vector_view<const DistT, int64_t>> norms_view,

cuvs::distance::DistanceType metric,

DistT metric_arg = 0.0,

)

Construct a brute force index from dataset

This class stores a non-owning reference to the dataset and norms, with the dataset being supplied on device in a col_major format

void update_dataset(

raft::resources const &res,

raft::device_matrix_view<const T, int64_t, raft::row_major> dataset,

)

Replace the dataset with a new dataset.

void update_dataset(

raft::resources const &res,

raft::host_matrix_view<const T, int64_t, raft::row_major> dataset,

)

Replace the dataset with a new dataset.

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

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

Distance metric used for retrieval

inline DistT metric_arg() const noexcept

Metric argument

inline size_t size() const noexcept

Total length of the index (number of vectors).

inline size_t dim() const noexcept

Dimensionality of the data.

inline raft::device_matrix_view<const T, int64_t, raft::row_major> dataset(

) const noexcept

Dataset [size, dim]

inline raft::device_vector_view<const DistT, int64_t, raft::row_major> norms(

) const

Dataset norms

inline bool has_norms() const noexcept

Whether ot not this index has dataset norms

Index build

cuvs::neighbors::brute_force::index<float, float> build(

raft::resources const &handle,

raft::device_matrix_view<const float, int64_t, raft::row_major> dataset,

cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Unexpanded,

float metric_arg = 0,

)

Build the index from the dataset for efficient search.

Usage example:

using namespace cuvs::neighbors;
// create and fill the index from a [N, D] dataset
auto index = brute_force::build(handle, dataset, metric);

Parameters:

• handle – [in]

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

• metric – [in] cuvs::distance::DistanceType

• metric_arg – [in] metric argument

Returns:

the constructed brute-force index

cuvs::neighbors::brute_force::index<half, float> build(

raft::resources const &handle,

raft::device_matrix_view<const half, int64_t, raft::row_major> dataset,

cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Unexpanded,

float metric_arg = 0,

)

Build the index from the dataset for efficient search.

Usage example:

using namespace cuvs::neighbors;
// create and fill the index from a [N, D] dataset
auto index = brute_force::build(handle, dataset, metric);

Parameters:

• handle – [in]

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

• metric – [in] cuvs::distance::DistanceType

• metric_arg – [in] metric argument

Returns:

the constructed ivf-flat index

cuvs::neighbors::brute_force::index<float, float> build(

raft::resources const &handle,

raft::device_matrix_view<const float, int64_t, raft::col_major> dataset,

cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Unexpanded,

float metric_arg = 0,

)

Build the index from the dataset for efficient search.

Usage example:

using namespace cuvs::neighbors;
// create and fill the index from a [N, D] dataset
auto index = brute_force::build(handle, dataset, metric);

Parameters:

• handle – [in]

• dataset – [in] a device pointer to a col-major matrix [n_rows, dim]

• metric – [in] cuvs::distance::DistanceType

• metric_arg – [in] metric argument

Returns:

the constructed bruteforce index

cuvs::neighbors::brute_force::index<half, float> build(

raft::resources const &handle,

raft::device_matrix_view<const half, int64_t, raft::col_major> dataset,

cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Unexpanded,

float metric_arg = 0,

)

Build the index from the dataset for efficient search.

Usage example:

using namespace cuvs::neighbors;
// create and fill the index from a [N, D] dataset
auto index = brute_force::build(handle, dataset, metric);

Parameters:

• handle – [in]

• dataset – [in] a device pointer to a col-major matrix [n_rows, dim]

• metric – [in] cuvs::distance::DistanceType

• metric_arg – [in] metric argument

Returns:

the constructed bruteforce index

Index search

void search(

raft::resources const &handle,

const cuvs::neighbors::brute_force::index<float, float> &index,

raft::device_matrix_view<const float, int64_t, raft::row_major> queries,

raft::device_matrix_view<int64_t, int64_t, raft::row_major> neighbors,

raft::device_matrix_view<float, int64_t, raft::row_major> distances,

const cuvs::neighbors::filtering::base_filter &sample_filter = cuvs::neighbors::filtering::none_sample_filter{},

)

Search ANN using the constructed index.

See the brute_force::build documentation for a usage example.

Note, this function requires a temporary buffer to store intermediate results between cuda kernel calls, which may lead to undesirable allocations and slowdown. To alleviate the problem, you can pass a pool memory resource or a large enough pre-allocated memory resource to reduce or eliminate entirely allocations happening within search:

...
// Use the same allocator across multiple searches to reduce the number of
// cuda memory allocations
brute_force::search(handle, index, queries1, out_inds1, out_dists1);
brute_force::search(handle, index, queries2, out_inds2, out_dists2);
brute_force::search(handle, index, queries3, out_inds3, out_dists3);
...

Parameters:

• handle – [in]

• index – [in] brute-force constructed index

• queries – [in] a device pointer to a row-major matrix [n_queries, index->dim()]

• neighbors – [out] a device pointer to the indices of the neighbors in the source dataset [n_queries, k]

• distances – [out] a device pointer to the distances to the selected neighbors [n_queries, k]

• sample_filter – [in] An optional device bitmap filter function with a row-major layout and the shape of [n_queries, index->size()], which means the filter will use the first index->size() bits to indicate whether queries[0] should compute the distance with dataset.

void search(

raft::resources const &handle,

const cuvs::neighbors::brute_force::index<half, float> &index,

raft::device_matrix_view<const half, int64_t, raft::row_major> queries,

raft::device_matrix_view<int64_t, int64_t, raft::row_major> neighbors,

raft::device_matrix_view<float, int64_t, raft::row_major> distances,

const cuvs::neighbors::filtering::base_filter &sample_filter = cuvs::neighbors::filtering::none_sample_filter{},

)

Search ANN using the constructed index.

See the brute_force::build documentation for a usage example.

Note, this function requires a temporary buffer to store intermediate results between cuda kernel calls, which may lead to undesirable allocations and slowdown. To alleviate the problem, you can pass a pool memory resource or a large enough pre-allocated memory resource to reduce or eliminate entirely allocations happening within search:

...
// Use the same allocator across multiple searches to reduce the number of
// cuda memory allocations
brute_force::search(handle, index, queries1, out_inds1, out_dists1);
brute_force::search(handle, index, queries2, out_inds2, out_dists2);
brute_force::search(handle, index, queries3, out_inds3, out_dists3);
...

Parameters:

• handle – [in]

• index – [in] ivf-flat constructed index

• queries – [in] a device pointer to a row-major matrix [n_queries, index->dim()]

• neighbors – [out] a device pointer to the indices of the neighbors in the source dataset [n_queries, k]

• distances – [out] a device pointer to the distances to the selected neighbors [n_queries, k]

• sample_filter – [in] a optional device bitmap filter function that greenlights samples for a given

void search(

raft::resources const &handle,

const cuvs::neighbors::brute_force::index<float, float> &index,

raft::device_matrix_view<const float, int64_t, raft::col_major> queries,

raft::device_matrix_view<int64_t, int64_t, raft::row_major> neighbors,

raft::device_matrix_view<float, int64_t, raft::row_major> distances,

const cuvs::neighbors::filtering::base_filter &sample_filter = cuvs::neighbors::filtering::none_sample_filter{},

)

Search ANN using the constructed index.

See the brute_force::build documentation for a usage example.

Parameters:

• handle – [in]

• index – [in] bruteforce constructed index

• queries – [in] a device pointer to a col-major matrix [n_queries, index->dim()]

• neighbors – [out] a device pointer to the indices of the neighbors in the source dataset [n_queries, k]

• distances – [out] a device pointer to the distances to the selected neighbors [n_queries, k]

• sample_filter – [in] an optional device bitmap filter function that greenlights samples for a given query

void search(

raft::resources const &handle,

const cuvs::neighbors::brute_force::index<half, float> &index,

raft::device_matrix_view<const half, int64_t, raft::col_major> queries,

raft::device_matrix_view<int64_t, int64_t, raft::row_major> neighbors,

raft::device_matrix_view<float, int64_t, raft::row_major> distances,

const cuvs::neighbors::filtering::base_filter &sample_filter = cuvs::neighbors::filtering::none_sample_filter{},

)

Search ANN using the constructed index.

See the brute_force::build documentation for a usage example.

Parameters:

• handle – [in]

• index – [in] bruteforce constructed index

• queries – [in] a device pointer to a col-major matrix [n_queries, index->dim()]

• neighbors – [out] a device pointer to the indices of the neighbors in the source dataset [n_queries, k]

• distances – [out] a device pointer to the distances to the selected neighbors [n_queries, k]

• sample_filter – [in] an optional device bitmap filter function that greenlights samples for a given query

Index serialize

void serialize(

raft::resources const &handle,

const std::string &filename,

const cuvs::neighbors::brute_force::index<half, float> &index,

bool include_dataset = true,

)

Save the index to file. The serialization format can be subject to changes, therefore loading an index saved with a previous version of cuvs is not guaranteed to work.

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

raft::resources handle;

// create a string with a filepath
std::string filename("/path/to/index");
// create an index with `auto index = brute_force::build(...);`
cuvs::neighbors::brute_force::serialize(handle, filename, index);

Template Parameters:

T – data element type

Parameters:

• handle – [in] the raft handle

• filename – [in] the file name for saving the index

• index – [in] brute force index

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

void serialize(

raft::resources const &handle,

const std::string &filename,

const cuvs::neighbors::brute_force::index<float, float> &index,

bool include_dataset = true,

)

Save the index to file. The serialization format can be subject to changes, therefore loading an index saved with a previous version of cuvs is not guaranteed to work.

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

raft::resources handle;

// create a string with a filepath
std::string filename("/path/to/index");
// create an index with `auto index = brute_force::build(...);`
cuvs::neighbors::brute_force::serialize(handle, filename, index);

Template Parameters:

T – data element type

Parameters:

• handle – [in] the raft handle

• filename – [in] the file name for saving the index

• index – [in] brute force index

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

void serialize(

raft::resources const &handle,

std::ostream &os,

const cuvs::neighbors::brute_force::index<half, float> &index,

bool include_dataset = true,

)

Write the index to an output stream The serialization format can be subject to changes, therefore loading an index saved with a previous version of cuvs is not guaranteed to work.

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

raft::resources handle;

// create an output stream
std::ostream os(std::cout.rdbuf());
// create an index with `auto index = cuvs::neighbors::brute_force::build(...);`
cuvs::neighbors::brute_force::serialize(handle, os, index);

Parameters:

• handle – [in] the raft handle

• os – [in] output stream

• index – [in] brute force index

• include_dataset – [in] Whether or not to write out the dataset to the file.

void serialize(

raft::resources const &handle,

std::ostream &os,

const cuvs::neighbors::brute_force::index<float, float> &index,

bool include_dataset = true,

)

Write the index to an output stream The serialization format can be subject to changes, therefore loading an index saved with a previous version of cuvs is not guaranteed to work.

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

raft::resources handle;

// create an output stream
std::ostream os(std::cout.rdbuf());
// create an index with `auto index = cuvs::neighbors::brute_force::build(...);`
cuvs::neighbors::brute_force::serialize(handle, os, index);

Parameters:

• handle – [in] the raft handle

• os – [in] output stream

• index – [in] brute force index

• include_dataset – [in] Whether or not to write out the dataset to the file.

void deserialize(

raft::resources const &handle,

const std::string &filename,

cuvs::neighbors::brute_force::index<half, float> *index,

)

Load index from file. The serialization format can be subject to changes, therefore loading an index saved with a previous version of cuvs is not guaranteed to work.

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

raft::resources handle;

// create a string with a filepath
std::string filename("/path/to/index");
using T    = half; // data element type
brute_force::index<T, float> index(handle);
cuvs::neighbors::brute_force::deserialize(handle, filename, index);

Parameters:

• handle – [in] the raft handle

• filename – [in] the name of the file that stores the index

• index – [out] brute force index

void deserialize(

raft::resources const &handle,

const std::string &filename,

cuvs::neighbors::brute_force::index<float, float> *index,

)

Load index from file. The serialization format can be subject to changes, therefore loading an index saved with a previous version of cuvs is not guaranteed to work.

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

raft::resources handle;

// create a string with a filepath
std::string filename("/path/to/index");
using T    = float; // data element type
brute_force::index<T, float> index(handle);
cuvs::neighbors::brute_force::deserialize(handle, filename, index);

Parameters:

• handle – [in] the raft handle

• filename – [in] the name of the file that stores the index

• index – [out] brute force index

void deserialize(

raft::resources const &handle,

std::istream &is,

cuvs::neighbors::brute_force::index<half, float> *index,

)

Load index from input stream The serialization format can be subject to changes, therefore loading an index saved with a previous version of cuvs is not guaranteed to work.

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

raft::resources handle;

// create an input stream
std::istream is(std::cin.rdbuf());
using T    = half; // data element type
brute_force::index<T, float> index(handle);
cuvs::neighbors::brute_force::deserialize(handle, is, index);

Parameters:

• handle – [in] the raft handle

• is – [in] input stream

• index – [out] brute force index

void deserialize(

raft::resources const &handle,

std::istream &is,

cuvs::neighbors::brute_force::index<float, float> *index,

)

Load index from input stream The serialization format can be subject to changes, therefore loading an index saved with a previous version of cuvs is not guaranteed to work.

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

raft::resources handle;

// create an input stream
std::istream is(std::cin.rdbuf());
using T    = float; // data element type
brute_force::index<T, float> index(handle);
cuvs::neighbors::brute_force::deserialize(handle, is, index);

Parameters:

• handle – [in] the raft handle

• is – [in] input stream

• index – [out] brute force index