Towards Scalable Point-Cloud KNN Search: Efficient KD-Tree Construction via Sampled Median-of-Medians

Jiayi Xie

doi:10.54097/31yfxc57

Authors

Jiayi Xie School of Automation, Nanjing University of Science and Technology, Nanjing, China

DOI:

https://doi.org/10.54097/31yfxc57

Keywords:

autonomous driving, K-nearest neighbor search, KD-Tree, Median of Medians.

Abstract

Autonomous driving applications in intelligent transportation, unmanned delivery and high-definition map navigation all require efficient spatial data processing for perception and localisation. Point cloud registration aligns scans obtained at different times or from different positions by repeatedly finding neighbouring points to establish correspondences. This operation is generally carried out by K-nearest neighbour (KNN) queries. KD-Tree is a general-purpose spatial index for KNN search. At the same time, each internal node selects a splitting axis and recursively divides its points at the median coordinate along that axis. The former way of sorting finds the median by arranging all the coordinates along the chosen axis. Multiple Sorts increase construction costs due to larger point clouds and deeper recursion. We propose MM-KDTree to reduce the cost. At each non-leaf node, we systematically sample 5% of the coordinates along the selected axis without replacement, compute the sample median using Median of Medians (MoM), and use it to partition the complete point set at that node. The recursive construction procedure and the exact KNN query rules are unchanged. Experiments show that MM-KDTree reduces construction time by 89.10% - 92.36% compared with a sorting-based KD-Tree and maintains the same exact top-10 results. Mean query latency is still in the same order of magnitude. Based on the above results, selecting split values from samples can reduce the cost of index construction while keeping the query accuracy.

References

[1] P. J. Besl and N. D. McKay, “A Method for Registration of 3-D Shapes,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14, no. 2, pp. 239–256, 1992.

[2] J. L. Bentley, “Multidimensional Binary Search Trees Used for Associative Searching,” Communications of the ACM, vol. 18, no. 9, pp. 509–517, 1975.

[3] M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan, “Time Bounds for Selection,” Journal of Computer and System Sciences, vol. 7, no. 4, pp. 448–461, 1973.

[4] A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,” in Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, pp. 47–57, 1984.

[5] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, “The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles,” in Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, pp. 322–331, 1990.

[6] S. T. Leutenegger, M. A. Lopez, and J. Edgington, “STR: A Simple and Efficient Algorithm for R-Tree Packing,” in Proceedings of the 13th International Conference on Data Engineering, pp. 497–506, 1997.

[7] T. Gu, K. Feng, G. Cong, C. Long, Z. Wang, and S. Wang, “The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data,” Proceedings of the ACM on Management of Data, vol. 1, no. 1, Article 63, pp. 1–26, 2023.

[8] J. H. Friedman, J. L. Bentley, and R. A. Finkel, “An Algorithm for Finding Best Matches in Logarithmic Expected Time,” ACM Transactions on Mathematical Software, vol. 3, no. 3, pp. 209–226, 1977.

[9] S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu, “An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions,” Journal of the ACM, vol. 45, no. 6, pp. 891–923, 1998.

[10] F. Groh, L. Ruppert, P. Wieschollek, and H. P. A. Lensch, “GGNN: Graph-Based GPU Nearest Neighbor Search,” IEEE Transactions on Big Data, vol. 9, no. 1, pp. 267–279, 2023, doi: 10.1109/TBDATA.2022.3161156.

[11] H. Ootomo, A. Naruse, C. Nolet, R. Wang, T. Feher, and Y. Wang, “CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 4236–4247, 2024, doi: 10.1109/ICDE60146.2024.00323.

[12] K. Zhou, Q. Hou, R. Wang, and B. Guo, “Real-Time KD-Tree Construction on Graphics Hardware,” ACM Transactions on Graphics, vol. 27, no. 5, Article 126, 2008.

[13] C. J. Ogayar-Anguita, A. López-Ruiz, A. J. Rueda-Ruiz, and R. J. Segura-Sánchez, “Nested Spatial Data Structures for Optimal Indexing of LiDAR Data,” ISPRS Journal of Photogrammetry and Remote Sensing, vol. 195, pp. 287–297, 2023, doi: 10.1016/j.isprsjprs.2022.11.018.

[14] F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “ParallelNN: A Parallel Octree-Based Nearest Neighbor Search Accelerator for 3D Point Clouds,” in 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pp. 403–414, 2023, doi: 10.1109/HPCA56546.2023.10070940.

[15] M. Han, L. Wang, L. Xiao, H. Zhang, T. Cai, J. Xu, Y. Wu, C. Zhang, and X. Xu, “BitNN: A Bit-Serial Accelerator for K-Nearest Neighbor Search in Point Clouds,” in Proceedings of the 51st Annual International Symposium on Computer Architecture (ISCA), pp. 1278–1292, 2024.

[16] Q. Chang, W. Wang, and J. Miyazaki, “Accelerating Nearest Neighbor Search in 3D Point Cloud Registration on GPUs,” ACM Transactions on Architecture and Code Optimization, vol. 22, no. 1, Article 43, pp. 1–24, 2025, doi: 10.1145/3716875.

[17] D. Dor and U. Zwick, “Selecting the Median,” SIAM Journal on Computing, vol. 28, no. 5, pp. 1722–1758, 1999.

[18] A. Alexandrescu, “Fast Deterministic Selection,” in Proceedings of the 16th International Symposium on Experimental Algorithms (SEA), Leibniz International Proceedings in Informatics, vol. 75, Article 24, pp. 24:1–24:19, 2017.

[19] S. M. Omohundro, Five Balltree Construction Algorithms, Technical Report TR-89-063, International Computer Science Institute, 1989.

[20] Y. Cai, W. Xu, and F. Zhang, “ikd-Tree: An Incremental K-D Tree for Robotic Applications,” arXiv:2102.10808, 2021.

[21] A. Geiger, P. Lenz, and R. Urtasun, “Are We Ready for Autonomous Driving? The KITTI Vision Benchmark Suite,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3354–3361, 2012.

[22] H. Caesar et al., “nuScenes: A Multimodal Dataset for Autonomous Driving,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11618–11628, 2020.