LIO-HKDT: Fast and Accurate LiDAR-Inertial Odometry with Hash K-D Tree

Abstract

LiDAR-inertial odometry(LIO) has been widely applied in intelligent robotics and autonomous driving, providing high-precision and low-latency ego-motion estimation. However, the massive point clouds generated by LiDAR introduce intensive data processing demands, making k-nearest neighbor(KNN) search and map update a critical bottleneck that limits the real-time performance of the LIO system. This paper proposes a novel data structure, the hkd-Tree, which uses hashed voxel indices as keys and local k-d tree as values. It combines the localized search advantages of voxel-based methods with the efficient search capability of k-d tree, enabling fast KNN search and point cloud insertion. To further improve the performance of the hkd-Tree, we propose a voxel distribution mechanism and buffered update strategy, where each new point is assigned to neighboring voxels within the search radius and inserted into local k-d tree via parallel batch updates. We develop a LiDAR-inertial odometry system, LIO-HKDT, based on the proposed hkd-Tree. Extensive experiments demonstrate that the hkd-Tree enables highly efficient point cloud search and insertion. LIO-HKDT achieves comparable accuracy to state-of-the-art LIO systems while significantly improving runtime efficiency.