The Priority RTree: A Practically Efficient and WorstCase Optimal RTree

American Medical Informatics Association 2009 Annual Symposium

(extended abstract) ; 2 Department of Computer Science, TU Eindhoven, ; 3 Department of Computer Science, Duke University,

PID  :  77047

来源: CEUR

【 摘 要 】

We present the Priority Rtree, or PRtree, which is the firstRtree variant that always answers a window query using O((N/B)11/d+ T/B) I/Os, where N is the number of ddimensional (hyper) rectangles stored in the Rtree, B is the disk block size, and T is the output size. This is provably asymptotically optimal and significantly better than other Rtree 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 prac tical performance of the PRtree using both reallife and synthetic data. This study shows that the PRtree performs similar to the best known Rtree variants on reallife and relatively nicely distributed data, but out