ThePriority R-tree is aworst-case asymptotically optimal alternative to thespatialtreeR-tree. It was first proposed by Arge, De Berg, Haverkort and Yi, K. in an article from 2004.^[1] The prioritized R-tree is essentially a hybrid between ak-dimensional tree and aR-tree in that it defines a given object's N-dimensionalbounding volume (called Minimum Bounding Rectangles – MBR) as apoint in N-dimensions, represented by the ordered pair of the rectangles. The termprioritized 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 awindow-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.

Argeet al. writes that the priority tree always answers window-queries with${\displaystyle O\left({\left(\frac{N}{B}\right)}^{1-\frac{1}{d}}+\frac{T}{B}\right)}$ 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.

In the case of${\displaystyle d=2}$ the rectangle is represented by${\displaystyle ((x_{min},y_{min}),(x_{max},y_{max}))}$ and the MBR thus four corners${\displaystyle (x_{min},y_{min},x_{max},y_{max})}$.

• Bounding volume hierarchy
• B-tree
• R-tree

Thisalgorithms ordata structures-related article is astub. You can help Wikipedia byadding missing information.

• v
• t
• e

• R-tree
• Database index techniques
• Algorithms and data structures stubs

• All stub articles