hnswlib.v0.8.0: checkIntegrity fail on tests/cpp/sift_1b.cpp

[lyj-fdu]

My branch is at v0.8.0. When building hnsw index in tests/cpp/sift_1b.cpp, I add appr_alg->checkIntegrity(); on line 346 to see if the graph built by the algorithm has in-edge for every node during report_every. However, the assertion fail!

the code fragment I modified is as follows

                if (j1 % report_every == 0) {
                    cout << j1 / (0.01 * vecsize) << " %, "
                         << report_every / (1000.0 * 1e-6 * stopw.getElapsedTimeMicro()) << " kips " << " Mem: "
                         << getCurrentRSS() / 1000000 << " Mb \n";
                    stopw.reset();
                    appr_alg->checkIntegrity(); // add this at line 346
                }

the output of command line like this

~/code/hnswlib/tests/cpp/downloads$ ../../../build/main 
Loading GT:
Loading queries:
Building index:
0.05 %, 40.9574 kips  Mem: 40877 Mb 
main: ~/code/hnswlib/tests/cpp/../../hnswlib/hnswalg.h:1403: void hnswlib::HierarchicalNSW<dist_t>::checkIntegrity() [with dist_t = int]: Assertion `inbound_connections_num[i] > 0' failed.
Aborted (core dumped)

If some node has no in-edge, then it's totally isolated, which means that search on the graph will never visisted it, even it has out-edge.

[YReddice]

Yes, I've encountered the same situation, and it does look as if the hnsw algorithm can't avoid nodes with in-degree 0, even if all points have out-degree.

[YReddice]

i think it may be because when the new insertion point creates an edge with its immediate neighbors, the cropping of the neighbor points happens to crop out the new insertion point. Do you know the cause or any other findings?