Priority R-Tree

I have been doing some reading on Priority R-Trees (PR-Trees). R-trees are the equivalent of B-trees for spatial data. Apparently, PR-Tree perform must like R-trees on average, but with a much better worst case analysis.


Lars Arge, Mark de Berg, Herman Haverkort, and Ke Yi, The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree, In Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data (SIGMOD ’04), Paris, France, June 2004, 347-358.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    Markdown is turned off in code blocks:
     [This is not a link](

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see