The priority 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 01, 2008
- Source ID
- 10.1145/1328911.1328920
Entities
People
- Herman Haverkort
- Ke Yi
- Lars Arge
- Mark De Berg
Organizations
- Aarhus University
- Army Research Office
- Dutch Research Council
- Eindhoven University of Technology
- Hong Kong University of Science and Technology
- National Science Foundation
- Research Grants Council, University Grants Committee