Neighbors Common | NVIDIA cuVS

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

Name	Type	Description
`metric`	`cuvs::distance::DistanceType`	Distance type.
`metric_arg`	`float`	The 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

Name	Value
`MERGE_STRATEGY_PHYSICAL`	`0`
`MERGE_STRATEGY_LOGICAL`	`1`

Types

neighbors::dataset

Two-dimensional dataset; maybe owning, maybe compressed, maybe strided.

template <typename IdxT>
struct dataset;

neighbors::device_vpq_dataset

VPQ compressed dataset.

The dataset is compressed using two level quantization

Vector Quantization
Product Quantization of residuals

template <typename MathT, typename IdxT>
struct device_vpq_dataset : public dataset<IdxT> {
  raft::device_matrix<math_type, uint32_t, raft::row_major> vq_code_book;
  raft::device_matrix<math_type, uint32_t, raft::row_major> pq_code_book;
  raft::device_matrix<uint8_t, index_type, raft::row_major> data;
};

Fields

Name	Type	Description
`vq_code_book`	`raft::device_matrix<math_type, uint32_t, raft::row_major>`	Vector Quantization codebook - “coarse cluster centers”.
`pq_code_book`	`raft::device_matrix<math_type, uint32_t, raft::row_major>`	Product Quantization codebook - “fine cluster centers”.
`data`	`raft::device_matrix<uint8_t, index_type, raft::row_major>`	Compressed dataset.

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

Name	Type	Description
`data`	`raft::device_mdarray<value_type, list_extents, raft::row_major>`	Possibly encoded data; it’s layout is defined by `SpecT`.
`indices`	`raft::device_mdarray<index_type, raft::extent_1d<size_type>, raft::row_major>`	Source indices.
`size`	`std::atomic<size_type>`	The actual size of the content.

Filtering for ANN Types

neighbors::filtering::FilterType

Filtering for ANN Types

enum class FilterType {
  None,
  Bitmap,
  Bitset
};

Values

Name	Value
`None`	“
`Bitmap`	“
`Bitset`	“

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

Name	Type	Description
`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

Name	Type	Description
`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

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

Fields

Name	Type	Description
`bitset_view_`	`const view_t`

neighbors::filtering::bitset_filter::bitset_filter

_RAFT_HOST_DEVICE bitset_filter(const view_t bitset_for_filtering);

Parameters

Name	Direction	Type	Description
`bitset_for_filtering`		`const view_t`

Returns

_RAFT_HOST_DEVICE

neighbors::filtering::bitset_filter::get_filter_type

FilterType get_filter_type() const override;

Returns

FilterType

ANN MG index build parameters

neighbors::distribution_mode

enum distribution_mode;

neighbors::mg_index_params

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

Fields

Name	Type	Description
`mode`	`cuvs::neighbors::distribution_mode`	Distribution mode

ANN MG search parameters

neighbors::replicated_search_mode

enum replicated_search_mode {
  LOAD_BALANCER,
  ROUND_ROBIN
};

Values

Name	Value
`LOAD_BALANCER`	“
`ROUND_ROBIN`	“

neighbors::sharded_merge_mode

enum sharded_merge_mode {
  MERGE_ON_ROOT_RANK,
  TREE_MERGE
};

Values

Name	Value
`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

Name	Type	Description
`search_mode`	`cuvs::neighbors::replicated_search_mode`	Replicated search mode
`merge_mode`	`cuvs::neighbors::sharded_merge_mode`	Sharded merge mode
`n_rows_per_batch`	`int64_t`	Number of rows per batch