Ball Cover#
2026-09-01
4 min read time
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:
handle – [in] library resource management handle
index – [inout] an empty (and not previous built) instance of cuvs::neighbors::ball_cover::index
-
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)