Priority R-tree

The Priority R-tree is a <a href="/facts/Worst-case_complexity/kqzQkwIc">worst-case asymptotically optimal</a> alternative to the <a href="/facts/Spatial_access_method/wzPAetLd">spatial</a> <a href="/facts/Tree_data_structure/RcXz9noF">tree</a> <a href="/facts/R-tree/9X5AQWln">R-tree</a>. 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 <a href="/facts/K-d_tree/XuhcfKKq">k-dimensional tree</a> and a <a href="/facts/R-tree/9X5AQWln">R-tree</a> in that it defines a given object's N-dimensional <a href="/facts/Bounding_volume_hierarchy/1FBFkwNe">bounding volume</a> (called Minimum Bounding Rectangles – MBR) as a <a href="/facts/Point_(geometry)/6YPAvX2a">point</a> 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 <a href="/facts/Information_retrieval/MFSmpeNw">window-query</a> 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.

Priority R-tree open-in-new

Priority R-tree