ICS Theory Group

ICS 269, Spring 2005: Theory Seminar

28 Jan 2005:
"The Priority R-Tree: A Practically Efficient and Worst-Case-Optimal R-Tree" by Lars Arge, et al.
Presented by Ivan A. Seredkin

Abstract: This paper presents 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.

(This paper is from the 2004 ACM SIGMOD International Conference on Management of Data.)