Edsger Wybe Dijkstra was one of the most influential members of computing science's founding generation. Among the domains in which his scientific contributions are fundamental are
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