Crisp Clustering Algorithm for 3D Geospatial Vector Data Quantization

In the next few years, 3D data is expected to be an intrinsic part of geospatial data. However, issues on 3D spatial data management are still in the research stage. One of the issues is performance deterioration during 3D data retrieval. Thus, a practical 3D index structure is required for efficient data constellation.

Due to its reputation and simplicity, R-Tree has been received increasing attention for 3D geospatial database management. However, the transition of its structure from 2D to 3D had caused a serious overlapping among nodes. Overlapping nodes also occur during splitting operation of the overflown node N of M + 1 entry.

Splitting operation is the most critical process of 3D R-Tree. The produced tree should satisfy the condition of minimal overlap and minimal volume coverage in addition with preserving a minimal tree height. Based on these concerns, in this paper, we proposed a crisp clustering algorithm for the construction of a 3D R-Tree.

Several datasets are tested using the proposed method and the percentage of the overlapping parallelepipeds and volume coverage are computed and compared with the original R-Tree and other practical approaches. The experiments demonstrated in this research substantiated that the proposed crisp clustering is capable to preserve minimal overlap, coverage and tree height, which is advantageous for 3D geospatial data implementations.

Another advantage of this approach is that the properties of this crisp clustering algorithm are analogous to the original R-Tree splitting procedure, which makes the implementation of this approach straightforward.