k-neighbor and radius search with CAPT

[viniciusmgn]

First and foremost, amazing work!

I am planning to use the CAPT code only in my research. However, it seems it does not support k-neighbor search. Is there a CAPT implementation of this feature somewhere?

[claytonwramsey]

As currently implemented, no, there is no support for k-nearest neighbors in a CAPT.

However, it is possible to implement, and in some circumstances would be much faster than a $k$-d tree.
Out of curiosity, what are you using it for?
Can you clarify a little about your needs; in particular:

• do you need exact $k$-nearest-neighbors or are approximate neighbors OK?
• Can $k$ be exactly equal to (or at least an integer multiple of) the SIMD vector size?
• Do you already have knowledge of the maximum distance to a neighbor and/or can you come up with a bound for it?

[viniciusmgn]

Thanks for the quick response.

In fact, I made a confusion. What I need is not a (k) nearest neighbor, but a range search, that is, to get all points within a radius R of a given point.

To give you an adapted answer related to this new question, I plan to use this feature to compute weighted averages, in which the weights are governed by distances from points in the tree to a given query point. The weights are sharply decreasing as a function of the distance. Given that, definitely the query can be approximated in the sense that if it gets points outside the range they are not going to matter and also that the average is (more or less) robust to some noise.

[claytonwramsey]

This is excellent, because range search is much easier to do with a CAPT than $k$-NN (though it is also not implemented here). For maximum performance, I would recommend forking the CAPT implementation and then implementing your intended method as a modification to collides_simd. It should be relatively easy to do (methinks).

The best place to start would be by working from the last phase of collision-checking in the sequential or parallel implementation. In your case, instead of returning true as soon as we encounter a result-point within a fixed radius of our query-point, you would probably want to execute a user-provided closure or compute your weighted averages there.

[viniciusmgn]

Thanks!