facebookresearch
random generator produces the same number sequence with the same seed
Summary
In random.h, struct RandomGenerator, random generator produces the same number sequence with the same seed. I found this problem in NSG.cpp, search_on_grapth function.
Platform
Faiss version:e7b9d5514bc41109a0c502bcb6dc72ac196b287a
Reproduction instructions
It is easy to be reproduced.
What did you expect?
Would it be better to generate random vertex sequences with different queries? A fixed group of "random" vertexes that fill the candidate pool seems a little wired. I'm not sure whether it will do harm to the performance or not.
Right, in NSG this is actually a valid concern. @KinglittleQ what do you think?
The original intent was to make the search process deterministic, which will produce the same search result given the same query. This deterministic does not harm the accuracy according to my evaluation.
I think your concern is reasonable. Maybe we could find a way to generate random sequences depending on the query point.
Assuming x is the query vector, we could set the random seed to *(unsigned int*)&(sum(x)).
There is a hash function that could be applied to queries: https://github.com/facebookresearch/faiss/blob/151e3d7be54aec844b6328dc3e7dd0b83fcfa5bc/faiss/utils/utils.h#L168
Thank you both. Maybe @KinglittleQ can change this line in the next pr, if you think it's more reasonable.