knn.h

/*!
 *  Copyright (c) 2021 by Contributors
 * \file graph/transform/knn.h
 * \brief k-nearest-neighbor (KNN) implementation
 */

#ifndef DGL_GRAPH_TRANSFORM_KNN_H_
#define DGL_GRAPH_TRANSFORM_KNN_H_

#include <dgl/array.h>
#include <string>

namespace dgl {
namespace transform {

/*!
 * \brief For each point in each segment in \a query_points, find \a k nearest
 *  points in the same segment in \a data_points. \a data_offsets and \a query_offsets
 *  determine the start index of each segment in \a data_points and \a query_points.
 *
 * \param data_points dataset points.
 * \param data_offsets offsets of point index in \a data_points.
 * \param query_points query points.
 * \param query_offsets offsets of point index in \a query_points.
 * \param k the number of nearest points.
 * \param result output array. A 2D tensor indicating the index
 *  relation between \a query_points and \a data_points.
 * \param algorithm algorithm used to compute the k-nearest neighbors.
 */
template <DGLDeviceType XPU, typename FloatType, typename IdType>
void KNN(const NDArray& data_points, const IdArray& data_offsets,
         const NDArray& query_points, const IdArray& query_offsets,
         const int k, IdArray result, const std::string& algorithm);

/*!
 * \brief For each input point, find \a k approximate nearest points in the same
 *  segment using NN-descent algorithm.
 *
 * \param points input points.
 * \param offsets offsets of point index.
 * \param result output array. A 2D tensor indicating the index relation between points.
 * \param k the number of nearest points.
 * \param num_iters The maximum number of NN-descent iterations to perform.
 * \param num_candidates The maximum number of candidates to be considered during one iteration.
 * \param delta A value controls the early abort.
 */
template <DGLDeviceType XPU, typename FloatType, typename IdType>
void NNDescent(const NDArray& points, const IdArray& offsets,
               IdArray result, const int k, const int num_iters,
               const int num_candidates, const double delta);

}  // namespace transform
}  // namespace dgl


#endif  // DGL_GRAPH_TRANSFORM_KNN_H_