This Article Full Text (OnlineFirst PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Scopus Google Scholar Articles by Al-Badarneh, A. F. Articles by Hmeidi, I. Social Bookmarking                         What's this?

A new enhancement to the R-tree node splitting

Jordan University of Science & Technology

^* To whom correspondence should be addressed. E-mail: amerb{at}just.edu.jo.

	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.

First published on July 17, 2009
Journal of Information Science 2009, doi:10.1177/0165551509340360


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?