Template Class KDTreeSingleIndexIncrementalAdaptorMT

Nested Relationships

Nested Types

Class Documentation

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

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.

Modifiers @{

inline void addPoints(IndexType start, IndexType end)
inline void addPoint(IndexType idx)
inline void removePoint(IndexType idx)
inline void removeBox(const BoundingBox &box)
inline void removeOutsideBox(const BoundingBox &keep)

Query methods (forwarded to the active tree) @{

template<typename RESULTSET>
inline bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &sp = {}) const
inline Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &sp = {}) const
inline Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector<ResultItem<IndexType, DistanceType>> &IndicesDists, const SearchParameters &sp = {}) const
inline Size rknnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
template<typename RESULTSET>
inline Size findWithinBox(RESULTSET &result, const BoundingBox &bbox) const

Observers @{

inline Size size() const noexcept
inline bool empty() const noexcept
inline Size physicalSize() const noexcept
inline bool isRebuilding() const noexcept
inline NANOFLANN_NODISCARD BoundingBox boundingBox () const

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

inline void snapshotLiveIndices(std::vector<IndexType> &out) const

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

inline void reserve(Size n)

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

inline void sync()

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

inline const Inner &activeIndex() const

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

Dataset-storage reclamation @{

inline void setCollectRemovedPoints(bool enable)

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

inline std::vector<IndexType> acquireRemovedPoints()

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

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 Functions

inline explicit KDTreeSingleIndexIncrementalAdaptorMT(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeIncrementalIndexParams &params = {}, double rebuild_growth = 1.3, Size min_rebuild_size = 10000)

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.

KDTreeSingleIndexIncrementalAdaptorMT(const KDTreeSingleIndexIncrementalAdaptorMT&) = delete
KDTreeSingleIndexIncrementalAdaptorMT &operator=(const KDTreeSingleIndexIncrementalAdaptorMT&) = delete
inline ~KDTreeSingleIndexIncrementalAdaptorMT()
inline void setRebuildCallback(std::function<void(Inner&)> cb)

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.