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>
struct index : public cuvs::neighbors::ann::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

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

Distance metric used for retrieval

T metric_arg() const noexcept

Metric argument

size_t size() const noexcept

Total length of the index (number of vectors).

size_t dim() const noexcept

Dimensionality of the data.

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

Dataset [size, dim]

raft::device_vector_view<const T, int64_t, raft::row_major> norms() const

Dataset norms

bool has_norms() const noexcept

Whether ot not this index has dataset norms

Index build

auto 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) -> cuvs::neighbors::brute_force::index<float>

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

Index search

void search(raft::resources const &handle, const cuvs::neighbors::brute_force::index<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)

Search ANN using the constructed index.

See the ivf_flat::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]