nmslib: kNN search returns less than K results
When I experiment with the HNSW indexing method, kNN search returns less number of results than requested. Is this behavior normal? If normal, how does the algorithm decide how many neighbors to return? Thanks!
Here is a snippet of the relevant code
unsigned K = 100; // 100-NN query
KNNQuery<float> knnQ(customSpace, queryObj, K);
index->Search(&knnQ);
About this issue
- Original URL
- State: open
- Created 7 years ago
- Reactions: 3
- Comments: 17 (11 by maintainers)
@shubaoliu If you set efs (both Search and Construction) lower than K (or M in case of construction), it is quite possible that the algorithm will return less than K approximate neighbors. So to get high accuracy it is a good practice to set efConstruction>M, efSearch>K. Or even efConstruction>>M, efSearch>>K in case of high dimensionality data.
@searchivarius I suppose, in case efConstruction is set too small, index construction can become unstable, leading to weird results.
@shubaoliu I am saying that there’s no guarantee yet. However, if getting < K NNs happens on a large data set, we need to investigate.