search

mortacious / cupy-knn

A fast nearest neighbor index cuda implementation for 3-D points using a left balanced BVH-tree.
MIT License
29 stars 5 forks source link

possible to use with custom metric #4

Closed PolarBean closed 5 months ago

PolarBean commented 5 months ago

Hi, I have been looking into methods for efficient nan_euclidean KNN. Would it be possible for me to implement a nan_euclidean metric using your library? Thank you in advance

mortacious commented 5 months ago

Hi, i don't think this can be implemented in any spatial search structure. At least it will not be easy ;).

While NaN values in the query points can be supported by a regular KdTree by just ignoring the splits along the dimension with undefined values, it is not possible for the BVH used in this library, as there are no splits along dimensions but between arbitrary AABBs. So NaN values would require to brute force through at least a large part of the search space anyway.

NaN values in the input points are even more problematic because, as the NaN dimensions are supposed to be ignored in the distance calculations, there is no way to insert them into a single leaf.

PolarBean commented 5 months ago

Thank you for your answer, it is very informative.