The Priority R-tree is a
worst-case asymptotically optimal alternative to the
spatial
Spatial may refer to:
*Dimension
*Space
*Three-dimensional space
Three-dimensional space (also: 3D space, 3-space or, rarely, tri-dimensional space) is a geometric setting in which three values (called ''parameters'') are required to determ ...
tree R-tree
R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found sign ...
. It was first proposed by Arge, De Berg, Haverkort and Yi, K. in an article from 2004.
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
In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operatio ...
(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
R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found sign ...
References
R-tree
Database index techniques
{{Datastructure-stub