Keeping multiple candidates while searching

[lukipuki]

Hi,
have you considered keeping multiple candidates from each layer while searching?
This code selects only one candidate from each layer before going to the next layer.

Does it make sense to keep more candidates, e.g. 2? Keeping 2 candidates instead of 1 might not cause a 100% slowdown, since the neighbors of the 2 candidates might have overlap and thus the number of distance calculations might go up by much less than 100%. E.g. with 60% overlap there will be only 40% more distance calculations.

[yurymalkov]

Hi @lukipuki ,

Sometime ago I've implemented passing multiply neighbors in nmslib and saw a small (yet measurable) increase in speed/accuracy (as far as I remember ~5-10% max after parameter tuning). However, it was coded in a ugly way and introduced a new parameter (number of candidates passed), which was not clear how to set.

So, I decided to remove this option.