Lars Arge, Mark de Berg, Herman Haverkort, and Ke Yi
Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data (SIGMOD '04), Paris, France, June 2004, 347-358. Journal version in ACM Transactions on Algorithms.
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.
Conference version: [acm
Journal version: [acm download]
SIGMOD '04, Paris, France, June 2004. Slides:
Duke CS Algorithms Seminar, March, 2004.
C++ code available for download:
© Association for Computing Machinery 2004.