A performance comparison among the traditional R-trees, the Hilbert R-tree and the SR-tree

This work investigates the performance of several spatial access methods with respect to the distribution of the indexed spatial objects. Although having gathered storage and insertion costs as well this work focuses on some issues regarding query costs. The performance results have showed that the R⁺-tree was the best spatial index structure for the point queries and the enclosure range queries, whereas the R^*-trees have produced the best outcomes for the intersection and the containment range queries. The Hilbert R-tree and the SR-tree have generated low performance results for any investigated query type. However, additional performance tests have showed that a variation in both the size and the shape properties of the data rectangles provided competitive results for the Hilbert R-tree and the SR-tree, mainly for the intersection and the containment queries.