Multi-Dimensional Indexing Structure for PointCloud Data

Muti-Dimensional data is of importance in many applications such as Geography Information System, Computer Aided Design, Medicine and so on. As one of multi-dimensional data, PointCloud is slightly different from the others. Many indexing structures can be used to organize multi-dimensional data, and a few of them could be used to manage PointCloud data. Several multi-dimensional data can be treated separately on each dimension. For example, the item of product (producer, date, price, location, …) always performs two major types of queries: similarity queries and range queries. So, indexing structure, such as B-tree, could be built on each attribute. PointCloud data is the discrete representation of geometry. To mine the geometry information hidden behind the Cartesian coordinates (x,y,z), k-nearest neighbor (k-NN) query is frequently performed. So, the three attributes must be treated together instead of separately. The most widely used data structure for PointCloud data are kd-tree and octree. It is well known that R-tree and R
^*
-tree are faster than kd-tree and octree in k-NN searching. In this paper, R-tree and R
^*
-tree are introduced and compared with kd-tree and octree to explore the potential of R-tree processing PointCloud data.