Skip to navigation

Common

View as Markdown

Source header: cuvs/neighbors/common.hpp

Approximate Nearest Neighbors Types

neighbors::index

The base for approximate KNN index structures.

struct index;

neighbors::index_params

The base for KNN index parameters.

struct index_params {
cuvs::distance::DistanceType metric;
float metric_arg;
};

Fields

NameTypeDescription
metriccuvs::distance::DistanceTypeDistance type.
metric_argfloatThe argument used by some distance metrics.

neighbors::MergeStrategy

Strategy for merging indices.

This enum is declared separately to avoid namespace pollution when including common.hpp. It provides a generic merge strategy that can be used across different index types.

enum class MergeStrategy {
MERGE_STRATEGY_PHYSICAL = 0,
MERGE_STRATEGY_LOGICAL = 1
};

Values

NameValue
MERGE_STRATEGY_PHYSICAL0
MERGE_STRATEGY_LOGICAL1

Types

neighbors::dataset

Tags selecting dataset representation for dataset / dataset_view.

Each container defines nested owning_storage then view_storage (aliases into detail::* storage types shared by device/host). Accessibility (device vs host) is selected by the Accessor template parameter on dataset / dataset_view, not by duplicating containers. Layout kinds: empty, padded, standard, VPQ. dataset / dataset_view only express ownership vs view.

template <typename ContainerType, typename DataT, typename IdxT, typename Accessor>
struct dataset;

math_type

Floating-point type used for VQ/PQ codebooks (rows are still uint8 codes).

using math_type = MathT;

neighbors::dataset_view_kind_of

Primary template returns unknown so traits safely return false for non-dataset-view types.

template <typename V>
struct dataset_view_kind_of {
static constexpr dataset_view_kind value;
};

Fields

NameTypeDescription
valuestatic constexpr dataset_view_kind

neighbors::dataset_view_is_device_accessible

True when the dataset view accessor is device-accessible.

template <typename V>
struct dataset_view_is_device_accessible;

neighbors::with_accessor

Generic accessor retargeting while preserving the dataset tag/layout and value/index types:

dataset<Tag, DataT, IdxT, OldAccessor> -> dataset<Tag, DataT, IdxT, NewAccessor> dataset_view<Tag, DataT, IdxT, OldAccessor> -> dataset_view<Tag, DataT, IdxT, NewAccessor>

template <typename DatasetLikeT, typename NewAccessor>
struct with_accessor;

neighbors::to_device_accessor

Map any host accessor to its device counterpart (same payload policy).

template <typename Accessor>
struct to_device_accessor;

neighbors::device_counterpart

Maps a host dataset view type to its device-resident counterpart.

template <typename HostViewT>
struct device_counterpart;

neighbors::cagra_view_element_type

Element type T for cagra::build(res, params, dataset_view) (deduced, not a template arg).

template <typename V, typename = void>
struct cagra_view_element_type;

neighbors::ivf::list_base

Abstract base class for IVF list data.

This allows polymorphic access to list data regardless of the underlying layout.

TODO: Make this struct internal (tracking issue: https://github.com/NVIDIA/cuvs/issues/1726)

template <typename ValueT, typename IdxT, typename SizeT = uint32_t>
struct list_base;

neighbors::ivf::list

The data for a single IVF list.

template <template <typename, typename...> typename SpecT,
typename SizeT,
typename... SpecExtraArgs>
struct list : public list_base<typename SpecT<SizeT, SpecExtraArgs...>::value_type,
typename SpecT<SizeT, SpecExtraArgs...>::index_type,
SizeT> {
raft::device_mdarray<value_type, list_extents, raft::row_major> data;
raft::device_mdarray<index_type, raft::extent_1d<size_type>, raft::row_major> indices;
std::atomic<size_type> size;
};

Fields

NameTypeDescription
dataraft::device_mdarray<value_type, list_extents, raft::row_major>Possibly encoded data; it’s layout is defined by SpecT.
indicesraft::device_mdarray<index_type, raft::extent_1d<size_type>, raft::row_major>Source indices.
sizestd::atomic<size_type>The actual size of the content.

Filtering for ANN Types

neighbors::filtering::FilterType

Filtering for ANN Types

enum class FilterType : int {
None = 0,
Bitmap = 1,
Bitset = 2,
Bloom = 3,
Roaring = 4,
UDF = 100
};

Values

NameValue
None0
Bitmap1
Bitset2
Bloom3
Roaring4
UDF100

neighbors::filtering::none_sample_filter::operator

constexpr __forceinline__ _RAFT_HOST_DEVICE bool operator()(
// query index
const uint32_t query_ix,
// the current inverted list index
const uint32_t cluster_ix,
// the index of the current sample inside the current inverted list
const uint32_t sample_ix) const;

Returns

constexpr __forceinline__ _RAFT_HOST_DEVICE bool

neighbors::filtering::none_sample_filter::get_filter_type

FilterType get_filter_type() const override;

Returns

FilterType

neighbors::filtering::ivf_to_sample_filter

Filter used to convert the cluster index and sample index of an IVF search into a sample index. This can be used as an intermediate filter.

template <typename index_t, typename filter_t>
struct ivf_to_sample_filter : public base_filter {
const index_t* const* inds_ptrs_;
const filter_t next_filter_;
};

Fields

NameTypeDescription
inds_ptrs_const index_t* const*
next_filter_const filter_t

neighbors::filtering::ivf_to_sample_filter::operator

If the original filter takes three arguments, then don’t modify the arguments.

inline _RAFT_HOST_DEVICE bool operator()(
// query index
const uint32_t query_ix,
// the current inverted list index
const uint32_t cluster_ix,
// the index of the current sample inside the current inverted list
const uint32_t sample_ix) const;

If the original filter takes two arguments, then we are using inds_ptr_ to obtain the sample index.

Returns

inline _RAFT_HOST_DEVICE bool

neighbors::filtering::bitmap_filter

Filter an index with a bitmap

template <typename bitmap_t, typename index_t>
struct bitmap_filter : public base_filter {
const view_t bitmap_view_;
};

Fields

NameTypeDescription
bitmap_view_const view_t

neighbors::filtering::bitmap_filter::operator

inline _RAFT_HOST_DEVICE bool operator()(
// query index
const uint32_t query_ix,
// the index of the current sample
const uint32_t sample_ix) const;

Returns

inline _RAFT_HOST_DEVICE bool

neighbors::filtering::bitmap_filter::get_filter_type

FilterType get_filter_type() const override;

Returns

FilterType

neighbors::filtering::bitset_filter

Filter an index with a bitset

This filter holds a non-owning view of the bitset; it does not allocate or copy the underlying device buffer. The library performs no caching of the bitset across search calls. Allocating and populating the device bitset may be more expensive than a single filtered search, so callers that issue repeated searches against the same filter (e.g. many queries over one index) should build the bitset once and reuse it across those calls rather than rebuild it per search. Reusing the bitset is essential for realizing the full throughput of filtered search.

template <typename bitset_t, typename index_t>
struct bitset_filter : public base_filter {
const view_t bitset_view_;
};

Fields

NameTypeDescription
bitset_view_const view_t

neighbors::filtering::bitset_filter::bitset_filter

_RAFT_HOST_DEVICE bitset_filter(const view_t bitset_for_filtering);

Parameters

NameDirectionTypeDescription
bitset_for_filteringconst view_t

Returns

_RAFT_HOST_DEVICE

neighbors::filtering::bitset_filter::get_filter_type

FilterType get_filter_type() const override;

Returns

FilterType

neighbors::filtering::bloom_filter

Filter CAGRA candidates with a global cuvs::core::bloom_filter over the index.

Build the filter once on the host with bulk add() over the allowed dataset row ids and pass the owning cuvs::core::bloom_filter to this wrapper. CAGRA internals build/cache the device payload, similar to bitset_filter, and the linked JIT-LTO fragment probes the same filter for every query and candidate with probabilistic membership tests.

Bloom filters have no false negatives: if a row was inserted, contains returns true. False positives are possible, so highly selective predicates may still need a bitset or UDF for exact filtering.

This adapter is non-owning. The referenced cuvs::core::bloom_filter must outlive the adapter and any searches that use it, and must not be moved or mutated concurrently with a search.

struct bloom_filter : public base_filter {
void* filter_data;
};

Fields

NameTypeDescription
filter_datavoid*

neighbors::filtering::roaring_bitmap_filter

Reusable per-query mapping to immutable exact Roaring allowlists.

Entry q selects view q. CAGRA retains candidate dataset row r when the selected allowlist contains r. Construction copies only already initialized device-reference pointers and empty flags into the filter payload; encoded bytes are neither copied nor parsed. Search therefore performs no Roaring allocation, initialization, synchronization, or preprocessing.

Owners and views can be reused across filters and queries. This filter owns its mapping tables and device payload, but not the referenced owners, which must outlive the filter and all searches using it. Copies are cheap shared handles required by CAGRA query-offset wrappers.

Roaring filters currently support direct cagra::search only. Dynamic batching can combine requests into a different query-row layout, and tiered search applies one filter to partitions with different row domains; both paths reject this filter type.

struct roaring_bitmap_filter;

neighbors::filtering::roaring_bitmap_filter::roaring_bitmap_filter

Construct an invalid handle. It cannot be passed to CAGRA search.

roaring_bitmap_filter() = default;

Returns

void

Additional overload: neighbors::filtering::roaring_bitmap_filter::roaring_bitmap_filter

Materialize the query-to-allowlist device pointer table.

explicit roaring_bitmap_filter(raft::resources const& res,
std::span<const cuvs::core::roaring_allowlist_view> allowlists);

dataset_rows(). Query count is inferred from the span length.

Parameters

NameDirectionTypeDescription
resraft::resources const&
allowlistsstd::span<const cuvs::core::roaring_allowlist_view>

Returns

explicit

neighbors::filtering::roaring_bitmap_filter::filtering_rate

Conservative maximum rejected fraction among all query allowlists.

[[nodiscard]] float filtering_rate() const noexcept;

CAGRA uses this precomputed value when search_params::filtering_rate is unset. Basing one batch-wide scalar on the sparsest query avoids under-provisioning that query, but a very sparse or empty allowlist can increase the search work performed for every query in the batch. Callers may set search_params::filtering_rate explicitly when another tradeoff is preferable.

Returns

[[nodiscard]] float

neighbors::filtering::roaring_bitmap_filter::size_bytes

Device bytes owned by this mapping, excluding the referenced allowlists.

[[nodiscard]] std::size_t size_bytes() const noexcept;

Returns

[[nodiscard]] std::size_t

neighbors::filtering::roaring_bitmap_filter::set_allowlist

Replace one query’s allowlist pointer outside the search path.

void set_allowlist(raft::resources const& res,
std::size_t query_id,
cuvs::core::roaring_allowlist_view replacement);

The replacement must have the same dataset_rows(). Copies share the underlying mapping, so the replacement is visible through every copy of this filter. The method copies one pointer and one empty flag to the device and synchronizes res before returning. Do not call it concurrently with a search, and keep the replacement owner alive for all subsequent searches.

Parameters

NameDirectionTypeDescription
resraft::resources const&
query_idstd::size_t
replacementcuvs::core::roaring_allowlist_view

Returns

void

neighbors::filtering::roaring_bitmap_filter::device_payload

Internal device payload already prepared for the linked CAGRA predicate.

[[nodiscard]] void* device_payload() const noexcept;

Returns

[[nodiscard]] void*

neighbors::filtering::udf_filter

JIT-LTO user-defined filter predicate.

The source must define a device function named by function_name with signature:

Return true to allow a source vector to appear in the results and false to reject it. UDF dereferences it. CAGRA currently provides source_index_t as uint32_t in the generated JIT fragment.

struct udf_filter : public base_filter {
std::string source;
void* filter_data;
float filtering_rate;
std::string function_name;
};

Fields

NameTypeDescription
sourcestd::stringCUDA C++ source containing the device predicate.
filter_datavoid*Opaque device-accessible pointer passed to the predicate.
filtering_ratefloatEstimated fraction of rows rejected by the predicate, or negative if unknown.
function_namestd::stringDevice function name to call from the generated CAGRA sample filter.

ANN MG index build parameters

neighbors::distribution_mode

enum distribution_mode {
REPLICATED,
SHARDED
};

Values

NameValue
REPLICATED“
SHARDED“

neighbors::mg_index_params

template <typename Upstream>
struct mg_index_params : public Upstream {
cuvs::neighbors::distribution_mode mode;
};

Fields

NameTypeDescription
modecuvs::neighbors::distribution_modeDistribution mode

ANN MG search parameters

neighbors::replicated_search_mode

enum replicated_search_mode {
LOAD_BALANCER,
ROUND_ROBIN
};

Values

NameValue
LOAD_BALANCER“
ROUND_ROBIN“

neighbors::sharded_merge_mode

enum sharded_merge_mode {
MERGE_ON_ROOT_RANK,
TREE_MERGE
};

Values

NameValue
MERGE_ON_ROOT_RANK“
TREE_MERGE“

neighbors::mg_search_params

template <typename Upstream>
struct mg_search_params : public Upstream {
cuvs::neighbors::replicated_search_mode search_mode;
cuvs::neighbors::sharded_merge_mode merge_mode;
int64_t n_rows_per_batch;
};

Fields

NameTypeDescription
search_modecuvs::neighbors::replicated_search_modeReplicated search mode
merge_modecuvs::neighbors::sharded_merge_modeSharded merge mode
n_rows_per_batchint64_tNumber of rows per batch