NN Descent

Source header: cuvs/neighbors/nn_descent.hpp

The nn-descent algorithm parameters.

neighbors::nn_descent::DIST_COMP_DTYPE

Dtype to use for distance computation

1
enum class DIST_COMP_DTYPE {
2
  AUTO = 0,
3
  FP32 = 1,
4
  FP16 = 2
5
};

Values

neighbors::nn_descent::index_params

Parameters used to build an nn-descent index

1
struct index_params : cuvs::neighbors::index_params {
2
  size_t graph_degree;
3
  size_t intermediate_graph_degree;
4
  size_t max_iterations;
5
  float termination_threshold;
6
  bool return_distances;
7
  DIST_COMP_DTYPE dist_comp_dtype;
8
};

Fields

neighbors::nn_descent::index_params::index_params

Construct NN descent parameters for a specific kNN graph degree

1
index_params(size_t graph_degree                 = 64,
2
cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Expanded);

Parameters

Returns

void

nn-descent index

neighbors::nn_descent::index

nn-descent Build an nn-descent index The index contains an all-neighbors graph of the input dataset stored in host memory of dimensions (n_rows, n_cols)

Reference: Hui Wang, Wan-Lei Zhao, Xiangxiang Zeng, and Jianye Yang. 2021. Fast k-NN Graph Construction by GPU based NN-Descent. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management (CIKM ‘21). Association for Computing Machinery, New York, NY, USA, 1929–1938. https://doi.org/10.1145/3459637.3482344

1
template <typename IdxT>
2
struct index;

neighbors::nn_descent::index::index

Construct a new index object

1
index(raft::resources const& res,
2
int64_t n_rows,
3
int64_t n_cols,
4
bool return_distances               = false,
5
cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Expanded);

This constructor creates an nn-descent index which is a knn-graph in host memory. The type of the knn-graph is a dense raft::host_matrix and dimensions are (n_rows, n_cols).

Parameters

Returns

void

Additional overload: neighbors::nn_descent::index::index

Construct a new index object

1
index(raft::resources const& res,
2
raft::host_matrix_view<IdxT, int64_t, raft::row_major> graph_view,
3
std::optional<raft::device_matrix_view<float, int64_t, row_major>> distances_view =
4
std::nullopt,
5
cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Expanded);

This constructor creates an nn-descent index using a user allocated host memory knn-graph. The type of the knn-graph is a dense raft::host_matrix and dimensions are (n_rows, n_cols).

Parameters

Returns

void

neighbors::nn_descent::index::metric

Distance metric used for clustering.

1
[[nodiscard]] constexpr inline auto metric() const noexcept -> cuvs::distance::DistanceType;

Returns

cuvs::distance::DistanceType

neighbors::nn_descent::index::size

Total length of the index (number of vectors).

1
[[nodiscard]] constexpr inline auto size() const noexcept -> IdxT;

Returns

IdxT

neighbors::nn_descent::index::graph_degree

Graph degree

1
[[nodiscard]] constexpr inline auto graph_degree() const noexcept -> uint32_t;

Returns

uint32_t

neighbors::nn_descent::index::graph

neighborhood graph [size, graph-degree]

1
[[nodiscard]] inline auto graph() noexcept
2
-> raft::host_matrix_view<IdxT, int64_t, raft::row_major>;

Returns

raft::host_matrix_view<IdxT, int64_t, raft::row_major>

neighbors::nn_descent::index::distances

neighborhood graph distances [size, graph-degree]

1
[[nodiscard]] inline auto distances() noexcept
2
-> std::optional<device_matrix_view<float, int64_t, row_major>>;

Returns

std::optional<device_matrix_view<float, int64_t, row_major>>

nn-descent index build

neighbors::nn_descent::build

Build nn-descent Index with dataset in device memory

1
auto build(raft::resources const& res,
2
index_params const& params,
3
raft::device_matrix_view<const float, int64_t, raft::row_major> dataset,
4
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph =
5
std::nullopt) -> cuvs::neighbors::nn_descent::index<uint32_t>;

The following distance metrics are supported:

• L2Expanded
• L2SqrtExpanded
• CosineExpanded
• InnerProduct
• L1

Usage example:

Parameters

Returns

cuvs::neighbors::nn_descent::index<uint32_t>

Additional overload: neighbors::nn_descent::build

Build nn-descent Index with dataset in host memory

1
auto build(raft::resources const& res,
2
index_params const& params,
3
raft::host_matrix_view<const float, int64_t, raft::row_major> dataset,
4
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph =
5
std::nullopt) -> cuvs::neighbors::nn_descent::index<uint32_t>;

The following distance metrics are supported:

• L2Expanded
• L2SqrtExpanded
• CosineExpanded
• InnerProduct
• L1

Usage example:

Template Parameters

Parameters

Returns

cuvs::neighbors::nn_descent::index<uint32_t>

Additional overload: neighbors::nn_descent::build

Build nn-descent Index with dataset in device memory

1
auto build(raft::resources const& res,
2
index_params const& params,
3
raft::device_matrix_view<const half, int64_t, raft::row_major> dataset,
4
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph =
5
std::nullopt) -> cuvs::neighbors::nn_descent::index<uint32_t>;

The following distance metrics are supported:

• L2Expanded
• L2SqrtExpanded
• CosineExpanded
• InnerProduct
• L1

Usage example:

Parameters

Returns

cuvs::neighbors::nn_descent::index<uint32_t>

Additional overload: neighbors::nn_descent::build

Build nn-descent Index with dataset in host memory

1
auto build(raft::resources const& res,
2
index_params const& params,
3
raft::host_matrix_view<const half, int64_t, raft::row_major> dataset,
4
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph =
5
std::nullopt) -> cuvs::neighbors::nn_descent::index<uint32_t>;

The following distance metrics are supported:

• L2Expanded
• L2SqrtExpanded
• CosineExpanded
• InnerProduct
• L1

Usage example:

Template Parameters

Parameters

Returns

cuvs::neighbors::nn_descent::index<uint32_t>

Additional overload: neighbors::nn_descent::build

Build nn-descent Index with dataset in device memory

1
auto build(raft::resources const& res,
2
index_params const& params,
3
raft::device_matrix_view<const int8_t, int64_t, raft::row_major> dataset,
4
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph =
5
std::nullopt) -> cuvs::neighbors::nn_descent::index<uint32_t>;

The following distance metrics are supported:

• L2Expanded
• L2SqrtExpanded
• CosineExpanded
• InnerProduct
• L1
• BitwiseHamming

Usage example:

Parameters

Returns

cuvs::neighbors::nn_descent::index<uint32_t>

Additional overload: neighbors::nn_descent::build

Build nn-descent Index with dataset in host memory

1
auto build(raft::resources const& res,
2
index_params const& params,
3
raft::host_matrix_view<const int8_t, int64_t, raft::row_major> dataset,
4
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph =
5
std::nullopt) -> cuvs::neighbors::nn_descent::index<uint32_t>;

The following distance metrics are supported:

• L2Expanded
• L2SqrtExpanded
• CosineExpanded
• InnerProduct
• L1
• BitwiseHamming

Usage example:

Template Parameters

Parameters

Returns

cuvs::neighbors::nn_descent::index<uint32_t>

Additional overload: neighbors::nn_descent::build

Build nn-descent Index with dataset in device memory

1
auto build(raft::resources const& res,
2
index_params const& params,
3
raft::device_matrix_view<const uint8_t, int64_t, raft::row_major> dataset,
4
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph =
5
std::nullopt) -> cuvs::neighbors::nn_descent::index<uint32_t>;

The following distance metrics are supported:

• L2Expanded
• L2SqrtExpanded
• CosineExpanded
• InnerProduct
• L1
• BitwiseHamming

Usage example:

Parameters

Returns

cuvs::neighbors::nn_descent::index<uint32_t>

Additional overload: neighbors::nn_descent::build

Build nn-descent Index with dataset in host memory

1
auto build(raft::resources const& res,
2
index_params const& params,
3
raft::host_matrix_view<const uint8_t, int64_t, raft::row_major> dataset,
4
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph =
5
std::nullopt) -> cuvs::neighbors::nn_descent::index<uint32_t>;

The following distance metrics are supported:

• L2Expanded
• L2SqrtExpanded
• CosineExpanded
• InnerProduct
• L1
• BitwiseHamming

Usage example:

Template Parameters

Parameters

Returns

cuvs::neighbors::nn_descent::index<uint32_t>