The Priority R-Tree: A Practically E±cient and Worst-Case Optimal R-Tree

Cache-Oblivious and Cache-Aware Algorithms

计算机科学;物理学

Lars Arge ; Mark de Berg ; Herman J. Haverkort ; Ke Yi

Others  :  http://drops.dagstuhl.de/opus/volltexte/2005/155/pdf/04301.HaverkortHerman1.ExtAbstract.155.pdf
PID  :  7295

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

We present the Priority R-tree, or PR-tree, which is the frist 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 signicantly 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 out performs them signicantly on more extreme data.