The priority R-tree: A practically efficient and worst-case optimal R-tree

ABSTRACT

We present the priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query using O((N/B)^1−1/d+T/B) I/Os, where N is the number of d-dimensional (hyper-) rectangles stored in the R-tree, B is the disk block size, and T is the output size. This is provably asymptotically optimal and significantly better than other R-tree variants, where a query may visit all N/B leaves in the tree even when T = 0. We also present an extensive experimental study of the practical performance of the PR-tree using both real-life and synthetic data. This study shows that the PR-tree performs similarly to the best-known R-tree variants on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.

REFERENCES

• 1: Agarwal, P. K., de Berg, M., Gudmundsson, J., Hammar, M., and Haverkort, H. J. 2002. Box-Trees and R-trees with near-optimal query time. Discr. Comput. Geom. 28, 3, 291--312.
• 2: Pankaj K. Agarwal , Lars Arge , Octavian Procopiuc , Jeffrey Scott Vitter, A Framework for Index Bulk Loading and Dynamization, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.115-127, July 08-12, 2001
• 3: Lars Arge , Jan Vahrenhold, I/O-efficient dynamic planar point location, Computational Geometry: Theory and Applications, v.29 n.2, p.147-162, October 2004 [doi>10.1016/j.comgeo.2003.04.001]
• 4: Arge, L., Hinrichs, K. H., Vahrenhold, J., and Vitter, J. S. 2002a. Efficient bulk operations on dynamic R-trees. Algorithmica 33, 1, 104--128.
• 5: Lars Arge , Octavian Procopiuc , Jeffrey Scott Vitter, Implementing I/O-efficient Data Structures Using TPIE, Proceedings of the 10th Annual European Symposium on Algorithms, p.88-100, September 17-21, 2002
• 6: Bayer, R., and McCreight, E. 1972. Organization and maintenance of large ordered indexes. Acta Inf. 1, 173--189.
• 7: 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
• 8: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegel, Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.216-230, March 23-27, 1998
• 9: Bozanis, P., Nanopoulos, A., and Manolopoulos, Y. 2003. LR-Tree: A logarithmic decomposable spatial index method. The Comput. J. 46, 3, 319--331.
• 10: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 11: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 12: David J. DeWitt , Navin Kabra , Jun Luo , Jignesh M. Patel , Jie-Bing Yu, Client-Server Paradise, Proceedings of the 20th International Conference on Very Large Data Bases, p.558-569, September 12-15, 1994
• 13: 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]
• 14: Yván J. García R , Mario A. López , Scott T. Leutenegger, A greedy algorithm for bulk loading R-trees, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.163-164, November 02-07, 1998, Washington, D.C., United States [doi>10.1145/288692.288723]
• 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: Herman J. Haverkort , Mark de Berg , Joachim Gudmundsson, Box-trees for collision checking in industrial installations, Proceedings of the eighteenth annual symposium on Computational geometry, p.53-62, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513407]
• 17: 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
• 18: Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
• 19: Kothuri Venkata Ravi Kanth , Ambuj K. Singh, Optimal Dynamic Range Searching in Non-replicating Index Structures, Proceedings of the 7th International Conference on Database Theory, p.257-276, January 10-12, 1999
• 20: Scott T. Leutenegger , J. M. Edgington , Mario A. Lopez, STR: A Simple and Efficient Algorithm for R-Tree Packing, Proceedings of the Thirteenth International Conference on Data Engineering, p.497-506, April 07-11, 1997
• 21: 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
• 22: Procopiuc, O., Agarwal, P. K., Arge, L., and Vitter, J. S. 2003. BKD-Tree: A dynamic scalable KD-Tree. In Proceedings of the International Symposium on Spatial and Temporal Databases.
• 23: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 24: 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
• 25: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 26: TIGER. 1998. TIGER/Line#8482; files, 1997 technical documentation. Washington, DC. http://www.census.gov/geo/tiger/TIGER97D.pdf.

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: Geometrical problems and computations

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Experimentation

Keywords:
R-trees