An investigation of classification and comparison of R tree construction algorithms with A Set of R* and R+ trees

Abstract

Given the growth of the internet network and the importance of the quality of different services that must be provided to users by several networks, packet classification is receiving increasing attention as one of the main and sensitive requirements of the network. Such that for the most services provided by the network, the routers must perform the classification with high speed and low memory usage. Packet classification enables the routers to provide modern network services. The classification is performed geometrically in R-tree. The main theory of the spatial index which considered as the most important theory of inquiry is the calculation of proximity theory. The most famous index structure is called the R-tree. The main strategy for R-tree is to collect multidimensional spatial nodes with a minimum boundary rectangle (MBR) that is the smallest inner spatial node of the rectangle. After indexing, the optimization of retrieving information from a spatial database has great importance. Hence for more discussion, a new spatial index belonged to the R+ tree family called R++ tree is investigated in this paper which maintains the overlap of the nodes. The results show that the suggested R+ tree outperforms the R+ tree in domains of queries, KNN queries, and Top-k queries.