Improving the R*-tree with outlier handling techniques

ABSTRACT

The R*-tree, as a state-of-the-art spatial index, has already found its way into commercial systems like Oracle. In this paper, we aim at improving query performance of the R*-tree. We focus on five widely used spatial queries: range query, aggregation query, nearest neighbor query, skyline query, and join query. The idea is to store outlier objects in internal tree nodes. The new structure is named the R^Otree. Here an outlier is an object which is located far from other objects or has large extent (we consider both point objects and objects with extent). If such objects are stored at higher levels of the tree, the lower-level nodes have smaller minimum bounding rectangles and thus the index performs better. To support the dynamic nature of the index, several structural and algorithmic changes are needed. The paper discusses these changes. In particular, we show how to identify and handle the outlier objects during page overflow/underflow, using gain/loss metrics. Extensive experiments reveal that the R^Otree significantly outperforms the R*-tree for all the five queries.

REFERENCES

• 1: N. An, K. Kanth, and S. Ravada. Improving Performance with Bulk-Inserts in Oracle R-Trees. In VLDB, 2003.
• 2: 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]
• 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: 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]
• 5: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 6: Antonio Corral , Yannis Manolopoulos , Yannis Theodoridis , Michael Vassilakopoulos, Closest pair queries in spatial databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.189-200, May 15-18, 2000, Dallas, Texas, United States
• 7: 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]
• 8: 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
• 9: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 10: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations, Proceedings of the 23rd International Conference on Very Large Data Bases, p.396-405, August 25-29, 1997
• 11: IBM. IBM Informix Spatial DataBlade Module. http://www-3.ibm.com/software/data/informix/pubs/specsheets/SWSEC27152000D.pdf.
• 12: 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
• 13: 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]
• 14: Oracle. Oracle8 Spatial Cartridge. http://technet.oracle.com/prod-ucts/oracle8/info/sdods/xsdo7ds.htm.
• 15: Dimitris Papadias , Panos Kalnis , Jun Zhang , Yufei Tao, Efficient OLAP Operations in Spatial Data Warehouses, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.443-459, July 12-15, 2001
• 16: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, An optimal and progressive algorithm for skyline queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872814]
• 17: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 18: Y. Theodoridis. The R-tree-portal. http://www.rtreeportal.org, 2003.
• 19: 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]
• 20: Donghui Zhang , Tian Xia, A novel improvement to the R*-tree spatial index using gain/loss metrics, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032253]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
R*-tree, outlier