A revised r*-tree in comparison with related index structures

ABSTRACT

In this paper we present an improved redesign of the R*-tree that is entirely suitable for running within a DBMS. Most importantly, an insertion is guaranteed to be restricted to a single path because re-insertion could be abandoned. We re-engineered both, subtree choice and split algorithm, to be more robust against specific data distributions and insertion orders, as well as peculiarities often found in real multidimensional data sets. This comes along with a substantial reduction in CPU-time.

Our experimental setup covers a wide range of different artificial and real data sets. The experimental comparison shows that the search performance of our revised R*-tree is superior to that of its three most important competitors. In comparison to its predecessor, the original R*-tree, the creation of a tree is substantially faster, while the I/O cost required for processing queries is improved by more than 30% on average for two- and three-dimensional data. For higher dimensional data, particularly for real data sets, much larger improvements are achieved.

REFERENCES

• 1: Lars Arge , Mark de Berg , Herman J. Haverkort , Ke Yi, The Priority R-tree: a practically efficient and worst-case optimal R-tree, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007608]
• 2: Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
• 3: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 4: Bruno Becker , Paolo Giulio Franciosa , Stephan Gschwind , Thomas Ohler , Gerald Thiemt , Peter Widmayer, Enclosing Many Boxes by an Optimal Pair of Boxes, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.475-486, February 13-15, 1992
• 5: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 6: 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
• 7: Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997
• 8: Bureau of the Census: Tiger/Line Precensus Files: 1995 technical documentation, Bureau of the Census, Washington DC 1996.
• 9: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• 10: The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces, Proceedings of the 15th International Conference on Data Engineering, p.440, March 23-26, 1999
• 11: Kaushik Chakrabarti , Sharad Mehrotra, Efficient concurrency control in multidimensional access methods, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.25-36, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 12: http://www.mathematik.uni-marburg.de/~seeger/rrstar/, 2009.
• 13: Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182593]
• 14: Yván J. García , Mario A. Lopez , Scott T. Leutenegger, On Optimal Node Splitting for R-trees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.334-344, August 24-27, 1998
• 15: 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
• 16: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 17: Erik G. Hoel , Hanan Samet, Benchmarking Spatial Join Operations with Spatial Output, Proceedings of the 21th International Conference on Very Large Data Bases, p.606-618, September 11-15, 1995
• 18: IBM Informix R-tree Index, User's Guide, 2005. IBM Informix Dynamic Server v10 Information Center, Feb. 2009.
• 19: Ibrahim Kamel , Christos Faloutsos, Hilbert R-tree: An Improved R-tree using Fractals, Proceedings of the 20th International Conference on Very Large Data Bases, p.500-509, September 12-15, 1994
• 20: Marcel Kornacker , C. Mohan , Joseph M. Hellerstein, Concurrency and recovery in generalized search trees, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.62-72, May 11-15, 1997, Tucson, Arizona, United States
• 21: 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]
• 22: 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
• 23: Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States
• 24: Yannis Manolopoulos , Alexandros Nanopoulos , Apostolos N. Papadopoulos , Y. Theodoridis, R-Trees: Theory and Applications (Advanced Information and Knowledge Processing), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 25: MySQL 5.0 Reference Manual, http://downloads.mysql.com/docs/refman-5.0-en.a4.pdf, 2008.
• 26: W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, and G. Taubin. The QPIC project: Quering images by content using color, texture, and shape. Poc. of the SPIE Conference on Storage and Retrieval for Image and Video Databases, 2-3 February '93, San Jose, CA, pages 173--187, 1993.
• 27: The PostgreSQL Comprehensive Manual, http://www.postgresql.org/docs/manuals/).
• 28: Bernd-Uwe Pagel , Hans-Werner Six , Heinrich Toben , Peter Widmayer, Towards an analysis of range query performance in spatial data structures, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-221, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153878]
• 29: Bernd-Uwe Pagel , Hans-Werner Six , Mario Winter, Window query-optimal clustering of spatial objects, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.86-94, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212458]
• 30: Yasushi Sakurai , Masatoshi Yoshikawa , Shunsuke Uemura , Haruhiko Kojima, The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation, Proceedings of the 26th International Conference on Very Large Data Bases, p.516-526, September 10-14, 2000
• 31: UC Irvine KDD Archive, http://kdd.ics.uci.edu/, 2002.
• 32: J. Weinberger: SpatialWare Extends Microsoft SQL Server Capabilities. MapInfo Magazine 6(2), 2001.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
choosesubtree, hilbert-r-tree, index structures, multi-dimensional data, performance comparison, r-tree, revised r*-tree, rr*-tree, split