8th January 2007, 1 min read

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.

Reference

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.