K-Nearest Neighbors find all ties

Question

I'm currently using sklearn to compute all the k-nearest neighbors from a dataset. Say k = 10. The problem I'm having is sklearn will only return the 10 nearest neighbors and none of the other data points that may tie for the 10th nearest neighbor in terms of distance. I was wondering is there any efficient way to find any other points that may tie the kth nearest neighbor in terms of distance?

Answer 1

In theory, all points in the set may tie, making the problem a different one. Indeed, the K nearest neighbors can be reported in time O(Log N + K) in the absence of ties, whereas ties can imply K = O(N) making any solution O(N).

In practice, if the coordinates are integer, the ties will be a rare event, unless the problem has a special structure. And in floating-point, ties are virtually impossible.

IMO, handling ties will kill efficiency, for no benefit.