kiddo: Too many items with the same position on one axis
Hello, Scott.
I am using kiddo version=“2.1.1”, while running I get the error:
panicked at ‘Too many items with the same position on one axis. Bucket size must be increased to at least 1 more than the number of items with the same position on one axis.’: /home/user/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-2.1.1/src/float/construction.rs:223
I create KdTree like this
use kiddo::KdTree;
let patterns: KdTree<f32, 3> = KdTree::with_capacity(15000);
Before there was a panic, about 2500-3000 points of this kind were added:
[0.375, 0.02111614, 0.6641945]
[0.4, 0.03517097, 0.7697125]
[0.8333333, 0.29152542, 0.79504514]
[0.39285713, 0.31456685, 0.68769246]
[0.4027778, 0.7054616, 0.17576419]
[0.4, 0.61720204, 0.12553063]
[0.7916667, 0.768097, 0.0121426955]
[0.6458333, 0.84298575, 0.010071943]
[0.35416666, 0.84498125, 0.009049486]
[0.3611111, 0.0, 0.032477904]
[0.75, 0.0, 0.0]
[0.6, 0.018008512, 0.15822956]
[0.20833333, 0.020134605, 0.19604518]
[0.6111111, 0.02478464, 0.21736293]
[0.22222222, 0.028708035, 0.21946773]
[0.6354167, 0.028441446, 0.26566488]
[0.32142857, 0.033044748, 0.24640274]
[0.6770833, 0.05056776, 0.2594764]
[0.35, 0.032584045, 0.23101737]
[0.37121212, 0.034161422, 0.10082746]
[0.70238096, 0.03304547, 0.10467288]
[0.34375, 0.01344555, 0.8041778]
[0.8333333, 0.004752005, 0.0]
[0.375, 0.28213167, 0.60720414]
[0.3888889, 0.0, 0.21019818]
[0.4, 0.0, 0.0]
[0.875, 0.13517289, 0.0]
[0.39583334, 0.14556533, 0.15978695]
[0.8055556, 0.12474227, 0.17170732]
[0.3690476, 0.080061756, 0.52134496]
[0.3690476, 0.117475726, 0.6248968]
...
What capacity should I choose if I expect to add no more than 15000 points? How to calculation it correctly? Why can’t you dynamically expand to the right size?
It’s a bit discouraging, it’s not at all obvious behavior. At first I use KdTree::new() but very quickly got the a similar error, switching to creation via with_capacity also does not completely solve the problem.
In any case, thanks for your library, I use it in my home project to predict the trade price.
Sincerely, Valery
About this issue
- Original URL
- State: closed
- Created 3 years ago
- Reactions: 1
- Comments: 20 (8 by maintainers)
Commits related to this issue
- Replace kiddo by kdtree kdtree is slower than kiddo by kiddo is unusable because of https://github.com/sdd/kiddo/issues/78 — committed to tucanos/tucanos by jeromerobert 3 years ago
- Replace kiddo by kdtree kdtree is slower than kiddo by kiddo is unusable because of https://github.com/sdd/kiddo/issues/78 — committed to tucanos/tucanos by jeromerobert 3 years ago
I would like to chime in with my experience. I really like this library and I appreciate the work that has gone into it. But this issue is unfortunately a dealbreaker: the fact that, given the wrong set of data the program can outright panic, makes it unsuitable for use in any public library or in production.
In my case, which is computer graphics photon mapping, having thousands of photons on a flat plane (with a coordinate value in common) is very typical, which unfortunately completely rules out this library. It’s a shame, because the performance and ergonomics are otherwise best in class.
Maybe another KD-tree type that heap-allocates instead of stack-allocates could solve this use case (or only heap allocates in case of bucket overflow, with something like smallvec). Or a method of splitting the bucket at an arbitrary point, and recording that this split is indeed arbitrary and both buckets need to be checked on access. Or manual assignment of an extra value to equal coordinates, to assign an order to data points with otherwise equal values.
I understand that these all involve a trade-off of either memory or performance, but in my view, squeezing 5% more performance for a tree that may panic when looked at the wrong way isn’t a worthwhile compromise.
This issue should be resolved in https://github.com/sdd/kiddo/pull/186 as part of the rewrite of the
ImmutableKdTree, which was just released as Kiddo v5.0.0 🎉https://crates.io/crates/kiddo/5.0.0
I know this issue was raised a while ago, and you have probably moved on, but if you do get chance to try v5 I’d love to hear any feedback. I’m closing this issue.
Currently, the splitting dimension is based on the depth of each stem node:
https://github.com/sdd/kiddo/blob/c21827d124c085585973912c73cee16e32c52b2f/src/float/construction.rs#L49
Unfortunately, as discussed above, this approach does not work for many datasets.
I suggest to change the implementation so that the split dimension is incremented by one in a loop until the data can be split. This would slightly increase the size of each stem node as it would have to store the index of the splitting dimension. IMHO the overall performance impact should be minimal.
As an intermediate solution to other tree types with different performance tradeoffs, just adding a fallible
try_addfunction would be more than enough for my use-cases.I’m already working on another two alternate types of KdTree that will be available within the library that are optimised for certain scenarios. I could keep the existing highest-performance tree and add another type more suited for your use-case.
At the same time I intend to introduce a KdTree trait that each of these variants implement, to make it easier for anyone that wants to experiment by switching between trees that have differing underlying implementations.
Hi Matt,
I’ve got an idea for how this could be addressed. Essentially it would involve having two sets of leaf nodes. The first type would be the fixed-length ones that we have now, that provide better performance (due to their size being fixed at compile time so that a list of them doesn’t require an extra indirection to a Vec). The second type would be dynamically sized buckets that would be slightly slower to access due to their contents being a Vec rather than an Array.
The stem nodes would use the most significant bit of the leaf index to indicate the leaf index type. This would be quick to check, and the size of the stem nodes would not need to be bigger in memory, keeping more of them in the CPU cache to help with performance. This would mean that the max quantity of standard leaf nodes is halved, but since the type of this index is configurable to be a
u16,u32oru64, that’s not necessarily a problem. Withu16’s and a bucket size of 32, that gives us a capacity of 2^15 * 2^5 = 2^20 (~1M) items. Switching tou32with bucket size 32 gives us room for 2^31 * 2^5 = 2^36 (nearly 700B) items. I think that’s more than enough for anyone 😆This would mean that the library would work for any scenario, with performance gradually degrading, the further the dataset is from an ideally suited distribution.
Hi Valery,
Sorry to hear you’re having problems. The issue that you’re experiencing looks like it is happening because your dataset has lots of points that have values of
0.0.When you use Kiddo via the
kiddo::KdTreeimport, you will get a k-d tree with the default bucket size of 32.kiddo::KdTreeis a type alias, defined in lib.rs like this:You can create a k-d tree with a larger bucket size, which should help. Something like this:
Kiddo’s k-d tree stores items in ‘buckets’ in the leaf nodes of the tree. The bucket size is fixed at compile time, but the number of leaves grows as you add items. When an item is assigned to a new bucket, that bucket gets split and its contents get shared with a new leaf node.
When a split happens, a value is chosen for a new stem node that is used to sort the contents into one bucket or another. For example, lets assume a simple 1-d tree, with a bucket size of 6, and a leaf containing these values:
If we then add 7 to the tree, that would overflow the bucket, so we split it. We sort the bucket and split it so that the first half of the items stay in our original bucket and the second half go to the new bucket
We then pick the smallest value in the new bucket to use as our new pivot value, which we use to determine which bucket any added items go into. In this case, the pivot value will be 4.
Now we can add 7 to the tree. Since it is >=4, it will of course go in the second bucket.
But, problems arise if you have lots of items with the same value. Lets say we had a bucket that looked like this, with two 3’s in it:
And we want to add an item, triggering a split. If we apply the same logic as before, we end up with buckets like this:
With the pivot value set to 3. But now though, we have a 3 in the wrong bucket. If you tried to find it by navigating from the pivot, you wouldn’t get to it, because the pivot tells you that all the items >=3 are in the right bucket.
So, we need to change our split algorithm to check if the split point lands in between two items with the same value. If this happens, we move the split point to the left until we no longer land in between two items with the same value. Our buckets end up split like this:
This is not quite optimal, but things don’t break. But, if we get too many items with the same value in one bucket, and we try to add another, we end up with a problem:
How can we split this bucket in half? We can’t. There’s no value that we can choose to pivot on to end up with some of the items in another bucket.
This is what is happening with your dataset. You have a lot of zeroes in your data. Kiddo has a fixed bucket size. If a bucket gets full of items with the same value on one dimension, and we try to add another item that ends up in that bucket, then we can’t split the bucket, and so Kiddo has to panic.
Your only option is to increase your bucket size to a size large enough so that you don’t end up with a bucket full of items with the same value. Larger buckets can lead to worse performance, but it may not be noticeable, depending on your use case. Probably not noticeable for a tree with just 15k items.