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.[1] 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.
Performance
Arge et al. writes that the priority tree always answers window-queries with 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.
Dimensions
In the case of the rectangle is represented by and the MBR thus four corners .
See also
- Bounding volume hierarchy
- B-tree
- R-tree
References
- ^ L. Arge; M. de Berg; H. J. Haverkort; K. Yi (2004). "The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree" (PDF). SIGMOD. Retrieved 12 October 2011.
- v
- t
- e
(dynamic sets/associative arrays)
- 2–3
- 2–3–4
- AA
- (a,b)
- AVL
- B
- B+
- B*
- Bx
- (Optimal) Binary search
- Dancing
- HTree
- Interval
- Order statistic
- Palindrome
- (Left-leaning) Red–black
- Scapegoat
- Splay
- T
- Treap
- UB
- Weight-balanced
![]() | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e