Priority R-tree

The Priority R-tree is a worst-case asymptotically optimal alternative to the spatial tree R-tree. It was first proposed by Arge, De Berg, Haverkort and Yi, K. in an article from 2004.{{cite news|author1=L. Arge|author1-link= Lars Arge |author2=M. de Berg|author3=H. J. Haverkort|author4=K. Yi|title=The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree|url=http://www.win.tue.nl/~mdberg/Papers/prtree.pdf|accessdate=12 October 2011|year=2004|publisher=SIGMOD}} The prioritized R-tree is essentially a hybrid between a k-dimensional tree and a R-tree in that it defines a given object's N-dimensional bounding volume (called Minimum Bounding Rectangles – MBR) as a point in N-dimensions, represented by the ordered pair of the rectangles. The term prioritized arrives from the introduction of four priority-leaves that represents the most extreme values of each dimensions, included in every branch of the tree. Before answering a window-query by traversing the sub-branches, the prioritized R-tree first checks for overlap in its priority nodes. The sub-branches are traversed (and constructed) by checking whether the least value of the first dimension of the query is above the value of the sub-branches. This gives access to a quick indexation by the value of the first dimension of the bounding box.