The R-tree, one of the most popular access methods for rectangles, IS based on the heurlstlc optlmlzatlon of the area of the enclosmg rectangle m each mner node By running numerous experiments m a standardized testbed under highly varying data, queries and operations, we were able to design the R*-tree which mcorporates a combined optlmlzatlon of area, margin and overlap of each enclosmg rectangle m the directory Using our standardized testbed m an exhaustive performance comparison, It turned out that the R*-tree clearly outperforms the exlstmg R-tree varmnts Guttman's linear and quadratic R-tree and Greene's variant of the R-tree This superlorlty of the R*-tree holds for different types of queries and operations, such as map overlay. for both rectangles and multldlmenslonal points m all experiments From a practical pomt of view the R*-tree 1s very attractive because of the followmg two reasons 1 It effrclently supports pomt and spattal data at the same time and 2 Its lmplementatlon cost 1s only slightly higher than that of other R-trees l.Introduction In this paper we will consider spatial access methods (SAMs) which are based on the approxlmatlon of a complex spatial object by the mmlmum boundmg rectangle with the sides of the rectangle parallel to the axes of the data space yIp---+ This work was supported by grant no Kr 670/4-3 from the Deutsche Forschun&iememschaft (German Research Society) and by the Mmlstry of Environmental and Urban Planning of Bremen Pemxss~on to copy wthout fee all or part of this maternal IS granted prowded that the copses are not made or dlstnbuted for dwzct commeraal advantage, the ACM copy&t notice and the title of the pubbcatlon and its date appear, and notw IS gwn that cqymg II by pemuwon of the Assoaatlon for Computmg Machmq To copy othemw, or to repubbsh requ,res a fee and/or speoflc pemllsslon 0 1990 ACM 089791365 5/!90/0@35/0322 $150 The most important property of this simple approxlmatlon 1s that a complex object 1s represented by a limited number of bytes Although a lot of mformatlon 1s lost, mnumum bounding rectangles of spatial oblects preserve the most essential geometric properties of the object, 1 e the location of the oblect and the extension of the object in each axis In [SK 881 we showed that known SAMs organlzmg (mmlmum bounding) rectangles are based on an underlymg point access method (PAM) using one of the followmg three techniques cllpplng, transformation and overlapping regions The most popular SAM for storing rectangles 1s the Rtree [Gut 841 Followmg our classlflcatlon, the R-tree 1s based on the PAM B+-tree [Knu 731 usmg the technique over-lapping regions Thus the R-tree can be easily implemented which considerably contributes to Its popularity The R-tree 1s based on a heurlstlc optlmlzatlon The optlmlzatton crlterlon which It persues, 1s to mmlmlze the area of each enclosing rectangle m the mner nodes This crlterlon IS taken for granted and not shown to be the best possible Questions arise such as Why not mnumlze the margin or the overlap of such mlnlmum bounding rectangles Why not optimize storage utlllzatlon? Why not optunlze all of these criteria at the same hme? Could these criteria mteract in a negative way? Only an engineering approach will help to find the best possible combmatlon of optimization criteria Necessary condltlon for such an engmeermg approach 1s the avallablhty of a standardized testbed which allows us to run large volumes of experiments with highly varying data, queries and operations We have implemented such a standardized testbed and used It for performance comparisons parucularly of pomt access methods [KSSS 891 As the result of our research we designed a new R-tree varmnt, the R*-tree, which outperforms the known R-tree variants under all experiments For many reallstlc profiles of data and operations the gam m performance 1s quite considerable Additionally to the usual point query, 322 rectangle mtersectton and rectangle enclosure query, we have analyzed our new R*-tree for the map overlay operation. also called spatial lout. which 1s one of the most rmportant operatrons m geographic and envrronmental database systems This paper is organized as follows In sectron 2, we tntroduce the prrncrples of R-trees rncludrng their optimizatron criteria In section 3 we present the existing R-tree variants of Guttman and Greene Section 4 describes rn detail the design our new R*-tree The results of the comparrsons of the R*-tree wrth the other R-tree varmnts are reported m section 5 Section 6 concludes the paper 2. Principles of R-trees and possible optimization criteria An R-tree 1s a B+-tree like structure which stores multrdrmensional rectangles as complete ObJects without clipping them or transformmg them to higher drmensronal points before A non-leaf node contarns entries of the form (cp, Rectangle) where cp 1s the address of a child node m the R-tree and Rectangle 1s the mnumum boundmg rectangle of all rectangles which are entries m that child node A leaf node contams entries of the form (Old, Rectangle) where Old refers to a record m the database, describing a spatial oblect and Rectangle 1s the enclosrng rectangle of that spatial oblect Leaf nodes containing entries of the form (datuob.tect, Rectangle) are also possrble This wrll not affect the basic structure of the R-tree In the followmg we wrll not consider such leaf nodes Let M be the maximum number of entries that will fit m one node and let m be a parameter specrfymg the mrmmum number of entries m a node (2 5 m < M/2) An R-tree satisfies the following properties l The root has at least two children unless rt 1s a leaf l Every non-leaf node has between m and M children unless it is the root l Every leaf node contans between m and M entries unless It 1s the root l All leaves appear on the same level An R-tree (R*-tree) 1s completely dynamrc, msertrons and deletions can be intermixed with queries and no perrodrc global reorgamzatron 1s required Obvrously, the structure must allow overlappmg drrectory rectangles Thus rt cannot guarantee that only one search path 1s requued for an exact match query For further mformatron we refer to [Gut841 We wrll show m this paper that the overlappmg-regronstechruque does not rmply bad average retrieval performance Here and rn the followmg, we use the term directory rectangle, which 1s geometrrcally the minrmum bounding rectangle of the underlymg rectangles The main problem rn R-trees 1s the followrng For an arbitrary set of rectangles, dynamrcally burld up bounding boxes from subsets of between m and M rectangles, m a way that arbitrary retrieval operatrons with query rectangles of arbitrary srze are supported effrcrently The known parameters of good retrieval performance affect each other m a very complex way, such that rt 1s rmposstble to optrmlze one of them without influencing other parameters whtch may cause a deterroratron of the overall performance Moreover, smce the data rectangles may have very different size and shape and the drrectory rectangles grow and shrmk dynamically, the success of methods which wrll opttmrze one parameter 1s very uncertam Thus a heurrstrc approach IS applied, whrch is based on many different experiments carried out m a systematrc framework In this section some of the parameters which are essential for the retrieval performance are considered Furthermore, tnterdependencres between different parameters and optnnrzatron criteria are analyzed (01) The area covered by a drrectory rectangle should be mtnrmrzed, 1 e the area covered by the boundmg rectangle but not covered by the enclosed rectangles, the dead space, should be mmlmrzed Thus will Improve performance smce decrsrons which paths have to be traversed, can be taken on higher levels (02) The overlap between drrectory rectangles should be mwmrzed Thts also decreases the number of paths to be traversed (03) The margrn of a dwectory rectangle should be mlnrmrzed Here the margin 1s the sum of the lengths of the edges of a rectangle Assummg fixed area, the oblect wnh the smallest margrn IS the square Thus mmtmrzmg the margin mstead of the area, the dvectory rectangles wrll be shaped more quadratrc Essentrally queries with large quadratic query rectangles will profit from this optimizatron More important. mmrmrzatlon of the margm wrll basrcally improve the structure Since quadratic objects can be packed easier, the bounding boxes of a level will build smaller directory rectangles m the level above Thus clustermg rectangles into bounding boxes wrth only little variance of the lengths of the edges wrll reduce the area of dtrectory rectangles (04) Storage utlltzatron should be optlmrzed Higher storage utrhzatron will generally reduce the query cost as the height of the tree wrll be kept low Evidently. query types with large query rectangles are influenced more smce the concentratron of rectangles m several nodes wrll have a stronger effect rf the number of found keys IS hrgh Keepmg the area and overlap of a directory rectangle small, requires more freedom m the number of rectangles stored m one node Thus mmrmrzmg these parameters will be paid with lower storage utrlrzatton. Moreover, when applymg (01) or (02) more freedom rn choosrng the shape 1s necessary Thus rectangles wrll be less quadratic Wrth (01) the overlap between directory rectangles may be affected m a postttve way srnce the coverrng of the data space 1s reduced As for every geometrrc optrmrzatron, muumrzmg the margins wrll also lead to reduced storage uttltzatton However, smce more quadratrc directory rectangles support 323 packing better, It will be easier to maintain high storage utlllzatlon Obviously, the performance for queries with sufflclently large query rectangles will be affected more by the storage utlllzatlon than by the parameters of (Ol)- (03) 3. R-tree Variants The R-tree 1s a dynamic structure Thus all approaches of optlmlzlng the retrieval performance have to be applied during the msertlon of a new data rectangle The insertion algorithm calls two more algorithms m which the crucial declslons for good retrieval performance are made The first IS the algorithm ChooseSubtree Beglnnmg in the root, descending to a leaf, it finds on every level the most suitable subtree to accomodate the new entry The second 1s the algorithm Split It 1s called, If ChooseSubtree ends m a node filled with the maximum number of entries M Split should distribute M+l rectangles mto two nodes m the most appropriate manner In the followmg, the ChooseSubtree-and Split-algorithms, suggested In available R-tree variants are analyzed and dlscussed We will first consider the orlgmal R-tree as proposed by Guttman m [Gut 841 Algorithm ChooseSubtree CSl Set N to be the root CS2 If N 1s a leaf, return N else Choose the entry m N whose rectangle needs least area enlargement to include the new data Resolve ties by choosmg the entry with the rectangle of smallest area end CS3 Set N to be the chlldnode pointed to by the chlldpomter of the chosen entry an repeat from CS2 Obviously, the method of optlmlzatlon 1s to mnumlze the area covered by a directory rectangle, 1 e (01) This may also reduce the overlap and the cpu cost will be relatively low Guttman discusses split-algorithms with exponential, quadratic and linear cost with respect to the number of entries of a node All of them are deslgned to mmlmlze the area, covered by the two rectangles resultmg from the split The exponential split finds the area with the global mmlmum, but the cpu cost 1s too high The others try to fmd approxlmatlons In his experiments, Guttman obtains nearly the same retrieval performance for the linear as for the quadratic version We implemented the R-tree m both variants However m our tests with different dlstrlbutlons, different overlap, variable numbers of data-entries and different combmatlons of M and m, the quadratic R-tree yielded much better performance than the linear version (see also section 5) Thus we will only discuss the quadratic algorithm m detail The algorithm PickSeeds fmds the two rectangles which would waste the largest area put m one group In this sense the two rectangles are the most distant ones It 1s important to mention that the seeds will tend to be small too, If the rectangles to be distributed are of very different size (and) or the overlap between them 1s high The algorithm DlstrlbuteEntry assigns the remaining entries by the crlterlon of mnumum area P&Next chooses the entry with the best area-goodness-value m every sltuatlon If this algorithm starts with small seeds, problems may occur If m d-l of the d axes a far away rectangle has nearly the same coordinates as one of the seeds, It will be distributed first Indeed, the area and the area enlargement of the created needle-like bounding rectangle will be very small, but the distance 1s very large This may nutlate a very bad split Moreover. the algorithm tends to prefer the bounding rectangle, created from the first assignment of a rectangle to one seed Smce It was enlarged, It will be larger than others Thus It needs less area enlargement to mclude the next entry, It will be enlarged again. and so on Another problem is, that If one group has reached the maximum number of entries M-m+l, all remaining entries are assigned to the other group without consldermg geometric properties Figure 1 (see section 4 3) gives an example showing all 324 these problems The result 1s either a split with much overlap (fig lc) or a split with uneven dlstrtbutlon of the entries reducing the storage utlhzatlon (fig lb) We tested the quadratic split of our R-tree lmplementatlon varying the mmlmum number of entries m = 20%, 30%, 35% ,40% and 45% relatively to M and obtained the best retrieval performance with m set to 40% On the occasion of comparmg the R-tree with other structures storing rectangles, Greene proposed the followmg alternative split-algorithm [Gre 891 To determine the appropriate path to insert a new entry she uses Guttman's original ChooseSubtree-algorithm Greene's-Split [Divide a set of M+l entries mto two groups] GSI Invoke ChooseAxls to determme the axis perpendicular to which the split 1s to be performed GS2 Invoke Distribute Algorithm ChooseAxis CA1 Invoke PickSeeds (see p 5) to find the two most distant rectangles of the current node CA2 For each axis record the separation of the two seeds CA3 Normalize the separations by dlvldmg them by the length of the nodes enclosing rectangle along the appropriate axis CA4 Return the axis with the greatest normalized separation Algorithm Distribute Dl Sort the entries by the low value of then rectangles along the chosen axis D2 Assign the first (M+l) dlv 2 entries to one group, the last (M+l) dlv 2 entries to the other D3 If M+l 1s odd, then assign the remaining entry to the group whose enclosmg rectangle will be increased least by its addition Almost the only geometric crlterlon used m Greene's split algorithm 1s the choice of the split axis Although choostng a suitable split axis 1s Important, our mvestlgatlons show that more geometric optimization criteria have to be applied to considerably improve the retrieval performance of the R-tree In spite of a well clustermg, m some sltuatlons Greene's split method cannot fmd the "nght" axis and thus a very bad split may result Figure 2b (see p 12) depicts such a sltuatlon 4. The R*-tree 4.1 Algorithm ChooseSubtree To solve the problem of choosmg an appropriate insertion path, previous R-tree versions take only the area parameter into conslderatlon In our mvestlgatlons, we tested the parameters area, margin and overlap m different combmatlons, where the overlap of an entry 1s defined as follows Let&, ,Ep be the entries m the current node Then P overlap = c alea(E;,Redangle n E,Rtiangle) , 1s k $ p 1=1,1#k The version W&I the best retrieval performance 1s described m the followmg algorithm For choosmg the best non-leaf node, alternatlve methods did not outperform Guttman's original algorithm For the leaf nodes, mmlmlzmg the overlap performed slightly better In this version, the cpu cost of determmmg the overlap 1s quadrant 111 the number of entries, because for each entry the overlap with all other entries of the node has to be calculated However, for large node sizes we can reduce the number of entries for which the calculation has to be done, smce for very distant rectangles the probabllltty to yield the mmlmum overlap 1s very small Thus, m order to reduce the cpu cost, this part of the algorithm might be modlfled as follows [determme the nearly mmnnum overlap cost] Sort the rectangles m N m mcreasmg order of then area enlargement needed to mclude the new data rectangle Let A be the group of the first p entrles From the entries m A, consldermg all entries m N, choose the entry whose rectangle needs least overlap enlargement Resolve ties as described above For two dlmenslons we found that with p set to 32 there 1s nearly no reduction of retrieval performance to state For more than two dlmenslons further tests have to be done Nevertheless the cpu cost remains higher than the original version of ChooseSubtree. but the number of disc accesses 325 1s reduced for the exact match query precedmg each msertlon and 1s reduced for the ChooseSubtree algortthm Itself The tests showed that the ChooseSubtree optlmlzatlon improves the retrieval performance partlculary m the followmg sltuatlon Queries wrth small query rectangles on datafiles wrth non-unrformly dlstrlbuted small rectangles or points In the other cases the performance of Guttman's algorithm was similar to this one Thus principally an improvement of robustness can be stated 4 2 Split of the R*-tree The R*-tree uses the followmg method to fmd good sphts Along each axis, the entries are first sorted by the lower value, then sorted by the upper value of then rectangles For each sort M-2m+2 dlstrlbutlons of the M+l entrles mto two groups are determmed. where the k-th dlstrlbutlon (k = 1, ,(M-2m+2)) 1s described as follows The first group contains the first (m-l)+k entrles, the second group contams the remaining entrles For each dlstrlbutlon goodness values are determined Depending on these goodness values the final dlstrlbutlon of the entries IS determined Three different goodness values and different approaches of using them in different combmatlons are tested experlmentally (1) Along the chosen split axIs, choose the dlstrlbutlon with the mmunum overlap-value Resolve ties by choosmg the dlstrlbutlon with mmunum area-value The split algorithm 1s tested with m = 20%, 302, 40% and 45% of the maximum number of entrles M As ex-perunents with several values of M have shown, m = 40% yields the best performance Additionally, we varied m over the life cycle of one and the same R*-tree m order to correlate the storage utlllzatlon with geometric paremeters However, even the followmg method did result m worse retrieval performance Compute a split usmg ml = 30% of M, then compute a split using m2 =40% If spllt(m2)ylelds overlap and spllt(ml) does not, take spllt(m,), otherwlse take vllt(q) Concernmg the cost of the split algorithm of the R*-tree we will mention the following facts For each axis (dlmenslon) the entries have to be sorted two times which requires O(M log(M)) tune As an experlmental cost analysis has shown, thrs needs about half of the cost of the split The remammg split cost 1s spent as follows For each axls the margm of 2*(2*(M-2m+2)) rectangles and the overlap of 2*(M-2m+2) dlstnbunons have to be calculated 4 3 Forced Relnsert Both, R-tree and R*-tree are nondetermmlstlc m allocatmg the entrles onto the nodes 1 e different sequences of msertlons will build up different trees For this reason the R-tree suffers from its old entrees Data rectangles inserted durmg the early growth of the structure may have introduced directory rectangles, which are not sultable to guarantee a good retrieval performance m the current situation A very local reorganlzatton of the directory rectangles 1s performend during a split But this 1s rather poor and therefore it 1s desirable to have a more powerful and less local mstrument to reorgamze the structure The discussed problem would be maintamed or even worsened, If underfilled nodes, resultmg from deletion of records would be merged under the old parent Thus the known approach of treatmg underfilled nodes 111 an R-tree 1s to delete the node and to remsert the orphaned entrles m the correspondmg level [Gut 841 This way the ChooseSubtree algorithm has a new chance of distributing entries mto different nodes Smce it was to be expected, that the deletion and reinsertion of old data rectangles would Improve the retrieval performance, we made the followmg simple experiment with the linear R-tree Insert 20000 umformly dlstrlbuted rectangles Delete the fast 10000 rectangles and insert them agaln The result was a performance improvement of 20% up to 50%(l) dependmg on the types of the queries Therefore to delete randomly half of the data and then to Insert It agam seems to be a very simple way of tuning existing R-tree datafiles But this 1s a stattc sltuahon. and for nearly static datafiles the pack algorithm [RL 851 1s a more sophlstlcated approach To achieve dynanuc reorgamzatlons, the R*-tree forces entries to be remserted during the msertlon routme The 326 following algorithm 1s based on the ability of tne insert routme to msert entries on every level of the tree as already required by the deletion algorithm [Gut 841 Except for the overflow treatment, It 1s the same as described orlgmally by Guttman and therefore It 1s only sketched here  If a new data rectangle 1s Inserted, each first overflow treatment on each level will be a reinsertion of p entries This may cause a split in the node which caused the overflow if all entrles are reinserted m the same location Otherwise splits may occur in one or more other nodes, but m many sltuattons sphts are completely prevented The parameter p can be varied mdependently for leaf nodes and non-leaf nodes as part of performance tunmg, and different values were tested experimentally The experiments have shown that p = 30% of M for leaf nodes as well as for nonleaf nodes yields the best performance Furthermore, for all data files and query files close remsert outperforms far remsert Close reinsert prefers the node which mcluded the entries oerore. ana tnis 1s mlenueu, DeCdube 1~s enclosmg rectangle was reduced m size Thus this node has lower probablllty to be selected by ChooseSubtree agam Summarizmg. we can say l
The existing multidimensional data index is mainly divided into: points division index such as R-tree, R+-tree and R*-tree REF .
The R*-tree: an efficient and robust access method for points and rectangles
SIGMOD '90
Computer Science