Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R*-tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R*-tree clearly outperforms the existing R-tree variants. Guttman's linear and quadratic R-tree and Greene's variant of the R-tree. This superiority of the R*-tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R*-tree is very attractive because of the following two reasons 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other R-trees.

REFERENCES

• Gre 89: Diane Greene, An Implementation and Performance Analysis of Spatial Data Access Methods, Proceedings of the Fifth International Conference on Data Engineering, p.606-615, February 06-10, 1989
• Gut 84: 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
• Hin 85: K Hlnrlchs 'The grid file system ~mplementatlon and case studies for appl~catxons', D~ssertat~on No 7734, Eldgen6sslsche Technlsche Hochschule (ETH), Zuench, 1985
• Knu 73: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• KSSS 89: H. -P. Kriegel , M. Schiwietz , R. Schneider , B. Seeger, Performance comparison of point and spatial access methods, Proceedings of the first symposium on Design and implementation of large spatial databases, p.89-114, February 1990, Santa Barbara, California, United States
• NHS 84: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• RL 85: Nick Roussopoulos , Daniel Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.17-31, May 1985, Austin, Texas, United States
• SK 88: Bernhard Seeger , Hans-Peter Kriegel, Techniques for Design and Implementation of Efficient Spatial Access Methods, Proceedings of the 14th International Conference on Very Large Data Bases, p.360-371, August 29-September 01, 1988
• SK 90: B Seeger, HP Krlegel 'The design and implementation of the buddy tree', Computer Science Techmcal Report 3/90, Umverslty of Bremen, submitted for pubhcatlon, 1990

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Algorithms, Performance