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?

Adding a reference to nearest neighbors in the readme would improve the discoverability of the crate.

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.

Is it possible to derive Clone for kdtree?

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?

This should be radius.

A few lines of documentation for each function would really help.

Kind of this

let a = ([0f64, 0f64], 0);
let b = ([1f64, 0f64], 1);
let mut kdtree = KdTree::new(2);

kdtree.add(a.0, a.1).unwrap();
kdtree.add(b.0, b.1).unwrap();

kdtree.remove(&[0f64, 0f64], &1).unwrap();

or

let a = ([0f64, 0f64], 0);
let b = ([0f64, 0f64], 1);
let mut kdtree = KdTree::new(2);

kdtree.add(a.0, a.1).unwrap();
kdtree.add(b.0, b.1).unwrap();

kdtree.remove(&[0f64, 0f64], &1).unwrap();

will cause the program to stuck. There may be some issue with the implementation of the remove fn.

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 ?

This issue was automatically generated. Feel free to close without ceremony if
you do not agree with re-licensing or if it is not possible for other reasons.
Respond to @cmr with any questions or concerns, or pop over to
#rust-offtopic on IRC to discuss.

You're receiving this because someone (perhaps the project maintainer)
published a crates.io package with the license as "MIT" xor "Apache-2.0" and
the repository field pointing here.

TL;DR the Rust ecosystem is largely Apache-2.0. Being available under that
license is good for interoperation. The MIT license as an add-on can be nice
for GPLv2 projects to use your code.

Why?

The MIT license requires reproducing countless copies of the same copyright
header with different names in the copyright field, for every MIT library in
use. The Apache license does not have this drawback. However, this is not the
primary motivation for me creating these issues. The Apache license also has
protections from patent trolls and an explicit contribution licensing clause.
However, the Apache license is incompatible with GPLv2. This is why Rust is
dual-licensed as MIT/Apache (the "primary" license being Apache, MIT only for
GPLv2 compat), and doing so would be wise for this project. This also makes
this crate suitable for inclusion and unrestricted sharing in the Rust
standard distribution and other projects using dual MIT/Apache, such as my
personal ulterior motive, the Robigalia project.

Some ask, "Does this really apply to binary redistributions? Does MIT really
require reproducing the whole thing?" I'm not a lawyer, and I can't give legal
advice, but some Google Android apps include open source attributions using
this interpretation. Others also agree with
it.
But, again, the copyright notice redistribution is not the primary motivation
for the dual-licensing. It's stronger protections to licensees and better
interoperation with the wider Rust ecosystem.

How?

To do this, get explicit approval from each contributor of copyrightable work
(as not all contributions qualify for copyright, due to not being a "creative
work", e.g. a typo fix) and then add the following to your README:

## License

Licensed under either of

 * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
 * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)

at your option.

### Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted
for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any
additional terms or conditions.

and in your license headers, if you have them, use the following boilerplate
(based on that used in Rust):

// Copyright 2016 kdtree-rs Developers
//
// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
// http://opensource.org/licenses/MIT>, at your option. This file may not be
// copied, modified, or distributed except according to those terms.

It's commonly asked whether license headers are required. I'm not comfortable
making an official recommendation either way, but the Apache license
recommends it in their appendix on how to use the license.

Be sure to add the relevant LICENSE-{MIT,APACHE} files. You can copy these
from the Rust repo for a plain-text
version.

And don't forget to update the license metadata in your Cargo.toml to:

license = "MIT OR Apache-2.0"

I'll be going through projects which agree to be relicensed and have approval
by the necessary contributors and doing this changes, so feel free to leave
the heavy lifting to me!

Contributor checkoff

To agree to relicensing, comment with :

I license past and future contributions under the dual MIT/Apache-2.0 license, allowing licensees to chose either at their option.

Or, if you're a contributor, you can check the box in this repo next to your
name. My scripts will pick this exact phrase up and check your checkbox, but
I'll come through and manually review this issue later as well.

• @mrhooray

I get the following output:

   Compiling petgraph v0.5.1
error[E0432]: unresolved import `std::arch::x86_64`
 --> /Users/ababo/.cargo/registry/src/github.com-1ecc6299db9ec823/kiddo-0.1.6/src/distance.rs:6:16
  |
6 | use std::arch::x86_64::*;
  |                ^^^^^^ could not find `x86_64` in `arch`

error[E0412]: cannot find type `__m128` in this scope
  --> /Users/ababo/.cargo/registry/src/github.com-1ecc6299db9ec823/kiddo-0.1.6/src/distance.rs:10:11
   |
10 |     simd: __m128,
   |           ^^^^^^ not found in this scope

error[E0425]: cannot find function `dot_sse` in this scope
  --> /Users/ababo/.cargo/registry/src/github.com-1ecc6299db9ec823/kiddo-0.1.6/src/distance.rs:78:14
   |
78 |     unsafe { dot_sse(ap, bp) }
   |              ^^^^^^^ not found in this scope

error[E0425]: cannot find function `dot_sse` in this scope
  --> /Users/ababo/.cargo/registry/src/github.com-1ecc6299db9ec823/kiddo-0.1.6/src/distance.rs:82:14
   |
82 |     unsafe { dot_sse(a.as_ptr(), b.as_ptr()) }
   |              ^^^^^^^ not found in this scope

error[E0425]: cannot find function `dot_sse_aligned` in this scope
  --> /Users/ababo/.cargo/registry/src/github.com-1ecc6299db9ec823/kiddo-0.1.6/src/distance.rs:88:14
   |
88 |     unsafe { dot_sse_aligned(ap, bp) }
   |              ^^^^^^^^^^^^^^^ not found in this scope

error[E0740]: unions may not contain fields that need dropping
  --> /Users/ababo/.cargo/registry/src/github.com-1ecc6299db9ec823/kiddo-0.1.6/src/distance.rs:10:5
   |
10 |     simd: __m128,
   |     ^^^^^^^^^^^^
   |
note: `std::mem::ManuallyDrop` can be used to wrap the type
  --> /Users/ababo/.cargo/registry/src/github.com-1ecc6299db9ec823/kiddo-0.1.6/src/distance.rs:10:5
   |
10 |     simd: __m128,
   |     ^^^^^^^^^^^^

   Compiling crossbeam-channel v0.5.1

I think there should always be a fallback for the case of generic CPU architecture.

    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 #20 (comment)

I see you use swap remove here https://github.com/mrhooray/kdtree-rs/blob/master/src/kdtree.rs#L268, I was wondering why is that, if you iterate over a vector using swap remove, you'll pop the first element and make the last element first, and so forth, this will end up on removing the first element and then exhausting the array in reverse order.

What's the algorithmic difference with like iterating over the points in forward order, or in reverse order using pop for instance?

Is there any possibility to use generics to support f32 (or so on)?

It may be possible to convert f32 to f64, but it requires so many type conversions.

Hi,

will it be possible to remove points as well in the future? Afaik no (kd|...)tree library for Rust does allow it. Would be nice to have.

Thanks

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.

I was wondering is there a way to return split_value as a vector?

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().

Is it possible to expose information related to the tree during construction? (e.g number of leafs generated thus far.)