# A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree
## 1 Introduction  
Currently, the study of autonomous vehicles and robots is a research hotspot. With the development of computer technology and the increasing demand for digitalization, the 3-dimension (3D) model has captured increasing research attention for decades [1]. For example, the 2D map which is widely used in robots cannot support robots to complete complex tasks, such as scene understanding. The 3D map becomes more and more significant for a robot. The 3D data is collected by 3D LiDAR, RGB-D camera, etc., which run at very high frequency. It is inevitable that huge amounts of data will be generated. So, it is urgent to choose an effective organizing and management method for 3D data.  
The 3D coordinates \((x,y,z)\) of each point correspond to the geometry component of the Point Cloud, which may contain one or more additional components (attributes), such as color, reflectance, and normal vectors, etc. Point Cloud data is a typical structure of 3D data, which is the set of points with 3D coordinates. The 3D sensors are widely used in various applications, and the technology is relatively mature, while the data processing technology lags behind to some extent. Due to the massive data, disorder, irregularity, sparsity, high resolution, and lack of topological relations or texture information [2], the Point Cloud data processing is complex and challenging. Most feature analyses are based on the relationship between point and neighbors; therefore, Nearest Neighbor (\(NN\)) search is frequently conducted. The efficiency of query operation directly affects processing Point Cloud data [3]. Furthermore, the 3D coordinate is the primary form of 3D vector data, thebasis of 3D geometric modeling, and the object of operation and analysis on vector space. So, it is of great significance to efficiently organize the Point Cloud data.  
Currently, the hierarchical partition is usually used to subdivide Point Cloud data space, and the most commonly used data structures are Grid, octree [4], KD-tree [5] and R-tree [6]. Grid divides the data space equally into grids with a fixed resolution, disregarding whether points exist inside or not. So, it is easy to implement. Paper [7] adopts a hash-like structure for storing a multi-dimensional spatial data, and it has the potential to process Point Cloud data. Octree is a 3-dimension extension of Quad-tree [8] or an adaptive Grid structure, and is widely recognized as a promising representation of Point Cloud [9]. It can divide the data space rigidly (i.e., with a fixed target depth or leaf size) or adaptively [10]. If the Point Cloud data distributes uniformly, octree can achieve a better retrieval performance. Otherwise, the octree is unbalanced, such that it will be difficult to perform query or other operations effectively. Since the most frequent operation of Point Cloud data is \(NN\) searching during subsequent processing, it is important to design an efficient index structure to increase efficiency of spatial query [11]. For this reason, a hybrid spatial index method combining octree and R*-tree [12] to organize Point Cloud data is proposed.