R-Tree Node-Splitting Algorithm Using Combined Quality Factors and Weights
Esam Al-Nsour, Azzam Sleit, Mohammad Alshraideh · 2017
In this work we introduce a new approach to calculate splitting quality factors using the distribution of objects inside overflown nodes. Finding most proper splits for overflown R-tree nodes leads to better performance, since it determines index final shape; its tree height, nodes count, and overlap percentage between nodes. A linear cost scan of overflown node's objects identifies the distribution of objects' locations in relative to its node's bounding rectangle, then using objects' locations to calculate the quality factors. Each factor value is normalized and is given a weight, and then all are combined to select the best axis to split the node along it.