NN-Descent#

NN-descent 方法是一种 ANN 算法，它通过随机采样点来计算距离并使用邻居的邻居距离来减少距离计算，从而直接近似 k-最近邻图。

#include <cuvs/neighbors/nn_descent.hpp>

namespace cuvs::neighbors::nn_descent

索引构建参数#

struct index_params : public cuvs::neighbors::index_params#
#include <nn_descent.hpp>

用于构建 nn-descent 索引的参数。

graph_degree: 对于维度为 (N, D) 的输入数据集，确定最终的 all-neighbors knn 图的维度，其维度为 (N, graph_degree) intermediate_graph_degree: 在内部，nn-descent 在选择最终的 graph_degree 邻居之前，构建维度为 (N, intermediate_graph_degree) 的 all-neighbors knn 图。建议 intermediate_graph_degree >= 1.5 * graph_degree max_iterations: nn-descent 精炼图的迭代次数。更多迭代会产生更高质量的图，但会牺牲性能 termination_threshold: nn-descent 将终止其迭代的 delta 值

索引#

template<typename IdxT>
struct index : public cuvs::neighbors::index#
#include <nn_descent.hpp>

nn-descent 构建一个 nn-descent 索引 该索引包含存储在主机内存中的输入数据集的 all-neighbors 图，其维度为 (n_rows, n_cols)

参考：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

模板参数:

IdxT – 用于构建 knn-graph 的 dtype

索引构建#

size_t graph_degree = 64
size_t intermediate_graph_degree = 128
size_t max_iterations = 20
float termination_threshold = 0.0001#
bool return_distances = true#
size_t n_clusters = 1#
index_params(
size_t graph_degree = 64,
cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Expanded
)#

构造特定 kNN 图度数的 NN descent 参数。

参数:

  • graph_degree – 输出图的度数

  • metric – 要使用的距离度量

inline index(
raft::resources const &res,
int64_t n_rows,
int64_t n_cols,
bool return_distances = false,
cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Expanded
)#

构造新的索引对象。

此构造函数创建一个 nn-descent 索引，它是一个存储在主机内存中的 knn-graph。knn-graph 的类型是密集 `raft::host_matrix`，维度为 (n_rows, n_cols)。

参数:

  • res – raft::resources 是一个管理资源的对象的引用

  • n_rows – knn-graph 中的行数

  • n_cols – knn-graph 中的列数

  • return_distances – 是否返回距离

  • metric – 要使用的距离度量

inline index(
raft::resources const &res,
raft::host_matrix_view<IdxT, int64_t, raft::row_major> graph_view,
std::optional<raft::device_matrix_view<float, int64_t, row_major>> distances_view = std::nullopt,
cuvs::distance::DistanceType metric = cuvs::distance::DistanceType::L2Expanded
)#

构造新的索引对象。

此构造函数使用用户分配的主机内存 knn-graph 创建 nn-descent 索引。knn-graph 的类型是密集 `raft::host_matrix`，维度为 (n_rows, n_cols)。

参数:

  • res – raft::resources 是一个管理资源的对象的引用

  • graph_view – 用于存储 knn-graph 的 `raft::host_matrix_view`

  • distances_view – 可选的 `raft::device_matrix_view` 用于存储距离

  • metric – 要使用的距离度量

inline cuvs::distance::DistanceType metric() const noexcept

用于聚类的距离度量。

inline IdxT size() const noexcept

索引的总长度（向量数量）。

inline uint32_t graph_degree() const noexcept

图的度数

inline raft::host_matrix_view<IdxT, int64_t, raft::row_major> graph(
) noexcept#

邻域图 [大小, 图度数]

inline std::optional<device_matrix_view<float, int64_t, row_major>> distances(
) noexcept#

邻域图距离 [大小, 图度数]

index(const index&) = delete
index(index&&) = default
index &=delete operator= (const index &)
index &=default operator= (index &&)
~index() = default
cuvs::neighbors::nn_descent::index<uint32_t> build(
raft::resources const &res,
index_params const &params,
raft::device_matrix_view<const float, int64_t, raft::row_major> dataset,
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph = std::nullopt
)#

使用设备内存中的数据集构建 nn-descent 索引。

支持以下距离度量

  • L2

使用示例

using namespace cuvs::neighbors;
// use default index parameters
nn_descent::index_params index_params;
// create and fill the index from a [N, D] raft::device_matrix_view dataset
auto index = nn_descent::build(res, index_params, dataset);
// index.graph() provides a raft::host_matrix_view of an
// all-neighbors knn graph of dimensions [N, k] of the input
// dataset

参数:

  • res – [in] raft::resources 是一个管理资源的对象的引用

  • params – [in] nn_descent::index_params 的一个实例，它是运行 nn-descent 算法的参数

  • dataset – [in] raft::device_matrix_view 输入数据集，预计位于设备内存中

  • graph – [in] 可选的 `raft::host_matrix_view` 用于拥有输出图

返回:

index 索引，包含主机内存中的 all-neighbors knn 图

cuvs::neighbors::nn_descent::index<uint32_t> build(
raft::resources const &res,
index_params const &params,
raft::host_matrix_view<const float, int64_t, raft::row_major> dataset,
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph = std::nullopt
)#

使用主机内存中的数据集构建 nn-descent 索引。

支持以下距离度量

  • L2

使用示例

using namespace cuvs::neighbors;
// use default index parameters
nn_descent::index_params index_params;
// create and fill the index from a [N, D] raft::host_matrix_view dataset
auto index = nn_descent::build(res, index_params, dataset);
// index.graph() provides a raft::host_matrix_view of an
// all-neighbors knn graph of dimensions [N, k] of the input
// dataset

模板参数:

  • T – 输入数据集的数据类型

  • IdxT – 输出索引的数据类型

参数:

  • res – raft::resources 是一个管理资源的对象的引用

  • params – [in] nn_descent::index_params 的一个实例，它是运行 nn-descent 算法的参数

  • dataset – [in] raft::host_matrix_view 输入数据集，预计位于主机内存中

  • graph – [in] 可选的 `raft::host_matrix_view` 用于拥有输出图

返回:

index 索引，包含主机内存中的 all-neighbors knn 图

cuvs::neighbors::nn_descent::index<uint32_t> build(
raft::resources const &res,
index_params const &params,
raft::device_matrix_view<const half, int64_t, raft::row_major> dataset,
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph = std::nullopt
)#

使用设备内存中的数据集构建 nn-descent 索引。

支持以下距离度量

  • L2

使用示例

using namespace cuvs::neighbors;
// use default index parameters
nn_descent::index_params index_params;
// create and fill the index from a [N, D] raft::device_matrix_view dataset
auto index = nn_descent::build(res, index_params, dataset);
// index.graph() provides a raft::host_matrix_view of an
// all-neighbors knn graph of dimensions [N, k] of the input
// dataset

参数:

  • res – [in] raft::resources 是一个管理资源的对象的引用

  • params – [in] nn_descent::index_params 的一个实例，它是运行 nn-descent 算法的参数

  • dataset – [in] raft::device_matrix_view 输入数据集，预计位于设备内存中

  • graph – [in] 可选的 `raft::host_matrix_view` 用于拥有输出图

返回:

index 索引，包含主机内存中的 all-neighbors knn 图

cuvs::neighbors::nn_descent::index<uint32_t> build(
raft::resources const &res,
index_params const &params,
raft::host_matrix_view<const half, int64_t, raft::row_major> dataset,
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph = std::nullopt
)#

使用主机内存中的数据集构建 nn-descent 索引。

支持以下距离度量

  • L2

使用示例

using namespace cuvs::neighbors;
// use default index parameters
nn_descent::index_params index_params;
// create and fill the index from a [N, D] raft::host_matrix_view dataset
auto index = nn_descent::build(res, index_params, dataset);
// index.graph() provides a raft::host_matrix_view of an
// all-neighbors knn graph of dimensions [N, k] of the input
// dataset

模板参数:

  • T – 输入数据集的数据类型

  • IdxT – 输出索引的数据类型

参数:

  • res – raft::resources 是一个管理资源的对象的引用

  • params – [in] nn_descent::index_params 的一个实例，它是运行 nn-descent 算法的参数

  • dataset – [in] raft::host_matrix_view 输入数据集，预计位于主机内存中

  • graph – [in] 可选的 `raft::host_matrix_view` 用于拥有输出图

返回:

index 索引，包含主机内存中的 all-neighbors knn 图

cuvs::neighbors::nn_descent::index<uint32_t> build(
raft::resources const &res,
index_params const &params,
raft::device_matrix_view<const int8_t, int64_t, raft::row_major> dataset,
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph = std::nullopt
)#

使用设备内存中的数据集构建 nn-descent 索引。

支持以下距离度量

  • L2

使用示例

using namespace cuvs::neighbors;
// use default index parameters
nn_descent::index_params index_params;
// create and fill the index from a [N, D] raft::device_matrix_view dataset
auto index = nn_descent::build(res, index_params, dataset);
// index.graph() provides a raft::host_matrix_view of an
// all-neighbors knn graph of dimensions [N, k] of the input
// dataset

参数:

  • res – [in] raft::resources 是一个管理资源的对象的引用

  • params – [in] nn_descent::index_params 的一个实例，它是运行 nn-descent 算法的参数

  • dataset – [in] raft::device_matrix_view 输入数据集，预计位于设备内存中

  • graph – [in] 可选的 `raft::host_matrix_view` 用于拥有输出图

返回:

index 索引，包含主机内存中的 all-neighbors knn 图

cuvs::neighbors::nn_descent::index<uint32_t> build(
raft::resources const &res,
index_params const &params,
raft::host_matrix_view<const int8_t, int64_t, raft::row_major> dataset,
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph = std::nullopt
)#

使用主机内存中的数据集构建 nn-descent 索引。

支持以下距离度量

  • L2

使用示例

using namespace cuvs::neighbors;
// use default index parameters
nn_descent::index_params index_params;
// create and fill the index from a [N, D] raft::host_matrix_view dataset
auto index = nn_descent::build(res, index_params, dataset);
// index.graph() provides a raft::host_matrix_view of an
// all-neighbors knn graph of dimensions [N, k] of the input
// dataset

模板参数:

  • T – 输入数据集的数据类型

  • IdxT – 输出索引的数据类型

参数:

  • res – raft::resources 是一个管理资源的对象的引用

  • params – [in] nn_descent::index_params 的一个实例，它是运行 nn-descent 算法的参数

  • dataset – [in] raft::host_matrix_view 输入数据集，预计位于主机内存中

  • graph – [in] 可选的 `raft::host_matrix_view` 用于拥有输出图

返回:

index 索引，包含主机内存中的 all-neighbors knn 图

cuvs::neighbors::nn_descent::index<uint32_t> build(
raft::resources const &res,
index_params const &params,
raft::device_matrix_view<const uint8_t, int64_t, raft::row_major> dataset,
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph = std::nullopt
)#

使用设备内存中的数据集构建 nn-descent 索引。

支持以下距离度量

  • L2

使用示例

using namespace cuvs::neighbors;
// use default index parameters
nn_descent::index_params index_params;
// create and fill the index from a [N, D] raft::device_matrix_view dataset
auto index = nn_descent::build(res, index_params, dataset);
// index.graph() provides a raft::host_matrix_view of an
// all-neighbors knn graph of dimensions [N, k] of the input
// dataset

参数:

  • res – [in] raft::resources 是一个管理资源的对象的引用

  • params – [in] nn_descent::index_params 的一个实例，它是运行 nn-descent 算法的参数

  • dataset – [in] raft::device_matrix_view 输入数据集，预计位于设备内存中

  • graph – [in] 可选的 `raft::host_matrix_view` 用于拥有输出图

返回:

index 索引，包含主机内存中的 all-neighbors knn 图

cuvs::neighbors::nn_descent::index<uint32_t> build(
raft::resources const &res,
index_params const &params,
raft::host_matrix_view<const uint8_t, int64_t, raft::row_major> dataset,
std::optional<raft::host_matrix_view<uint32_t, int64_t, raft::row_major>> graph = std::nullopt
)#

使用主机内存中的数据集构建 nn-descent 索引。

支持以下距离度量

  • L2

使用示例

using namespace cuvs::neighbors;
// use default index parameters
nn_descent::index_params index_params;
// create and fill the index from a [N, D] raft::host_matrix_view dataset
auto index = nn_descent::build(res, index_params, dataset);
// index.graph() provides a raft::host_matrix_view of an
// all-neighbors knn graph of dimensions [N, k] of the input
// dataset

模板参数:

  • T – 输入数据集的数据类型

  • IdxT – 输出索引的数据类型

参数:

  • res – raft::resources 是一个管理资源的对象的引用

  • params – [in] nn_descent::index_params 的一个实例，它是运行 nn-descent 算法的参数

  • dataset – [in] raft::host_matrix_view 输入数据集，预计位于主机内存中

  • graph – [in] 可选的 `raft::host_matrix_view` 用于拥有输出图

返回:

index 索引，包含主机内存中的 all-neighbors knn 图

bool has_enough_device_memory(
raft::resources const &res,
raft::matrix_extent<int64_t> dataset,
size_t idx_size = 4
)#

测试是否有足够的 GPU 内存来运行 NN descent 算法。

参数:

  • res –

  • dataset – 数据集的形状

  • idx_size – 索引类型的大小（字节）

返回:

如果可以分配足够的 GPU 内存则为 True

返回:

否则为 False