overflow when building index

[piskvorky]

Using FLANN from repo (master branch at 9125041) and

$ uname -a
Linux m3-2xlarge 3.11.0-12-generic #19-Ubuntu SMP Wed Oct 9 16:20:46 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1

I asked for target_precision=0.999 with autotune. FLANN munches for a while, then something goes wrong (line 586):

     12 Entering autotuning, dataset size: 3487548, sampleSize: 348754, testSampleSize: 1000, target precision: 0.999
     13 Computing ground truth...
     14 Autotuning parameters...
     15 KMEANS, Step 1: Exploring parameter space
     16 KMeansTree using params: max_iterations=1, branching=16
     17   Nodes  Precision(%)   Time(s)   Time/vec(ms)  Mean dist
     18 ---------------------------------------------------------
     19        1      0.292      0.044      0.044     1.4332
     20        2      0.303      0.044      0.044     1.4102
...
    543 ----------------------------------------------------
    544 Autotuned parameters:
    545 algorithm : 2
    546 branching : 128
    547 centers_init : 0
    548 iterations : 10
    549 ----------------------------------------------------
    550 Computing ground truth
    551 Estimating number of checks
    552 KMeans algorithm, estimating cluster border factor
    553   Nodes  Precision(%)   Time(s)   Time/vec(ms)  Mean dist
    554 ---------------------------------------------------------
    555        1      0.371       0.21       0.21     1.2449
    556        2      0.371       0.21       0.21     1.2449
    557        4      0.423       0.22       0.22     1.1891
    558        8      0.461       0.23       0.23      1.163
    559       16      0.516       0.23       0.23     1.1373
    560       32      0.565       0.27       0.27     1.1161
    561       64      0.619       0.31       0.31     1.0917
    562      128      0.685        0.4        0.4      1.064
    563      256      0.744       0.61       0.61     1.0463
    564      512      0.802       0.96       0.96     1.0351
    565     1024      0.857       1.73       1.73     1.0241
    566     2048      0.924       3.23       3.23     1.0098
    567     4096      0.963       6.44       6.44     1.0042
    568     8192      0.986      13.59      13.59     1.0021
    569    16384      0.995       29.2       29.2     1.0004
    570    32768      0.996      60.64      60.64          1
    571    65536      0.996     119.73     119.73          1
    572   131072      0.996     242.14     242.14          1
    573   262144      0.996     473.86     473.86          1
    574   524288      0.996     945.31     945.31          1
    575  1048576      0.996     1822.8     1822.8          1
    576  2097152      0.996     2233.4     2233.4          1
    577  4194304      0.996     2333.6     2333.6          1
    578  8388608      0.996     2153.6     2153.6          1
    579 16777216      0.996     2181.5     2181.5          1
    580 33554432      0.996     2144.3     2144.3          1
    581 67108864      0.996     2090.7     2090.7          1
    582 134217728      0.996     2091.6     2091.6          1
    583 268435456      0.996     2106.8     2106.8          1
    584 536870912      0.996     2178.2     2178.2          1
    585 1073741824      0.996     2169.4     2169.4          1
    586 -2147483648      0.371       0.21       0.21     1.2449
    587        0      0.371       0.22       0.22     1.2449
    588        0      0.371       0.22       0.22     1.2449
    589        0      0.371       0.22       0.22     1.2449
...
  53020        0      0.371       0.21       0.21     1.2449
  53021        0      0.371       0.21       0.21     1.2449
  53022        0      0.371       0.21       0.21     1.2449
  53023        0      0.371       0.21       0.21     1.2449
...

apparently an infinite loop.

Is the target precision too high? What are the acceptable values?

Lower values (0.99) worked OK, but didn't give me the approximation quality I needed.

[piskvorky]

Same thing with `target_precision=0.995". Seems 0.99 is the best FLANN can do without hanging, on this dataset.