A novel improvement to the R*-tree spatial index using gain/loss metrics

ABSTRACT

The R*-tree is a state-of-the-art spatial index structure. It has already found its way into commercial systems. The most important improvement of the R*-tree over the original R-tree is that it utilizes forced reinsertion. That is, if a disk page overflows, some objects are removed from the page and reinserted into the index. The goals are: (a) to reduce the MBR area; and (b) to keep the shape of the MBR close to a square. However, no existing work consists of a unified metric which can be used to balance the two criteria. For example, if there are two methods to remove objects from a rectangle, and one results in a rectangle with smaller area, while the other results in a square with slightly larger area, which method shall we choose? The R*-tree algorithm selects objects whose distances to the center of the page's MBR are the largest. However, this is not optimal. In this paper, we formally define the <i>quality</i> of a rectangle and the <i>gain</i> to shrink a rectangle. Then we provide algorithms to shrink the MBRs with the goal to maximize the gain. The algorithms are experimentally compared with the R*-tree's reinsertion algorithm. Furthermore, as the opposite of <i>gain</i>, we define the <i>loss</i> of expanding a rectangle. While inserting an object into the R*-tree, we need to choose a sub-tree to put the object in. With the new metric, we can choose the sub-tree with the least loss. Finally, we integrate the new algorithms into the R*-tree.

REFERENCES

• 1: R-tree-portal. http://www.rtreeportal.org/.
• 2: N. An, K. Kanth, and S. Ravada. Improving Performance with Bulk-Inserts in Oracle R-Trees. In Proceedings of International Conference on Very Large Data Bases (VLDB), 2003.
• 3: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 4: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 5: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 6: K. V. R. Kanth , D. Agrawal , A. K. Singh , A. El Abbadi, Indexing non-uniform spatial data, Proceedings of the 1997 International Symposium on Database Engineering & Applications, p.289, August 24-27, 1997
• 7: Ravi Kanth V Kothuri , Siva Ravada , Daniel Abugov, Quadtree and R-tree indexes in oracle spatial: a comparison using GIS data, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564755]
• 8: K. V. Ravi Kanth , Siva Ravada , Jayant Sharma , Jay Banerjee, Indexing medium-dimensionality data in Oracle, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.521-522, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 9: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Measurement, Performance

Keywords:
R*-tree, gain, quality, reinsertion