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 $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.

Dimensions

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

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.

Tree data structures

Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red-black Scapegoat Splay T Treap UB Weight-balanced

Heaps	Binary Binomial Fibonacci Leftist Pairing Skew Van Emde Boas

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

This article is issued from Wikipedia - version of the 3/25/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Priority R-tree

Performance

Dimensions

See also

References