Aarhus University Seal / Aarhus Universitets segl

Lars Arge

The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-tree

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Lars Arge
  • Mark de Berg, TU Eindhoven, Eindhoven, Netherlands
  • Herman Haverkort, Utrecht University, Utrecht, Netherlands
  • Ke Yi, Duke University, Durham, NC, United States
  • Department of Computer Science

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 similar to the best known R-tree variants on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.

Original languageEnglish
Title of host publicationProceedings of ACM SIGMOD International Conference on Management of Data
EditorsGerhard Weikum, Arnd Christian König, Stefan Dessloch
Number of pages11
PublisherAssociation for Computing Machinery
Publication year2004
ISBN (print)1-58113-859-8
Publication statusPublished - 2004
EventACM SIGMOD international conference on Management of data - Paris, France
Duration: 13 Jun 200418 Jun 2004
Conference number: 25


ConferenceACM SIGMOD international conference on Management of data

See relations at Aarhus University Citationformats

ID: 10650767