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 similar 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. P. K. Agarwal, L. Arge, O. Procopiuc, and J. S. Vitter. A framework for index bulk loading and dynamization. In Proc. International Colloquium on Automata, Languages, and Programming, pages 115--127, 2001.]]
2. P. K. Agarwal, M. de Berg, J. Gudmundsson, M. Hammar, and H. J. Haverkort. Box-trees and R-trees with near-optimal query time. Discrete and Computational Geometry, 28(3):291--312, 2002.]]
3. L. Arge, O. Procopiuc, and J. S. Vitter. Implementing I/O-efficient data structures using TPIE. In Proc. European Symposium on Algorithms, pages 88--100, 2002.]]
4. L. Arge and J. Vahrenhold. I/O-efficient dynamic planar point location. International Journal of Computational Geometry & Applications, 2003. To appear.]]
5. R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173--189, 1972.]]
6. N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Proc. SIGMOD International Conference on Management of Data, pages 322--331, 1990.]]
7. S. Berchtold, C. Böhm, and H.-P. Kriegel. Improving the query performance of high-dimensional index structures by bulk load operations. In Proc. Conference on Extending Database Technology. LNCS 1377, pages 216--230, 1998.]]
8. B. Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, New York, 2001.]]
9. D. Comer. The ubiquitous B-tree. ACM Computing Surveys, 11(2):121--137, 1979.]]
10. D. J. DeWitt, N. Kabra, J. Luo, J. M. Patel, and J.-B. Yu. Client-server paradise. In Proc. International Conference on Very Large Databases, pages 558--569, 1994.]]
11. V. Gaede and O. Günther. Multidimensional access methods. ACM Computing Surveys, 30(2):170--231, 1998.]]
12. Y. J. García, M. A. López, and S. T. Leutenegger. A greedy algorithm for bulk loading R-trees. In Proc. 6th ACM Symposium on Advances in GIS, pages 163--164, 1998.]]
13. A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proc. SIGMOD International Conference on Management of Data, pages 47--57, 1984.]]
14. H. J. Haverkort, M. de Berg, and J. Gudmundsson. Box-trees for collision checking in industrial installations. In Proc. ACM Symposium on Computational Geometry, pages 53--62, 2002.]]
15. I. Kamel and C. Faloutsos. On packing R-trees. In Proc. International Conference on Information and Knowledge Management, pages 490--499, 1993.]]
16. I. Kamel and C. Faloutsos. Hilbert R-tree: An improved R-tree using fractals. In Proc. International Conference on Very Large Databases, pages 500--509, 1994.]]
17. K. V. R. Kanth and A. K. Singh. Optimal dynamic range searching in non-replicating index structures. In Proc. International Conference on Database Theory, LNCS 1540, pages 257--276, 1999.]]
18. S. T. Leutenegger, M. A. López, and J. Edgington. STR: A simple and efficient algorithm for R-tree packing. In Proc. IEEE International Conference on Data Engineering, pages 497--506, 1996.]]
19. Y. Manolopoulos, A. Nanopoulos, A. N. Papadopoulos, and Y. Theodoridis. R-trees have grown everywhere. Technical Report available at http://www.rtreeportal.org/, 2003]]
20. O. Procopiuc, P. K. Agarwal, L. Arge, and J. S. Vitter. Bkd-tree: A dynamic scalable kd-tree. In Proc. International Symposium on Spatial and Temporal Databases, 2003.]]
21. J. Robinson. The K-D-B tree: A search structure for large multidimensional dynamic indexes. In Proc. SIGMOD International Conference on Management of Data, pages 10--18, 1981.]]
22. N. Roussopoulos and D. Leifker. Direct spatial search on pictorial databases using packed R-trees. In Proc. SIGMOD International Conference on Management of Data, pages 17--31, 1985.]]
23. T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-tree: A dynamic index for multi-dimensional objects. In Proc. International Conference on Very Large Databases, pages 507--518, 1987.]]
24. TIGER/Line#8482; Files, 1997 Technical Documentation. Washington, DC, September 1998. http://www.census.gov/geo/tiger/TIGER97D.pdf.]]