petabi/petal-neighbors

Nearest neighbor search algorithms including a ball tree and a vantage point tree.

petal-neighbors's Issues

Accept ndarray as a point in `query*` functions

query* functions such as BallTree::query_nearest takes a slice as a point, assuming coordinates are stored contiguously. However, often those points are stored in an ndarray, and it may have a large stride between elements. It would make this crate more flexible if passing an ndarray as a point is allowed.

Use `kth_distance` in knn query

This will never prune:

petal-neighbors/src/ball_tree.rs

Line 205 in aca8a78

if root_node.distance_lower_bound(point, &self.metric) > radius {

as radius is always A::infinity().

Vantage-point tree

A vantage-point tree would allow nearest neighbor search without requiring multidimensional points.

ball tree not parallelized?

Dear ball tree/kd tree team,

I think ball tree can be efficiently parallelized right according to this paper: https://www.nazneenrajani.com/hpgm.pdf

We can rely on rayon package?

Thanks,

Jianshu

Performance analysis of current implementation

• Setup fair performance comparison routine with Nearest neighbors
• Identify the performance issues currently existed.

Improving the flexibility of distance calculation by using trait instead of function pointer