Pith. sign in

REVIEW 12 cited by

ikd-Tree: An Incremental K-D Tree for Robotic Applications

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2102.10808 v1 pith:TSM24CII submitted 2021-02-22 cs.RO

Yixi Cai , Wei Xu , Fu Zhang This is my paper · ORCID
classification cs.RO
keywords ikd-treetreeoperationstimeapplicationsdataefficiencyefficient
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 12 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Parallel $k$d-tree with Batch Updates

    cs.DS 2024-11 accept novelty 7.0 of 10

    A new parallel kd-tree construction and batch-update design based on sampling and multi-level sieving reduces build and update times by orders of magnitude versus prior libraries.

  2. ECO: Incremental Ego-Centric Octree Update for Point Streams

    cs.RO 2026-07 accept novelty 6.0 of 10

    Ego-Centric Octree (ECO) maintains a robot-centered, fixed-volume octree via shift-out/shift-in/overlap incremental updates, reducing update time ~25% vs full rebuild and ~55% vs bounded i-Octree on KITTI.

  3. IncA-DES: An incremental and adaptive dynamic ensemble selection approach using online K-d tree neighborhood search for data streams with concept drift

    cs.LG 2025-07 conditional novelty 6.0 of 10

    IncA-DES reports the best average accuracy among eight streaming classifiers on 22 datasets, with speedups from an online K-d tree neighbor search.

  4. Vibration-aware Lidar-Inertial Odometry based on Point-wise Post-Undistortion Uncertainty

    cs.RO 2025-07 conditional novelty 6.0 of 10

    Modeling the residual distortion of each LiDAR point as a per-point covariance and using it in matching and residual weighting reduces odometry error under intense vibration.

  5. GaRLIO: Gravity enhanced Radar-LiDAR-Inertial Odometry

    cs.RO 2025-02 conditional novelty 6.0 of 10

    GaRLIO uses radar Doppler velocity measurements to estimate gravity and reduce vertical drift in LiDAR-inertial odometry, outperforming three LIO baselines on public datasets.

  6. SLIDER: Sparse History-Guided Aerial Robot Target Search using Sliding Local Maps

    cs.RO 2026-07 conditional novelty 5.5 of 10

    A local sliding map plus history-pose observation inference and incremental viewpoint clustering lets aerial robots search large unknown scenes with less memory and lower decision latency than dense-map baselines.

  7. FAST-LIVO2 on Resource-Constrained Platforms: LiDAR-Inertial-Visual Odometry with Efficient Memory and Computation

    cs.RO 2025-01 conditional novelty 5.0 of 10

    A LiDAR-inertial-visual odometry system skips most camera frames when the laser gives enough constraints, reducing runtime and memory on edge hardware for a small accuracy loss.

  8. AF-RLIO: Adaptive Fusion of Radar-LiDAR-Inertial Information for Robust Odometry in Challenging Environments

    cs.RO 2025-07 conditional novelty 4.0 of 10

    AF-RLIO adaptively switches between LiDAR-inertial and radar-inertial odometry based on a feature-ratio degradation detector and uses chi-square GPS outlier weighting, showing lower APE in tunnels and smoke than the t...

  9. Self-Balancing, Memory Efficient, Dynamic Metric Space Data Maintenance, for Rapid Multi-Kernel Estimation

    cs.LG 2025-04 reject novelty 4.0 of 10

    A (K,alpha) dynamic octree is proposed for maintaining neighbor structure in evolving metric spaces, with claimed log-time updates and reported speedups in SVGD, KNN, RAG, and OT-Flow.

  10. SHIFT Planner: Speedy Hybrid Iterative Field and Segmented Trajectory Optimization with IKD-tree for Uniform Lightweight Coverage

    cs.RO 2024-12 reject novelty 4.0 of 10

    SHIFT combines semantic-aware speed control with incremental local replanning to make robot coverage more uniform in dynamic 3D environments.

  11. An Addendum to NeBula: Towards Extending TEAM CoSTAR's Solution to Larger Scale Environments

    cs.RO 2025-04 conditional novelty 3.0 of 10

    NeBula 2.0 integrates multi-robot SLAM, risk-aware planning, and communication-aware behaviors to enable heterogeneous robot teams to map multi-kilometer underground environments with sub-2-meter accuracy.

  12. A Survey on LiDAR-based Autonomous Aerial Vehicles

    cs.RO 2025-09 conditional novelty 2.0 of 10

    A structured survey of LiDAR-based autonomous UAVs, covering sensor hardware, perception, planning, control, open-source projects, and applications.

Pith tools