search

nmslib / hnswlib

Header-only C++/python library for fast approximate nearest neighbors
https://github.com/nmslib/hnswlib
Apache License 2.0
4.36k stars 645 forks source link

The searching process sometimes only return the entorpoint #220

Open orrorcol opened 4 years ago

orrorcol commented 4 years ago

My application occasionally met a case that when all neighbors of entorpoint are marked delete and are further to the query point. The search process will terminate and only return the entorpoint.

https://github.com/nmslib/hnswlib/blob/a97ec891e8aa19587897523ef70b3a923c14f99a/hnswlib/hnswalg.h#L259-L265 https://github.com/nmslib/hnswlib/blob/a97ec891e8aa19587897523ef70b3a923c14f99a/hnswlib/hnswalg.h#L295-L311

Should we add some constrains to prevent the searching process from terninating too quickly?

yurymalkov commented 4 years ago

@uestc-lfs, thanks for reporting! One of the the stop condition does not hold if some elements are omitted. Probably the best way to solve it is to add check if there are deletions and top_candidates.size()>=ef the in line #264. Not sure.

orrorcol commented 4 years ago

@yurymalkov Thank you for your quick response. I agree that we can check the size of top_candidates or visited_list in line 264

yurymalkov commented 4 years ago

Not yet implemented it.