search

lmcinnes / pynndescent

A Python nearest neighbor descent for approximate nearest neighbors
BSD 2-Clause "Simplified" License
895 stars 105 forks source link

Minor bias in split selection? #228

Open jlmelville opened 1 year ago

jlmelville commented 1 year ago

In euclidean_random_projection_split, this part of the code is picking two random points to form the hyperplane:

https://github.com/lmcinnes/pynndescent/blob/db258cea34cce7e11e90a460c1f8a0bd8b69f1c1/pynndescent/rp_trees.py#L221-L224

right_index has an ever so slight bias to being chosen as 0, because when left_index == indices[-1] and right_index is also sampled as indices[-1], it will be "overflowed" to 0.

If right_index was selected as:

    right_index = tau_rand_int(rng_state) % (indices.shape[0] - 1)

then the bias is removed and there is no need for the right_index = right_index % indices.shape[0] -- I think?

This also affects the angular and sparse variants, but I assume this doesn't really matter. I am mainly asking to make sure I didn't miss something.

lmcinnes commented 1 year ago

No, I think you are correct. This should probably be fine for large indices, but when you get low in the tree perhaps it could actually come into play? Thanks for pointing this out; I'll have to see if I can run some small experiments and see if it is worth trying to fix this up.