Insertion Performance

To better understand the performance of the library, it is best to look at some alternatives, since you are likely to choose among them, which one to use. The following libraries are being pitched in comparison with Spatial.

libkdtree++

Spatial aims at being a descendant of libkdtree++, comparing the C++ API only it provide a superior amount of features. libkdtree++ provides binding to other languages and it is older. Spatial also aims at similar or better performance than libkdtree++ for its algorithms.

The sources used for the comparison are retrieved from

https://github.com/nvmd/libkdtree.git

libkdtree++ is a header-only library, hence its source code is directly compiled in the benchmark programs.

Boost.Geometry.Index

The Boost.Geometry.Index is based on R-tree implementation. R-trees generally provide better insertion and removal performance than k-d trees, however both R-tree and k-d tree indexing invariants are making them less efficient in higher dimensions.

The sources used for the comparison are sources from the anonymous read-only SVN repository:

http://svn.boost.org/svn/boost/trunk/boost/geometry/index

Boost.Geometry.Index is a header-only library, hence its source code is directly compiled in the benchmark programs.

Flann

To be completed.

This is a little bit like comparing Apples and Oranges, but Flann, which is expected to be the fastest of the 4 libraries to perform nearest neighbor search (even with an 100% accuracy requirement) will provide the benchmark for that particular algorithm.