Laminar flame speed: Difference between revisions
en>AFLmcgill No edit summary |
en>Brian the Editor m Link to Mallard's stub |
||
| Line 1: | Line 1: | ||
The '''Priority R-tree''' is a [[Worst-case_complexity|worst-case asymptotically optimal]] alternative to the [[spatial access method|spatial]] [[tree data structure|tree]] [[R-tree]]. It was first proposed by Arge, De Berg, Haverkort and Yi, K. in an article from 2004.<ref name="prtree-article">{{cite article|author1=L. Arge|author2=M. de Berg|author3=H. J. Haverkort|author3=K. Yi|title=The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree|url=http://www.win.tue.nl/~mdberg/Papers/prtree.pdf|accessdate=12 October 2011|year=2004|publisher=SIGMOD}}</ref> The prioritized R-tree is essentially a hybrid between a [[kd-tree|k-dimensional tree]] and a r-tree in that it defines a given object's N-dimensional [[bounding volume hierarchy|bounding volume]] (called Minimum Bounding Rectangles - MBR) as a [[point (geometry)|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 [[query|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 | |||
<math>\, O((N / B)^{1-1/d} + T / B) I/Os</math>, 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 <math>\, ((x_{min}, y_{min}), (x_{max}, y_{max}))</math> and the MBR thus four corners <math>\, (x_{min}, y_{min}, x_{max}, y_{max})</math>. | |||
== See also == | |||
* [[Bounding volume hierarchy]] | |||
* [[B-tree]] | |||
* [[R-tree]] | |||
== References == | |||
<references /> | |||
{{CS trees}} | |||
[[Category:R-tree]] | |||
[[Category:Database index techniques]] | |||
{{Datastructure-stub}} | |||
Latest revision as of 01:38, 14 November 2013
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 , 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 and the MBR thus four corners .