NN-Descent#

The NN-descent method is an ANN algorithm that directly approximates a k-nearest neighbors graph by randomly sampling points to compute distances and using neighbors of neighbors distances to reduce distance computations.

#include <cuvs/neighbors/nn_descent.hpp>

namespace cuvs::neighbors::nn_descent

Index build parameters#

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

Parameters used to build an nn-descent index.

graph_degree: For an input dataset of dimensions (N, D), determines the final dimensions of the all-neighbors knn graph which turns out to be of dimensions (N, graph_degree) intermediate_graph_degree: Internally, nn-descent builds an all-neighbors knn graph of dimensions (N, intermediate_graph_degree) before selecting the final graph_degree neighbors. It’s recommended that intermediate_graph_degree >= 1.5 * graph_degree max_iterations: The number of iterations that nn-descent will refine the graph for. More iterations produce a better quality graph at cost of performance termination_threshold: The delta at which nn-descent will terminate its iterations

Public Functions

inline index_params(size_t graph_degree = 64)#

Construct NN descent parameters for a specific kNN graph degree.

Parameters:

graph_degree – output graph degree

Index#

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

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

Template Parameters:

IdxT – dtype to be used for constructing knn-graph

Public Functions

inline index(raft::resources const &res, int64_t n_rows, int64_t n_cols)#

Construct a new index object.

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:

  • res – raft::resources is an object mangaging resources

  • n_rows – number of rows in knn-graph

  • n_cols – number of cols in knn-graph

inline index(raft::resources const &res, raft::host_matrix_view<IdxT, int64_t, raft::row_major> graph_view)#

Construct a new index object.

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:

  • res – raft::resources is an object mangaging resources

  • graph_view – raft::host_matrix_view<IdxT, int64_t, raft::row_major> for storing knn-graph

inline constexpr auto metric() const noexcept -> cuvs::distance::DistanceType#

Distance metric used for clustering.

inline constexpr auto graph_degree() const noexcept -> uint32_t#

Graph degree

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

neighborhood graph [size, graph-degree]

Index build#

auto build(raft::resources const &res, index_params const &params, raft::device_matrix_view<const float, int64_t, raft::row_major> dataset) -> cuvs::neighbors::nn_descent::index<uint32_t>#

Build nn-descent Index with dataset in device memory.

The following distance metrics are supported:

  • L2

Usage example: 

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

Parameters:

  • res – [in] raft::resources is an object mangaging resources

  • params – [in] an instance of nn_descent::index_params that are parameters to run the nn-descent algorithm

  • dataset – [in] raft::device_matrix_view input dataset expected to be located in device memory

Returns:

index<IdxT> index containing all-neighbors knn graph in host memory

auto build(raft::resources const &res, index_params const &params, raft::host_matrix_view<const float, int64_t, raft::row_major> dataset) -> cuvs::neighbors::nn_descent::index<uint32_t>#

Build nn-descent Index with dataset in host memory.

The following distance metrics are supported:

  • L2

Usage example: 

using namespace cuvs::neighbors::experimental;
// 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 = cagra::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

Template Parameters:

  • T – data-type of the input dataset

  • IdxT – data-type for the output index

Parameters:

  • res – raft::resources is an object mangaging resources

  • params – [in] an instance of nn_descent::index_params that are parameters to run the nn-descent algorithm

  • dataset – [in] raft::host_matrix_view input dataset expected to be located in host memory

Returns:

index<IdxT> index containing all-neighbors knn graph in host memory

auto build(raft::resources const &res, index_params const &params, raft::device_matrix_view<const half, int64_t, raft::row_major> dataset) -> cuvs::neighbors::nn_descent::index<uint32_t>#

Build nn-descent Index with dataset in device memory.

The following distance metrics are supported:

  • L2

Usage example: 

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

Parameters:

  • res – [in] raft::resources is an object mangaging resources

  • params – [in] an instance of nn_descent::index_params that are parameters to run the nn-descent algorithm

  • dataset – [in] raft::device_matrix_view input dataset expected to be located in device memory

Returns:

index<IdxT> index containing all-neighbors knn graph in host memory

auto build(raft::resources const &res, index_params const &params, raft::host_matrix_view<const half, int64_t, raft::row_major> dataset) -> cuvs::neighbors::nn_descent::index<uint32_t>#

Build nn-descent Index with dataset in host memory.

The following distance metrics are supported:

  • L2

Usage example: 

using namespace cuvs::neighbors::experimental;
// 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 = cagra::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

Template Parameters:

  • T – data-type of the input dataset

  • IdxT – data-type for the output index

Parameters:

  • res – raft::resources is an object mangaging resources

  • params – [in] an instance of nn_descent::index_params that are parameters to run the nn-descent algorithm

  • dataset – [in] raft::host_matrix_view input dataset expected to be located in host memory

Returns:

index<IdxT> index containing all-neighbors knn graph in host memory

auto build(raft::resources const &res, index_params const &params, raft::device_matrix_view<const int8_t, int64_t, raft::row_major> dataset) -> cuvs::neighbors::nn_descent::index<uint32_t>#

Build nn-descent Index with dataset in device memory.

The following distance metrics are supported:

  • L2

Usage example: 

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

Parameters:

  • res – [in] raft::resources is an object mangaging resources

  • params – [in] an instance of nn_descent::index_params that are parameters to run the nn-descent algorithm

  • dataset – [in] raft::device_matrix_view input dataset expected to be located in device memory

Returns:

index<IdxT> index containing all-neighbors knn graph in host memory

auto build(raft::resources const &res, index_params const &params, raft::host_matrix_view<const int8_t, int64_t, raft::row_major> dataset) -> cuvs::neighbors::nn_descent::index<uint32_t>#

Build nn-descent Index with dataset in host memory.

The following distance metrics are supported:

  • L2

Usage example: 

using namespace cuvs::neighbors::experimental;
// 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 = cagra::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

Template Parameters:

  • T – data-type of the input dataset

  • IdxT – data-type for the output index

Parameters:

  • res – raft::resources is an object mangaging resources

  • params – [in] an instance of nn_descent::index_params that are parameters to run the nn-descent algorithm

  • dataset – [in] raft::host_matrix_view input dataset expected to be located in host memory

Returns:

index<IdxT> index containing all-neighbors knn graph in host memory

auto build(raft::resources const &res, index_params const &params, raft::device_matrix_view<const uint8_t, int64_t, raft::row_major> dataset) -> cuvs::neighbors::nn_descent::index<uint32_t>#

Build nn-descent Index with dataset in device memory.

The following distance metrics are supported:

  • L2

Usage example: 

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

Parameters:

  • res – [in] raft::resources is an object mangaging resources

  • params – [in] an instance of nn_descent::index_params that are parameters to run the nn-descent algorithm

  • dataset – [in] raft::device_matrix_view input dataset expected to be located in device memory

Returns:

index<IdxT> index containing all-neighbors knn graph in host memory

On this page
Show Source