Flann.fromDataset(dataset) become extremely slow when points equal 1000

[AndrewChan2022]

When I test web-examples\plane, build index is very fast when points number less than 1000,
but quickly become very slow when points number is 1000.

var numberOfPivots = 999 is very fast. less than 1 seconds.

var numberOfPivots = 1000 extremly slow. about 10 seconds.

[agrbin]

Thank you for reaching out and documenting this issue!

I can only confirm your observation and give repro links:

• https://agrbin.github.io/flann.js/plane/index.html#n999, loads quickly
• https://agrbin.github.io/flann.js/plane/index.html#n1000, loads slowly

Unfortunatelly I will not have time to dig in to understand better why this happens. One thing that caught my eye from the README:

Autotuned index is built based on those pivot points.

Maybe the "autotune" has a hard threshold on 1000, and then a different indexing strategy is used.

The upstream C++ code for autotuned index is here:
https://github.com/flann-lib/flann/blob/f9caaf609d8b8cb2b7104a85cf59eb92c275a25d/src/cpp/flann/algorithms/autotuned_index.h#L73