Unable to replicate example workflow in README -- stack smashing

[harsha-simhadri]

$ kgraph/index -I 14 -L 150 -S 10 -R 100 /mnt/SIFT1M/sift_base.kg.data /mnt/SIFT1M/kgraph.result Generating control... Initializing... iteration: 1 recall: 0 accuracy: 2.23433 cost: 0.00038 M: 10 delta: 1 time: 5.81898 one-recall: 0 one-ratio: 3.53372 iteration: 2 recall: 0.002 accuracy: 1.13812 cost: 0.000637557 M: 10 delta: 0.855773 time: 9.32155 one-recall: 0.01 one-ratio: 2.71138 iteration: 3 recall: 0.0344 accuracy: 0.621388 cost: 0.00109574 M: 11.5365 delta: 0.834505 time: 14.0836 one-recall: 0.08 one-ratio: 2.16501 iteration: 4 recall: 0.1912 accuracy: 0.295963 cost: 0.00163154 M: 11.8474 delta: 0.782809 time: 18.7587 one-recall: 0.23 one-ratio: 1.74459 iteration: 5 recall: 0.5088 accuracy: 0.0961833 cost: 0.00223746 M: 12.6159 delta: 0.664009 time: 23.4768 one-recall: 0.64 one-ratio: 1.28671 iteration: 6 recall: 0.7808 accuracy: 0.0235666 cost: 0.00298158 M: 15.1331 delta: 0.432179 time: 29.2621 one-recall: 0.95 one-ratio: 1.00885 iteration: 7 recall: 0.9024 accuracy: 0.00668195 cost: 0.00395733 M: 21.148 delta: 0.196402 time: 35.0734 one-recall: 0.97 one-ratio: 1.00386 iteration: 8 recall: 0.9488 accuracy: 0.00301341 cost: 0.00498334 M: 27.3224 delta: 0.088411 time: 40.8331 one-recall: 0.97 one-ratio: 1.00269 iteration: 9 recall: 0.9672 accuracy: 0.00172632 cost: 0.00577787 M: 31.3168 delta: 0.0513151 time: 45.942 one-recall: 0.98 one-ratio: 1.00231 iteration: 10 recall: 0.978 accuracy: 0.000938965 cost: 0.00626418 M: 33.429 delta: 0.0371458 time: 49.2892 one-recall: 0.99 one-ratio: 1.00059 iteration: 11 recall: 0.9816 accuracy: 0.000794071 cost: 0.00652194 M: 34.4583 delta: 0.0312213 time: 51.9613 one-recall: 0.99 one-ratio: 1.00059 iteration: 12 recall: 0.9824 accuracy: 0.000786144 cost: 0.00664935 M: 34.9466 delta: 0.0286689 time: 53.9705 one-recall: 0.99 one-ratio: 1.00059 iteration: 13 recall: 0.9828 accuracy: 0.000784735 cost: 0.00671028 M: 35.1763 delta: 0.0275193 time: 55.3717 one-recall: 0.99 one-ratio: 1.00059 iteration: 14 recall: 0.9832 accuracy: 0.000671959 cost: 0.00674068 M: 35.2903 delta: 0.0269744 time: 57.0438 one-recall: 1 one-ratio: 1 0 62.858780s wall, 1093.320000s user + 74.460000s system = 1167.780000s CPU (1857.8%)

$ nsg/tests/kgraph2ivec /mnt/SIFT1M/kgraph.result /mnt/SIFT1M/sift.150nngraph KNNGRAPH 2 0 1000000 stack smashing detected : nsg/tests/kgraph2ivec terminated Aborted (core dumped)

Could you please suggest how to fix this? experiment run on Ubuntu 16LTS, gcc5.4.0.

[fc731097343]

It seems that the graph file format of the KGraph is now inconsistent with what we expect to read. You need to convert the result of the KGraph into the format we need:

[fc731097343]

The "ivecs" format is what you need (binary file with no blank or other separators): For each line of the graph, we begin with an int32 N indicating the number of neighbors, and the following are the indices of the neighbors (N int32s). For example: 150 1 5 3 13 ...... 99 150 91 45 23 143 ...... 9 150 23 42 36 38 ...... 43 ...... Note that there are no separators between numbers.

[xuxiaohui4]

Did you solve the problem? Could you share with me how to deal with it?

[fc731097343]

You need to convert the KNN graph file produced by KGraph into the "ivecs" format as I mentioned above. It's a very simple coding work. I believe you can do it. See http://corpus-texmex.irisa.fr/ for more details on the data format.

[xuxiaohui4]

Thank you for your answer, now I know what format file I should give to nsg/tests/kgraph2ivec. Another problem is that I don't know the format of the KNN graph file produced by kGraph, so I can't finish the coding. Emmm could you explain the format of the KNN graph file produced by kGraph for me or just share a link where its format is explained?(Maybe it's too easy?)

[fc731097343]

First is 8 char (magic char array), then an int32 (version number), then an int32 (dist indicator), then an int32 (N the total number of the points).

Next is the index part. It's in the following format: If you save it with no-distance format (which can be specified as saving parameters): int32 (M) int32 (K) int32K (ids) int32 (M) int32 (K) int32K (ids) int32 (M) int32 (K) int32K (ids) int32 (M) int32 (K) int32K (ids) .... ....

If you save it with distance format: int32 (M) int32 (K) int323K (neighbor struct) int32 (M) int32 (K) int323K (neighbor struct) int32 (M) int32 (K) int323K (neighbor struct) int32 (M) int32 (K) int323K (neighbor struct) .... ....

For your convenience, I suggest you save the index with no-distance format. See the code of KGraph for more details (the "load" function) https://github.com/aaalgo/kgraph/blob/master/kgraph.cpp

Sometimes it's necessary to develop the ability to read others' codes. Good Luck : )

[xuxiaohui4]

Thank you~ Memeda!!!

[xuxiaohui4]

Emmmm. I'm here again..... Now I read the kgraph.result file, then I got the output below. This is built from the sift_base.fvecs.

kgraph index info: KNNGRAPH 2 0 1000000 kgraph index data part: (57, 150, 2, 1183991808, 0, 6, 1186856960, 0, 83606, 1193419264, 0, 631203, 1194433536, 0, 677834, 1194702080, 0, 246710, 1194832384, 0, 677793, 1194867712, 0, 480592, 1195016192, 0, 10336, 1195058432, 0, 658180, 1195215616, 0, 799350, 1195235584, 0, 738996, 1195304704, 0, 516942, 1195433472, 0, 965310, 1195441408, 0, 451321, 1195466496, 0, 725637, 1195534592, 0, 480903, 1195574528, 0, 719046, 1195605248, 0, 248230, 1195829248, 0, 799488, 1195876608, 0, 500141, 1195990272, 0, 799404, 1196037888, 0, 466880, 1196076800, 0, 529593, 1196107520, 0, 688749, 1196180736, 0, 558961, 1196189696, 0, 686828, 1196217344, 0, 183625, 1196237824, 0, 432221, 1196304896, 0, 532473, 1196316160, 0, 187896, 1196362752, 0, 678008, 1196373504, 0, 772144, 1196415744)

Here I read 100 int32 as in the bracket. It seems right as 57=M, 150=K. As I thought, 150*3=450 int32s follow the 150. For example, 2 indicate the point_id, 1183991808 indicates the dist(current_point, 2), 0 indicate whether this entry is a newly found one. I wonder what the current_point_id is ?

For this example, the binary file I should write is 150 2 6 83606 ... 150 ....? Is there anything I'm wrong?

[fc731097343]

It seems that you save the index in "with-distance" format. I said above that it's better to save it in "no-distance" format. This can be specified in the input parameters in KGraph's indexing procedure. You need to read its documents. Obviously, the number "1183991808" is not an integer. It's a float32, indicating the distance. And the following flag is the "bool flag" in the "neighbor" struct.

[xuxiaohui4]

Hey, guy. It seems the file generated by the following command is larger than 200G? ---using sift1M_base data. $nsg/tests/kgraph2ivec kgraph.result sift.150nngraph

[fc731097343]

I thought you convert the data with your own code. If you use kgraph2ivec, you need to generate the kgraph index in "with-distance" format. It's impossible to be 200G, and you are probably using the wrong data format.