A brand-new node-choosing algorithm in R-tree spatial index

摘要

Spatial index is one of the key techniques in the field of spatial database. This paper presents a brand-new node-choosing algorithm in the insertion procedure of R-tree spatial index, which is very different from the current algorithms. From the beginning of the leaf-node layer, firstly from bottom to top then inversely, the proper leaf-node is chosen, and this scheme can solve the problems caused by node overlapping. Meantime, the concept of Rtree_Cauchy is firstly put forward, and the sum of overlay, overlap and Rtree_Cauchy is introduced as selection criterion to guarantee that shape of node is average and avoid generating long-strip-shape nodes. A comparative performance analysis on the current and improved methods shows that not only the query performance but also the generation performance of the improved method is higher than the current methods such as R~*-tree.