From limited testing this seems to work well. Had to add a partialeq constraint to filter data and points. I don't rebalance the tree, just remove the items, not sure if that would be helpful. Fixes #30

I think that everything is ready to allow users to pass the maximum radius when searching for nearest points. Unfortunately rust does not support optional arguments yet, so something like this could be trivial to implement:

pub fn nearest_radius<F>(
        &self,
        point: &[A],
        num: usize,
        radius: A,
        distance: &F,
    )

The current function

pub fn nearest<F>(
        &self,
        point: &[A],
        num: usize,
        distance: &F,
    )

calls to

self.nearest_step(
                point,
                num,
                A::infinity(),
                distance,
                &mut pending,
                &mut evaluated,
            );

which already has the maximum radius as A::infinity().

This is big! I stumbled on this experimenting with a refactoring.

New bench:

running 2 tests
test bench_add_to_kdtree_with_1k_3d_points       ... bench:         156 ns/iter (+/- 44)
test bench_nearest_from_kdtree_with_1k_3d_points ... bench:       3,603 ns/iter (+/- 3,217)

Old bench:

running 2 tests
test bench_add_to_kdtree_with_1k_3d_points       ... bench:         139 ns/iter (+/- 61)
test bench_nearest_from_kdtree_with_1k_3d_points ... bench:       6,677 ns/iter (+/- 6,613)

Maby evan "0.3.1"?

    I get the same error when I use this crate.

And I figured out the reason.

The avg will be equal to a, under the limit of f64's accuracy. As a result, the fn split() can't split this node successfully. In this situation, fn add_to_bucket() and fn split() will call each other infinitely.

    let a = 0.47945351705599926f64;
    let b = 0.47945351705599931f64;
    
    let avg = (a + b) / 2.0;

    println!("{:.20E}", a);
    println!("{:.20E}", b);
    println!("{:.20E}", avg);

And the resolution is extremely easy. Just modify fn belongs_in_left() like this

fn belongs_in_left(&self, point: &[A]) -> bool {
        // before
        // point[self.split_dimension.unwrap()] < self.split_value.unwrap()
        // after
        point[self.split_dimension.unwrap()] <= self.split_value.unwrap()
}

Originally posted by @TYPEmber in https://github.com/mrhooray/kdtree-rs/issues/20#issuecomment-1344093398

For unknown reason the kdtree-rs library takes about 1000x more time than Python's sklearn.neighbors.KDTree for very large datasets (like several millions of points). Can you confirm we have O(log(n)) for the nearest point query?

• Run cargo fmt
• Run cargo +nightly clippy and fixed warnings
• Run cargo fix --edition
• Fixed docs in src/distance.rs, and other cosmetic changes
• Replaced assert!(x == y) with assert_eq!(x, y)

I haven't minimised yet, but in some circumstances, add_to_bucket results in a stack overflow. Without looking too closely, I think there's an infinite (or exponential) loop where add_to_bucket calls split, which in turn calls add_to_bucket, etc.

Edit: If I create a KdTree with sufficient capacity to begin with, the stack overflow doesn't occur, so the problem is with it dynamically resizing.

I have a project encoding location data into a kdtree. Because all the fields are private it is a hassle to add getters for all of them. Supporting serde here would be a lot more convenient.

Hi,

I'm interested in space aware datastructures and just learning rust, I was wondering what does the U: AsRef<f64> means in the kdtree.rs file. Does it mean that there should be a generic parameter U that defaults to a slice of f64 items that are default implemented and functions like:

    pub fn nearest<F>(&self,
                      point: &[f64],
                      num: usize,
                      distance: &F)
                      -> Result<Vec<(f64, &T)>, ErrorKind>

can be implemented to use a type U rather than f64?

It seems like a lot has changed since the last release (the documentation doesn't even match anymore). So it would be cool if you could release a new version. I'll have to use the git version directly till then I guess.

Hello ,
First of all, thank you for your work. I'm planning to use your kdtree crate in rust. In my checking, the latest crate version is 0.6.0 , which is almost 3 years ago. But it seems that git hub has more commits after it. Do you have a plan to upgrade the version of crate ?