Limitations on supported metrics / use of `Adaptor::accum_dist()` / Chebsyhev distance

[szhorvat]

I was looking at using the Chebyshev distance ($L_\inf$ metric) with nanoflann, and I'm wondering if this is possible at all. The question that came up:

What is the accum_dist() member function of the metric adaptor supposed to do?

As far as I can tell, it computes a value per single component $x_i$ of a difference vector $\mathbf{x}$. Then the expectation is that that these values should be summed (specifically summed, not accumulated in any other way) to obtain the final distance (or something monotonically related to it).

With a Chebyshev distance, we'd need to take the maximum instead of summing. Do I see it correctly that this is simply not possible with nanoflann?

I am also wondering about that the purpose of the idx parameter of accum_dist() is. This does not seem to be used at all in any of the built-in metrics.

[szhorvat]

CC @katgit and @bu-bgregor as you seem to have an implementation of the a Chebyshev distance here:

https://github.com/montilab/knnmi/blob/b5c09880d1dab283e1c8ec4db2f20de6fcad232c/src/include/ChebyshevMetric.h

According to my current understanding this might be incorrect (depending on what nanoflann does with accum_dist()). Can you please comment on why you believe your implementation of accum_dist() is not going to lead to invalid results?

---

Other relevant uses on GitHub:

https://github.com/Peace44/DBSCAN/blob/beabb26117c17c5ee999e0337f9bccc888cc3090/KDTREE_DBSCAN/kdtree_dbscan_OPT.cpp#L59-L66

[katgit]

@szhorvat @bu-bgregor implemented this particular algorithm. I will leave it up to him to comment.

[szhorvat]

I'm hoping that you thought this through, looked at how nanoflann uses accum_dist() in detail, and were able to determine what is needed to make this work correctly. Let me know if you have any advice.

[bu-bgregor]

@szhorvat - Thank you for pointing this out. You care correct, accum_dist() is used incorrectly in the Chebyshev metric in that package. The output of the mutual information calculations was validated against some other software libraries, however, so while it is erroneous it doesn't impact the mutual information calculations. I am looking into a fix for this. That'll take some time to do, but at this point I can't say if it'll be a more general fix applied to nanoflann.hpp or a fix that'll work just inside the knnmi software.

[szhorvat]

@bu-bgregor Thanks for looking into this! Do let me know if you find a robust way to use Chebyshev distance with nanoflann as we'd also like to use it.

@jlblancoc, do you have any input on this issue?

[jlblancoc]

Hey!

I am also wondering about that the purpose of the idx parameter of accum_dist() is. This does not seem to be used at all in any of the built-in metrics.

It took myself a while to recall this... the lib requires a good clean up... some day :-)
There is a reason for the idx in accum_dist(): to handle non-Euclidean vector spaces; e.g. say, one of the coordinates is "circular", the metric function must know what dimension index are we measuring the distance right now.

I didn't thought carefully through the whole process but in principle the Chebyshev distance could be implemented by changing two things in nanoflann.hpp:

1. computeInitialDistances(): Some trait / flag / method should be added to metric classes for this code to know how to "sum" distances (or in your case, just keeping the max value).
2. searchLevel(): here only one dimension is used to determine the search order, so there's no way to integrate Chebyshev but it may still work given the correct computation of the initial distances above.

If you have time for this, please, play around with these ideas and if adding a couple of unit tests against known results, it works, I would be glad to review / iteration on a pull request 🙏