Loading...
Searching...
No Matches
nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType > Class Template Reference
nanoflann C++ library for KD-trees » KD-tree classes and adaptors

`#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
Persistence (see the synchronous index's saveIndex()/loadIndex())
void | saveIndex (std::ostream &stream)
void | loadIndex (std::istream &stream)
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. That background thread is one persistent worker started on the first rebuild and reused for every later one, not one thread per rebuild: a long-running incremental map triggers rebuilds continuously, and a thread per rebuild would make the host process churn through thousands of OS threads, multiplying every per-thread cost it carries (malloc arenas, sanitizer bookkeeping) for no benefit.
- 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 )

inline explicit

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).

## loadIndex()

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

void nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >::loadIndex | ( | std::istream & | stream | ) |

inline

Blocks until any in-flight background rebuild is integrated, then loads a previously saved topology into the active tree (see the synchronous index's loadIndex() precondition: the active tree must be freshly constructed / empty).

## 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).

## saveIndex()

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

void nanoflann::KDTreeSingleIndexIncrementalAdaptorMT< Distance, DatasetAdaptor, DIM, IndexType >::saveIndex | ( | std::ostream & | stream | ) |

inline

Blocks until any in-flight background rebuild is integrated (see sync()), then serializes the active tree's topology.

## 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