nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType > Class Template Reference

#include <nanoflann.hpp>

Public Types
using	Inner = KDTreeSingleIndexIncrementalAdaptor<Distance, DatasetAdaptor, DIM, IndexType>
using	ElementType = typename Inner::ElementType
using	DistanceType = typename Inner::DistanceType
using	Size = typename Inner::Size
using	Dimension = typename Inner::Dimension
using	BoundingBox = typename Inner::BoundingBox

Public Member Functions
	KDTreeSingleIndexIncrementalAdaptorMT (const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeIncrementalIndexParams &params={}, double rebuild_growth=1.3, Size min_rebuild_size=10000)
	KDTreeSingleIndexIncrementalAdaptorMT (const KDTreeSingleIndexIncrementalAdaptorMT &)=delete
KDTreeSingleIndexIncrementalAdaptorMT &	operator= (const KDTreeSingleIndexIncrementalAdaptorMT &)=delete
void	setRebuildCallback (std::function< void(Inner &)> cb)
Modifiers @{
void	addPoints (IndexType start, IndexType end)
void	addPoint (IndexType idx)
void	removePoint (IndexType idx)
void	removeBox (const BoundingBox &box)
void	removeOutsideBox (const BoundingBox &keep)
Query methods (forwarded to the active tree) @{
template<typename RESULTSET>
bool	findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParameters &sp={}) const
Size	knnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &sp={}) const
Size	radiusSearch (const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &sp={}) const
Size	rknnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
template<typename RESULTSET>
Size	findWithinBox (RESULTSET &result, const BoundingBox &bbox) const
Observers @{
Size	size () const noexcept
bool	empty () const noexcept
Size	physicalSize () const noexcept
bool	isRebuilding () const noexcept
NANOFLANN_NODISCARD BoundingBox	boundingBox () const
void	snapshotLiveIndices (std::vector< IndexType > &out) const
void	reserve (Size n)
void	sync ()
const Inner &	activeIndex () const
Dataset-storage reclamation @{
void	setCollectRemovedPoints (bool enable)
std::vector< IndexType >	acquireRemovedPoints ()

Detailed Description

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>
class nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >

Multi-threaded variant of KDTreeSingleIndexIncrementalAdaptor that hides the O(N) near-root rebuild spike: the large balancing rebuild is performed on a background thread while the foreground tree keeps serving inserts, deletions and queries.

Model (single foreground thread + one background rebuild thread):

• The live ("active") tree never rebalances inline; it only appends and lazily tombstones, so every foreground call returns quickly.
• When the active tree has grown / accumulated tombstones past a threshold, a snapshot of its live point indices is taken and a background thread bulk-builds a fresh, balanced tree from it. Foreground operations meanwhile keep mutating the active tree and are appended to a small op-log.
• At the next foreground call after the build finishes, the op-log is replayed onto the fresh tree and it atomically replaces the active tree.

This keeps the foreground tail latency bounded (snapshot + replay) instead of paying the full O(N) rebuild inline. It matches ikd-Tree's async-rebuild idea but with a thread-isolated build (no per-node locks), a bounded std::deque- style op-log (no fixed 10⁶ queue), and no PCL/pthread dependency.

Warning

Same threading contract as the synchronous index for the foreground thread (const queries are safe for concurrent readers; no concurrent writer). Additionally, because the background thread reads point coordinates from the dataset adaptor, the dataset must keep stable element storage while a rebuild is in flight (e.g. reserve() the backing vector, or use a std::deque) so that appends on the foreground thread do not reallocate it. Disabled entirely under NANOFLANN_NO_THREADS.

Constructor & Destructor Documentation

KDTreeSingleIndexIncrementalAdaptorMT()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >::KDTreeSingleIndexIncrementalAdaptorMT ( const Dimension dimensionality, const DatasetAdaptor & inputData, const KDTreeIncrementalIndexParams & params = {}, double rebuild_growth = 1.3, Size min_rebuild_size = 10000 )

inlineexplicit

Constructor.

Parameters

rebuild_growth	Trigger a background rebuild once the physical node count exceeds this factor of the live count at the last rebuild (captures both appends and tombstone accumulation).
min_rebuild_size	Never trigger below this many physical nodes.

Member Function Documentation

acquireRemovedPoints()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

std::vector< IndexType > nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >::acquireRemovedPoints ( )

inline

Move out the point indices whose dataset slots became free since the last call (no live OR tombstoned tree node references them — safe to recycle). Requires setCollectRemovedPoints(true).

activeIndex()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

const Inner & nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >::activeIndex ( ) const

inline

Access the underlying active tree (e.g. for further query types).

boundingBox()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

NANOFLANN_NODISCARD BoundingBox nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >::boundingBox ( ) const

inline

Live AABB of the active tree (see the synchronous index).

reserve()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >::reserve ( Size n )

inline

Pre-size the active tree's internal map (see the synchronous index).

setCollectRemovedPoints()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >::setCollectRemovedPoints ( bool enable )

inline

Enable recording of dataset slots that become free when a background rebuild drops tombstoned points (so the caller can recycle them and keep the dataset bounded). Off by default (cost-free when unused).

setRebuildCallback()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >::setRebuildCallback ( std::function< void(Inner &)> cb )

inline

Set a callback invoked on the background worker thread on each freshly built tree, right after it is balanced and before it is handed back for integration. Lets the caller recompute per-point auxiliary data (e.g. covariances) off the foreground thread. The callback runs concurrently with foreground queries on the old tree, so it must only touch the passed-in fresh index and its own/snapshot data — never foreground-shared state without external synchronization. Pass {} to clear.

snapshotLiveIndices()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >::snapshotLiveIndices ( std::vector< IndexType > & out ) const

inline

Append the live point indices of the active tree into out.

sync()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >::sync ( )

inline

Block until any in-flight background rebuild has been integrated.

---

The documentation for this class was generated from the following file:

• include/nanoflann.hpp