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 withdeserialize
-
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 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 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 firstindex->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