Evaluating Various Quality Factors for Splitting Nodes in Tree-Structured Spatial Indices

The massive increase of multi-dimensional (spatial) data collected, either in size or veracity, has demanded better spatial index techniques able to handle efficient storing and fast retrieval of spatial objects. No matter how big the data are, eventually it will reside on physical storage media arranged as a series of logical blocks with prefixed sizes resembling nodes in tree-structured spatial indices. Good node splitting strategy is essential since it affects; the final shape of the index, the overlap area between nodes, and the overall index performance. Better node splitting process results will be obtained if multiple splitting strategies (quality factors) were combined to govern the split decision, and it will eliminate the need for dynamic or static tree packing.