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. This paper presents a solution to the above problem.
The proposed solution to this problem distributes rectangles as follows: (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.