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_