Support for Neighbor Pairs Searching

[zhujunmian]

The scipy KDTree package provides a method query_pairs (in this link) which returns all the pairs within a distance for the given tree. This package seems only to provide nearest neighbor searching for a given point by the inrange function, rather than for pairs.

Such feature could also be implemented in this Julia package and should be helpful for users.

[ali-ramadhan]

What would be a good algorithm for doing this?

I imagine a naive solution might be to loop over all data points and for each data point, call inrange to get a list of nearby data points then append them to a set storing (i, j) index pairs where i < j.

[KristofferC]

I think you can do better by basically searching and pruning two trees against each other. I think I had an implementation of that but don't recall why I didn't put it in, maybe it didn't improve performance much over the naive version.

[KristofferC]

This is the tree vs tree code I was talking about:

https://github.com/JuliaGeometry/KDTrees.jl/blob/6543a0f779dfe4e3951e1075e368f8993740f90f/src/kd_tree.jl#L615-L727

Would be interesting to update this for the current code here and do some perf measurement https://github.com/JuliaGeometry/KDTrees.jl/blob/6543a0f779dfe4e3951e1075e368f8993740f90f/src/kd_tree.jl#L615-L727.