Support for non-symmetric distance measure

[Petkomat]

Sometimes, the most natural distance measures are not symmetric (e.g, roads and other networks), which is also the case for my concrete problem.

The code currently assumes that the distance is symmetric (for example, it computes d = dist(i, j) and tries to update the neighbours of i and j using d).

Would it be worth extending the code (computing both d1 = dist(i, j) and d2 = dist(j, i) where necessary if a user specifies symmetric=False) or is it known that the NNDescent approach does not work well with such distance measures (I suspect this might be so due to the reverse neighbours)?

[lmcinnes]

There actually have been versions in the past that supported non-symmetric distances (although I'm not sure they ever got pushed to github in any form). It does work, although I don't believe it was thoroughly tested with regard to how good the neighbor accuracy was (it was good enough for the one-off tasks it was coded for and applied to). You are right that reverse neighbors are a concern, but it only really constitutes a serious problem if `there are a lot of cases where d(i,j) >> d(j,i) rather than merely being unequal. Most asymmetric distance measures don't really suffer from this.

The code was never included because it had a serious performance impact on symmetric differences. To avoid that you probably need to essentially keep the existing code path, but add an alternative code path, branching off at a relatively high level, that supports the non-symmetric case (e.g. a nndescent_asymmetric function which can then call specialised asymetric versions of all the required functions below. Note that, for example, we already do that for the sparse case -- so this isn't crazy. I would certainly be happy with a PR that added such a thing.