Ball Cover#

2026-09-01

4 min read time

Applies to Linux

Random Ball Cover is an exact nearest neighbors algorithm that can be faster than brute-force for low dimensional data by partitioning the dataset into a set of balls (defined by a landmark point and a radius) and only searching the balls that could contain a query’s true nearest neighbors.

#include <cuvs/neighbors/ball_cover.hpp>

namespace cuvs::neighbors::ball_cover

Random Ball Cover#

void all_knn_query(
raft::resources const &handle,
index<int64_t, float> &index,
raft::device_matrix_view<int64_t, int64_t, raft::row_major> inds,
raft::device_matrix_view<float, int64_t, raft::row_major> dists,
bool perform_post_filtering = true,
float weight = 1.0
)#

Performs a faster exact knn in metric spaces using the triangle inequality with a number of landmark points to reduce the number of distance computations from O(n^2) to O(sqrt(n)). This performs an all neighbors knn, which can reuse memory when the index and query are the same array. This function will build the index and assumes rbc_build_index() has not already been called.

Usage example:

#include <raft/core/resources.hpp>
#include <cuvs/neighbors/ball_cover.hpp>
#include <cuvs/distance/distance.hpp>
using namespace cuvs::neighbors;

raft::resources handle;
...
auto metric = cuvs::distance::DistanceType::L2Expanded;

// Construct a ball cover index
ball_cover::index index(handle, X, metric);

// Perform all neighbors knn query
ball_cover::all_knn_query(handle, index, inds, dists, k);

Parameters:
  • handle – [in] raft handle for resource management

  • index – [in] ball cover index which has not yet been built

  • inds – [out] output knn indices

  • dists – [out] output knn distances

  • perform_post_filtering – [in] if this is false, only the closest k landmarks are considered (which will return approximate results).

  • weight – [in] a weight for overlap between the closest landmark and the radius of other landmarks when pruning distances. Setting this value below 1 can effectively turn off computing distances against many other balls, enabling approximate nearest neighbors. Recall can be adjusted based on how many relevant balls are ignored. Note that many datasets can still have great recall even by only looking in the closest landmark.

void knn_query(
raft::resources const &handle,
const index<int64_t, float> &index,
raft::device_matrix_view<const float, int64_t, raft::row_major> query,
raft::device_matrix_view<int64_t, int64_t, raft::row_major> inds,
raft::device_matrix_view<float, int64_t, raft::row_major> dists,
bool perform_post_filtering = true,
float weight = 1.0
)#

Performs a faster exact knn in metric spaces using the triangle inequality with a number of landmark points to reduce the number of distance computations from O(n^2) to O(sqrt(n)). This function does not build the index and assumes rbc_build_index() has already been called. Use this function when the index and query arrays are different, otherwise use rbc_all_knn_query().

Usage example:

#include <raft/core/resources.hpp>
#include <cuvs/neighbors/ball_cover.hpp>
#include <cuvs/distance/distance.hpp>
using namespace cuvs::neighbors;

raft::resources handle;
...
auto metric = cuvs::distance::DistanceType::L2Expanded;

// Build a ball cover index
ball_cover::index index(handle, X, metric);
ball_cover::build_index(handle, index);

// Perform all neighbors knn query
ball_cover::knn_query(handle, index, inds, dists, k);

Parameters:
  • handle – [in] raft handle for resource management

  • index – [in] ball cover index which has not yet been built

  • query – [in] device matrix containing query data points

  • inds – [out] output knn indices

  • dists – [out] output knn distances

  • perform_post_filtering – [in] if this is false, only the closest k landmarks are considered (which will return approximate results).

  • weight – [in] a weight for overlap between the closest landmark and the radius of other landmarks when pruning distances. Setting this value below 1 can effectively turn off computing distances against many other balls, enabling approximate nearest neighbors. Recall can be adjusted based on how many relevant balls are ignored. Note that many datasets can still have great recall even by only looking in the closest landmark.

void build(
raft::resources const &handle,
index<int64_t, float> &index
)#

Builds and populates a previously unbuilt cuvs::neighbors::ball_cover::index

Usage example:

#include <raft/core/resources.hpp>
#include <cuvs/neighbors/ball_cover.hpp>
#include <cuvs/distance/distance.hpp>
using namespace cuvs::neighbors;

raft::resources handle;
...
auto metric = cuvs::distance::DistanceType::L2Expanded;
ball_cover::index index(handle, X, metric);
ball_cover::build_index(handle, index);

Parameters:
template<typename idx_t, typename value_t>
struct index : public cuvs::neighbors::index#
#include <ball_cover.hpp>

Stores raw index data points, sampled landmarks, the 1-nns of index points to their closest landmarks, and the ball radii of each landmark. This class is intended to be constructed once and reused across subsequent queries.

Template Parameters:
  • int64_t –

  • float –

  • int –

Public Functions

inline explicit index(
raft::resources const &handle_,
raft::device_matrix_view<const float, int64_t, raft::row_major> X_,
cuvs::distance::DistanceType metric_
)#

the sqrt() here makes the sqrt(m)^2 a linear-time lower bound

Total memory footprint of index: (2 * sqrt(m)) + (n * sqrt(m)) + (2 * m)