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.

## Contents

* 1 Performance
* 2 Dimensions
* 3 See also
* 4 References

## Performance

Arge et al. writes that the priority tree always answers window-queries with O((NB)1−1d+TB) 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 d=2 the rectangle is represented by ((xmin,ymin),(xmax,ymax)) and the MBR thus four corners (xmin,ymin,xmax,ymax).

## See also

* Bounding volume hierarchy
* B-tree
* R-tree

## References

1. ↑ L. Arge; M. de Berg; H. J. Haverkort; K. Yi (2004). "The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree". SIGMOD. http://www.win.tue.nl/~mdberg/Papers/prtree.pdf. Retrieved 12 October 2011.

* v
* t
* e

Tree data structures

Search trees
(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
* (Left-leaning) Red-black
* Scapegoat
* Splay
* T
* Treap
* UB
* Weight-balanced

Heaps|

* Binary
* Binomial
* Brodal
* Fibonacci
* Leftist
* Pairing
* Skew
* van Emde Boas
* Weak

Tries|

* Ctrie
* C-trie (compressed ADT)
* Hash
* Radix
* Suffix
* Ternary search
* X-fast
* Y-fast

Spatial data partitioning trees|

* Ball
* BK
* BSP
* Cartesian
* Hilbert R
* k-d (implicit k-d)
* M
* Metric
* MVP
* Octree
* Priority R
* Quad
* R
* R+
* R*
* Segment
* VP
* X

Other trees|

* Cover
* Exponential
* Fenwick
* Finger
* Fractal tree index
* Fusion
* Hash calendar
* iDistance
* K-ary
* Left-child right-sibling
* Link/cut
* Log-structured merge
* Merkle
* PQ
* Range
* SPQR
* Top

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Priority R-tree. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Priority_R-tree&oldid=294365"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template