Priority R-tree

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Priority R-tree is a spatial index designed to be worst-case asymptotically optimal, offering an alternative to the traditional R-tree. It was proposed in 2004 by Arge, De Berg, Haverkort and Yi. The data structure blends ideas from k-d trees and R-trees: instead of storing objects directly, each object's N-dimensional bounding box (its MBR) is treated as a point in N-dimensional space, represented by an ordered pair of rectangles. The tree includes four priority leaves that capture the most extreme values in each dimension in every branch, guiding how the tree is built and searched.

When answering a window query, the algorithm first checks the priority nodes for overlaps, then traverses sub-branches by comparing the least value in the first dimension to decide which sub-branches to explore. This makes it fast to index by the first dimension of bounding boxes. The I/O complexity for operations is O(((N/B)^(1-1/d)) + (T/B)), where N is the number of d-dimensional rectangles stored, B is the disk block size, and T is the output size. In 2D, a rectangle is represented by (xmin, ymin, xmax, ymax).