distance_fn with bigger return type?

[wentasah]

I have a KdTree<FixedI32<U0>, usize, 2, 32, u32>. When I want to use squared_euclidean as distance_fn, I get an overflow. Would it be possible to support FixedI64 as distance_fn return type?

Currently, I work around it by using KdTree<FixedI64<U0>,...>, which seems wasteful.

[sdd]

Hi Michael. That's a good point. When I used FixedU16 I was having to sacrifice some precision in order to ensure that the distance would not overflow, which is not ideal.

Getting this working generically will be interesting - I'll have a think about how it could be done. Any suggestions or PRs appreciated, if you have some ideas.

[NeuralModder]

Hi Scott,

Again with the RGB color information. Since RGB values can be stored in a U8F0, I tried using that as coordinate type, but distances are frequently higher than 255 even with the Manhattan distance function, which forces me to use a U16F0 because of this issue.
I would say, to fix this, maybe just always set the distance type to a FixedU64 with the given bits of precision? Or calculate the maximum distance for the given coordinate type and distance function, and pick the smallest FixedUx that will fit; not sure if that's worth it though.

[sdd]

Hi @wentasah / @NeuralModder.

The upcoming Kiddo v6 rewrite on #301 will address this issue. There are a few features that will help especially when using Kiddo v6 to store RGB values:

• Result widening. As per your initial request, Kiddo v6 allows the type of the result to be specified as a generic param on the distance metric. So you can widen from 8 bits to 16 bits. The widening happens prior to the distance calculation.
• Support for u8 directly (as well as u16 / u32 / u64). This would allow RGB triplets to be stored in a format identical to the original data in many cases
• Configurable result projection. If you wanted the colour itself to be returned from the query directly, rather than an index of it that would then need the colour to be looked up by indexing into a Vec, you can choose to return the point itself rather than the stored item.
• Complementing the above, the stored item type can be set to (), rather than an unsigned integer type, reducing storage requirements and improving query performance.

I expect to release an alpha version soon as 6.0.0-alpha.1 containing these changes, to elicit initial feedback on the design.

It has only taken me 3 years! 😆