K-d tree is a common multidimensional data structure, which can be used for range search, nearest neighbor search and other problems. However, in practical applications, we often need to query and modify dynamic data. At this time, the traditional k-d tree seems to be powerless. In order to solve this problem, researchers put forward the concept of Dynamic k-d tree. Different from the traditional k-d tree, the dynamic k-d tree can support insert, delete and modify operations, and can maintain a balanced state. Dynamic k-d tree can be used for various multidimensional data structure problems, such as range search, nearest neighbor search, etc. This paper will introduce the basic principle and implementation method of dynamic k-d tree.
1. Basic Principles
1.k-d tree
First, let’s review the traditional k-d tree. K-d tree is a binary search tree, which represents each node as a super rectangle, and divides the super rectangle into two sub regions according to some rules. Specifically, the construction process of k-d tree is as follows:
1. Select a dimension d and sort the dataset according to the value of the d-th dimension.
2. Select the median as the root node and divide the dataset into two subsets. The left subset contains all data below the median, while the right subset contains all data above the median.
3.Recursively perform steps 1 and 2 on the left and right subsets until each node contains only one data point
In the k-d tree, each node represents a super rectangle, which contains some data points. For any node, the hyperrectangles represented by its left and right subtrees do not intersect. Therefore, when searching, we can determine the search direction by comparing the position relationship between the query point and the hyper rectangle represented by the current node. For example, when building a k-d tree on a two-dimensional plane, each node represents a rectangular region. If the query point is in the lower left corner of the rectangular area represented by the current node, the search direction is the left subtree; If the query point is in the upper right corner, the search direction is the right subtree.
1.2Dynamic k-d tree
The traditional k-d tree can only deal with static data sets, that is, the data sets will not change. However, in practical applications, we often need to query and modify dynamic data. For example, in robot motion planning, the robot needs to constantly obtain the surrounding environment information and carry out path planning. At this time, the traditional k-d tree cannot meet the demand.
In order to solve this problem, researchers put forward the concept of Dynamic k-d tree. Different from the traditional k-d tree, the dynamic k-d tree can support insert, delete and modify operations, and can maintain a balanced state.
In a dynamic k-d tree, each node represents a hyper rectangular region, which contains some data points. Different from the traditional k-d tree, the nodes in the dynamic k-d tree can be inserted, deleted or modified. When a node is inserted, we need to rebuild the entire tree; When a node is deleted, we need to remove it from the tree and rebalance the entire tree; When a node is modified, we need to update the hyper rectangular region it represents and rebalance the entire tree.
2.ikd Tree Design and Implementation
ikd-Tree is a dynamic data structure based on k-d tree. It consists of a binary search tree, which stores a super rectangular region and a set of points on each node. A hyper rectangular region is the smallest hyper rectangular region determined by all the points represented by that node. Each node has a partition axis and partition value to divide its child nodes into two subsets. The basic structure of ikd-Tree includes nodes, segmentation planes, subtrees, and some incremental operations, including insertion, reinsertion, and deletion. In these operations, ikd-Tree uses a recursive algorithm to update nodes and maintains balance by rotating and reconstructing subtrees. In addition, this section also introduces how to perform dynamic rebalancing to avoid tree imbalance leading to a decrease in query efficiency. Finally, this section discusses how to use ikd-Tree for nearest point search. The attributes of tree nodes in ikd-Tree are given in the following table. Lines 2-4 are the public attributes of the standard k-d tree. The attributes left tson and rightson are pointers to its left and right child nodes, respectively. Point information (such as point coordinates, intensity) is stored in the point. Since a point corresponds to a single node on the k-d tree, we will use points and nodes interchangeably. Record the division axis in axis. Lines 5-7 are the new attributes designed for incremental updates detailed in Section III-C.
2.1Incremental updates and rebalancing
Figure 1 shows the update and re equilibration process of the incremental k-d tree. In this example, black points represent existing k-d tree nodes, and red triangles represent new points to be inserted. The blue cube represents the space that needs to be rebalanced (i.e. branches). After inserting a new point, ikd-Tree uses rotation and reconstruction of the subtree to maintain balance and move the blue cube to the correct position.
fig.1
Figure 1. Diagram of update and rebalance of incremental k-d tree, (a): existing k-d tree (black dot) and new point (red triangle) to be inserted, blue cube represents the space to be rebalanced (i.e. branch), (b): k-d tree after point insertion and tree rebalance, blue cube represents the space after rebalance, while most other trees remain unchanged.
2.2Box operation and downsampling
Box operations refer to dividing space into multiple boxes to search for the nearest point faster. In ikd-Tree, this is a method of inserting, deleting, or reinserting all points within a rectangular box aligned with the data axis. These rectangular boxes can be specified by the user or automatically calculated based on the dataset. Downsampling refers to reducing the amount of data while maintaining data distribution, thereby improving query efficiency.
fig.2
Figure 2, point cloud downsampling, (a) point cloud before downsampling, (b) point cloud after downsampling
2.3 Dynamic Rebalance
Ikd-Tree also supports dynamic rebalancing to avoid a decrease in query efficiency caused by imbalanced trees. Specifically, ikd-Tree uses partial reconstruction methods to rebalance the tree. When rebalancing is required, ikd Tree divides the tree into two parts and performs the reconstruction operation simultaneously in both threads. This method can minimize reconstruction time and improve overall efficiency.
Figure 3 Reconstruction of imbalanced subtree
3.Time and Space Complexity
This section introduces the analysis of the time complexity of insertion, deletion, query, and reconstruction operations by ikd-Tree. Finally, this section also discusses the spatial complexity of ikd-Tree and its performance in practical applications. Ikd Tree is an incremental data structure based on k-d tree, which can efficiently process point cloud data, path planning and other operations in robot applications. In ikd-Tree, each node contains a segmentation plane and two subtrees, with the left subtree containing points smaller than the segmentation plane value and the right subtree containing points greater than or equal to the segmentation plane value. Through recursive algorithms, binary search is performed on each node, and balance is maintained by rotating and reconstructing subtrees. In terms of insertion operations, this section points out that in the worst-case scenario, inserting a new point requires O (n) comparison operations (where n represents the number of nodes in the tree). This is because new points may be inserted into the left or right subtree of all nodes. However, in practical applications, due to the dynamic rebalancing method used by ikd-Tree to maintain balance and the support for downsampling and other functions to reduce data volume, the time complexity of the insertion operation is usually O (log n). In terms of deletion operations, this section points out that deleting a node requires O (log n) comparison operations. This is because ikd-Tree uses a recursive algorithm to find the nodes to be deleted, and maintains balance by rotating and rebuilding the subtree. However, in practical applications, due to ikd-Tree’s support for downsampling and other functions to reduce data volume, the time complexity of deletion operations is usually O (log n). In terms of query operations, this section points out that ikd-Tree’s query operations require O (log n) comparison operations. This is because binary search is performed on each node and left or right subtrees are selected for recursive search based on the value of the segmentation plane. Due to the dynamic rebalancing method used by ikd-Tree to maintain balance and the support for downsampling and other functions to reduce data volume, the time complexity of query operations is usually O (log n).
In terms of reconstruction operations, this section points out that ikd-Tree uses partial reconstruction methods to rebalance the tree. When rebalancing is required, ikd Tree divides the tree into two parts and performs the reconstruction operation simultaneously in both threads. This method can minimize reconstruction time and improve overall efficiency. Due to ikd-Tree’s support for dynamic rebalancing and partial reconstruction, the time complexity of reconstruction operations is usually O (log n).
In terms of spatial complexity, this section points out that ikd-Tree requires O (n) space to store all nodes and data points. Each node needs to store its segmentation plane, subtree information, and other metadata. However, in practical applications, ikd-Tree supports downsampling and other functions to reduce data volume, and can further reduce the required storage space through technologies such as compressed storage.
4.Experimental results and analysis
This section first introduces the testing environment and dataset, including the hardware and software configurations used, as well as the sources and characteristics of the test data. Then, this section discusses in detail the performance of ikd-Tree in different application scenarios and compares it with other data structures. These experiments are based on random incremental datasets and outdoor SLAM experiments based on LiDAR rangefinder. The efficiency of ikd-Tree has been fully validated in experiments on random incremental datasets. This experiment uses 1000 points as the initial dataset and gradually adds 1000 points for testing. Figure 4 (a) shows the running time comparison between ikd Tree and static k-d tree, where the x-axis represents the number of incremental updates and the y-axis represents the running time (in milliseconds). It can be seen that when the number of incremental updates is small, there is little difference in the running time between ikd Tree and static k-d tree. However, when the number of incremental updates reaches a certain number, ikd Tree is obviously better than the static k-d tree, and has better scalability. Figure 4 (b) shows the comparison of the nearest neighbor search time between ikd Tree and static k-d tree, where the x-axis represents the number of queries and the y-axis represents the running time (in milliseconds). It can be seen that when the number of queries is small, the query time difference between ikd Tree and static k-d tree is small. However, when the number of queries reaches a certain number, ikd Tree is obviously better than the static k-d tree, and has better scalability. Figure 4 (c) shows the comparison of operation count and total time consumption between ikd Tree and static k-d tree, where the x-axis represents the number of points and the y-axis represents the operation count and total time consumption. When the number of points reaches a certain amount, ikd Tree is obviously better than static k-d tree.
fig.4 The time performance coparison between an ikd-Tree and a static k-d tree
In LiDAR’s outdoor SLAM experiment, ikd Tree also demonstrated excellent performance. This experiment used a mobile robot and a LiDAR to construct a map by scanning the surrounding environment. Figure 5 shows the performance of ikd-Tree in this experiment, where the x-axis represents time in seconds and the y-axis represents running time in milliseconds. It can be seen that the running time of ikd-Tree remained at a relatively low level throughout the entire experimental process.
fig.5