Minor bias in split selection?

[jlmelville]

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

pynndescent/pynndescent/rp_trees.py

Lines 221 to 224 in db258ce

	left_index = tau_rand_int(rng_state) % indices.shape[0]
	right_index = tau_rand_int(rng_state) % indices.shape[0]
	right_index += left_index == right_index
	right_index = right_index % indices.shape[0]

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]

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.