Source-linked AI summary
ikd-Tree: An Incremental K-D Tree for Robotic Applications
Yixi Cai, Wei Xu, Fu Zhang
TL;DR
Robotic applications need dynamic nearest-neighbor structures that can keep pace with sequential point acquisition without repeatedly rebuilding static k-d trees. The paper introduces ikd-Tree, which incrementally updates, down-samples, and partially re-balances k-d trees while supporting point-wise and box-wise operations. In LiDAR-inertial mapping, its incremental updates average 0.23 ms, or 4% of the static k-d tree time, while nearest-search times remain at the same level.
Problem
Sequential robotic data makes rebuilding a static k-d tree from all points inefficient, while dynamic designs must also support space operations and efficient re-balancing.
Method
ikd-Tree incrementally inserts, deletes, and re-inserts points or boxes, down-samples data, and partially re-builds unbalanced subtrees while maintaining lazy-update metadata.
Results
0.23 ms average incremental-update time is 4% of the static k-d tree time, while nearest-search times are at the same level in LiDAR-inertial mapping.
Takeaways & Limitations
ikd-Tree supports accurate nearest search with approximately O(log n) time for the low point dimensions typical of robotic applications.
Abstract
from arXiv · showhide
This paper proposes an efficient data structure, ikd-Tree, for dynamic space partition. The ikd-Tree incrementally updates a k-d tree with new coming points only, leading to much lower computation time than existing static k-d trees. Besides point-wise operations, the ikd-Tree supports several features such as box-wise operations and down-sampling that are practically useful in robotic applications. In parallel to the incremental operations (i.e., insert, re-insert, and delete), ikd-Tree actively monitors the tree structure and partially re-balances the tree, which enables efficient nearest point search in later stages. The ikd-Tree is carefully engineered and supports multi-thread parallel computing to maximize the overall efficiency. We validate the ikd-Tree in both theory and practical experiments. On theory level, a complete time complexity analysis is presented to prove the high efficiency. On experiment level, the ikd-Tree is tested on both randomized datasets and real-world LiDAR point data in LiDAR-inertial odometry and mapping application. In all tests, ikd-Tree consumes only 4% of the running time in a static k-d tree.
I. INTRODUCTION
Static k-d trees are poorly matched to sequential robotic data because rebuilding from scratch is costly, while dynamic designs must support updates, re-balancing, and real-time operation. The paper proposes ikd-Tree to address these needs through incremental updates, partial rebuilding, and broader point-cloud operations.
- Static k-d trees rebuild from all points, making sequential incorporation of new data inefficient and time-consuming.
- Local insertion and deletion can eliminate redundant rebuilding, especially when newly acquired data is much smaller than the existing tree.
- Dynamic k-d trees must support point and space operations, prevent imbalance after updates, and re-balance efficiently enough for real-time robotics.
- ikd-Tree incrementally updates and down-samples new points, supports point-wise and box-wise operations, and partially re-builds unbalanced sub-trees.
- The design targets sequentially sampled robotic applications such as real-time LiDAR mapping and motion planning, while related methods often lack deletion or use complete rebuilding.
III. IKD-TREE DESIGN AND IMPLEMENTATION
ikd-Tree extends a balanced k-d tree with metadata and incremental update mechanisms. Its design combines recursive construction, lazy deletion, and node attributes that support later re-balancing and space operations.
- ikd-Tree stores standard child and axis fields together with tree size, invalid-node count, lazy labels, and other update metadata.
- The implementation provides algorithmic support for building a balanced tree and maintaining node state during incremental operations.
- The initial tree is built by sorting points along the highest-covariance division axis, selecting the median, and recursively constructing both subtrees.
- Incremental updates insert, delete, or re-insert points, with deletion implemented lazily by marking nodes instead of removing them immediately.
2 Function Build(V, l, r)
Deleted points remain represented through lazy labels until rebuilding, while box-wise updates extend the same mechanism from individual points to axis-aligned regions.
- A point marked deleted can be re-inserted efficiently by resetting its deleted attribute rather than creating a new tree node.
- Points that remain deleted are removed during the rebuilding process rather than immediately after deletion.
- Point-wise updates affect one point, whereas box-wise updates insert, delete, or re-insert all points inside an axis-aligned box.
1) Pushdown and Pullup:
The implementation maintains subtree metadata through Pushdown and Pullup while recursively processing box operations and spawning parallel rebuilding when imbalance criteria require it.
- 1) Pushdown and Pullup: Pushdown propagates lazy labels from a node to its immediate sons when the node's pushdown flag is active.
- 1) Pushdown and Pullup: Pullup summarizes subtree size, deleted-node count, and coordinate ranges at the current node.
- 1) Pushdown and Pullup: Point-wise updates are implemented recursively on the incremental k-d tree.
- 1) Pushdown and Pullup: When a subtree violates the balancing criterion, parallel rebuilding can be spawned subject to subtree-size and parallelization conditions.
23 End Function
Point-wise and box-wise updates modify the incremental k-d tree recursively, using lazy labels and rebuilding when balance criteria are violated.
- Point-wise insertion recursively descends the tree to append a new node, while deletion and re-insertion modify the stored point's deleted attribute.
- Box-wise insertion adds points individually, whereas box-wise deletion and re-insertion use range information and lazy labels.
- When a box partially intersects a subtree, the algorithm updates contained points, recursively visits child nodes, refreshes attributes, and re-balances if needed.
4) Downsample:
The tree supports down-sampling and monitors structural balance using criteria based on subtree size and invalid-node counts, triggering partial rebuilding when necessary.
- 4) Downsample: Down-sampling partitions space into cubes of resolution L and keeps the point nearest the cube center.
- Supported updates: The comparison concerns supported incremental updates across static, dynamic, scapegoat, and ikd-Tree variants.
- Re-balancing: The balance test combines an α-balanced criterion with an α-deleted criterion based on subtree size and invalid-node count.
- Re-balancing: Violating either criterion triggers rebuilding; the balance criterion limits subtree height, while the deleted criterion controls invalid nodes.
2) Re-build:
Unbalanced subtrees are rebuilt by flattening valid points and constructing a new balanced tree, with large rebuilds moved to a parallel thread to preserve real-time operation.
- 2) Re-build: Rebuilding flattens a subtree into an array, discards deleted nodes, and constructs a perfectly balanced k-d tree from the remaining points.
- Parallel rebuilding: Large-subtree rebuilding can degrade real-time ability, motivating a double-thread method that separates rebuilding from the main thread.
- Parallel rebuilding: The main thread rebuilds subtrees smaller than Nmax, while a second thread handles the rest.
- Parallel rebuilding: During parallel rebuilding, updates are locked during copying, recorded while the original subtree remains queryable, then applied to the replacement tree before swapping it in.
- Search: Nearest-neighbor search remains accurate and uses stored range information to speed search.
1 Function ParallelRebuild(T )
The analysis establishes logarithmic point-wise and down-sampling complexity, while box-wise operations receive bounds determined by inserted points and spatial range geometry.
- 1) Incremental Operations: O(log n) is the time complexity for a point-wise incremental operation on an incremental k-d tree.
- Box-wise operations: O(m log n) is the complexity of inserting m points within a box in a 3-d incremental tree.
- Box-wise operations: Box-wise deletion and re-insertion have complexity O(H(n)), with H(n) determined by the tree size and normalized box dimensions.
- Downsample: Down-sampling combines box-wise search and deletion with point insertion and has complexity O(log n) when the down-sampling cube is small relative to the full space.
2) Re-build:
The ikd-Tree’s rebuilding complexity is O(n) with two-thread parallel rebuilding versus O(n log n) single-thread rebuilding, while k-nearest search is approximately O(log n) for low-dimensional robotic data.
- Re-building: O(n) rebuilding is achieved with two-thread parallel execution, compared with O(n log n) for single-thread rebuilding.The main thread performs flattening while the second thread builds the tree; single-thread rebuilding sorts recursively across log n levels.
- Re-building: O(log n) approximates k-nearest search complexity because robotic applications typically use low-dimensional points and maintain tree height near log n.
B. Space Complexity
The ikd-Tree maintains linear space complexity while supporting incremental updates, rebalancing, and robotic LiDAR mapping experiments. Its practical evaluations show substantially lower update and overall processing times than static k-d trees.
- Space Complexity: O(n) space complexity is achieved for an incremental k-d tree, although its space constant is a few times larger than a static k-d tree.Each node stores point information, tree size, invalid-point count, point distribution, and lazy-operation flags.
- Randomized Data Experiments: One-order-of-magnitude lower overall time is achieved by ikd-Tree than a static k-d tree in randomized incremental operations.Its query performance is slightly slower, possibly because of the highly optimized PCL implementation.
- LiDAR Inertial-Odometry and Mapping: 1.6 ms is the nearly constant average time for fusing a LiDAR scan with ikd-Tree, compared with static-tree processing that exceeds 10 ms after 366 s.The reported timing supports mapping rates up to 100 Hz, versus 10 Hz in the original static-tree-based work.
- LiDAR Inertial-Odometry and Mapping: 0.23 ms is the average incremental-update time with ikd-Tree, compared with 5.71 ms for a static k-d tree.Nearest-search times are reported to be at the same level for both trees.
- LiDAR Inertial-Odometry and Mapping: The tree remains well-balanced through incremental updates because the two balance criteria stay below prescribed thresholds after rebuilding.Temporary threshold peaks occur during parallel rebuilding and drop quickly when rebuilding finishes.
VI. CONCLUSION
The paper proposes ikd-Tree, a dynamic k-d tree for robotic applications that incrementally updates data while maintaining balance through partial rebuilding. Randomized and outdoor LiDAR experiments evaluate its efficiency.
- VI. CONCLUSION: The ikd-Tree supports incremental robotic operations while maintaining balance through partial rebuilding, with complete time and space complexity analysis.Its evaluation includes randomized experiments and an outdoor LiDAR odometry and mapping experiment.