Abstract:
The performance of spatial queries depends mainly on the underlying index structure used to handle them.
R-tree, a well-known spatial index structure, suffers largely from high overlap and high coverage resulting
mainly from splitting the overflowed nodes. Assigning the remaining entries to the underflow node in order
to meet the R-tree minimum fill constraint (Remaining Entries problem) may induce high overlap or high
coverage. This is done without considering the geometric features of the remaining entries and this may cause
a very non-optimized expansion of that particular node. The proposed solution to this problem distributes
rectangles as follow: (1) Assign m entries to the first node, which are nearest to the first seed. (2) Assign other
m entries to the second node, which are nearest to the second seed. (3) Assign the remaining entries one by
one to the nearest seed. Several experiments on real data, as well as synthetic data, show that the proposed
splitting algorithm outperforms the efficient version of the original R-tree in terms of query performance