# A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree
## 3 Materials and Methods
### 3D R*-Tree  
R- tree, a hierarchical data structure, extends B-tree [29] from 1 to dimension to k-dimension space. Consequently, it is a highly balanced tree and a dynamic structure inherited from B-tree. It is a famous indexing method for multi-dimensional data for spatial query operation. Basic operations can be conducted conveniently, such as inserting, deleting, and querying. Each node in the tree stores the Minimum Bounding k-dimensional Rectangle (MBR) covering its child nodes rather than the actual data, thereby saving the memory space by 50% at least. However, R-tree ignores the overlaps between MBRs and results in increasing the time of querying. In classical R-tree, if two objects lay in two different nodes, it is impossible to merge them into one node, albeit they are near in spatial. Because it follows the principle of minimizing area, ignoring other factors such as overlap.  
By researching what factors affect the R-tree's performance, R*-tree [12] is proposed to minimize the rectangle area, overlaps, and margins of the rectangle. R*-tree makes the MBR of node approaching a square and greatly improves the performance. Generally, R*-tree is recognized as the most efficient spatial querying method [13], which is why we adopt 3D R*-tree.  
We hope 3D R-tree is a dynamic structure like R-tree, which is considered as a most promising spatial indexing method and has faster query efficiency than octree [30, 31]. As 2D R*-tree does, 3D R*-tree also aims at improving query efficiency based on 3D R-tree by minimizing the overlaps, volume of the Minimum Bounding Box (MBB). We hope that points closed in 3D space are in the same MBB. However, the overlap between MBBs becomes highly complex because the shape of 3D objects or distribution of 3D points will become more diverse. 3D R*-tree consists of intermediate nodes and leaf nodes. Unlike octree or kd-tree, nodes of the 3D R*-tree include node ID and MBB \((x_{min},y_{min},z_{min},x_{max},y_{max},z_{max})\).  
An example of 3D R*-tree [32] subdividing the Point Cloud data spatial is shown in Figure 3, the dataset is _table_scene_lms400._pcd_[33], a commonly used dataset. We can see that the overlap becomes more and more severe when the tree is deeper, despite the R*-tree adopting a series of rules to minimize the overlaps. In brief, although 3D R*-tree is faster in querying than octree or kd-tree, it is also tough to query when Point Cloud data becomes huge. This is why we design a hybrid structure based on octree and 3D R*-tree.  
In conclusion, among the index methods for Point Cloud management, octree is unbalanced in most cases. Kd-tree is too deep when managing large-scale Point Cloud data, although we did not describe the detail above. The 3D R*-tree will overlap each other when the tree becomes deep. The single indexing methods can hardly meet the requirement of managing large-scale Point Cloud data. So, many hybrid index methods are proposed in recent years. Such as combining 3D R*-tree and kd-tree [18], octree and 3D R*-tree [19], quad-tree and 3D R-tree [31], kd-tree and octree [11], octree and kd-tree [3, 34], quad-tree and octree [35], etc. The main idea is to improve the imbalance of tree and speed up the query operation. In this paper, a hybrid indexing method based on octree and 3D R*-tree is proposed for the same purpose.