Приоритетное R-дерево

является R-дерево приоритетов асимптотически для наихудшего случая оптимальной альтернативой пространственному дереву R-дерева . Впервые он был предложен Арге, Де Бергом, Хаверкортом и Йи К. в статье 2004 года. Приоритизированное R-дерево, по сути, является гибридом k -мерного дерева и R-дерева данного объекта , поскольку оно определяет N-мерный ограничивающий объем (называемый минимальными ограничивающими прямоугольниками – MBR) как точку в N-мерностях, представленную выражением упорядоченная пара прямоугольников. Термин «приоритетность» возник из-за введения четырех листьев приоритета, которые представляют собой наиболее крайние значения каждого измерения, включенные в каждую ветвь дерева. Прежде чем ответить на запрос окна путем обхода подветвей, приоритетное R-дерево сначала проверяет наличие перекрытия в своих приоритетных узлах. Подветви просматриваются (и создаются) путем проверки того, превышает ли наименьшее значение первого измерения запроса значение подветвей. Это дает доступ к быстрой индексации по значению первого измерения ограничивающей рамки.

Производительность

Арге и др. пишет, что дерево приоритетов всегда отвечает на оконные запросы с $O\left(\left({\frac {N}{B}}\right)^{1-{\frac {1}{d}}}+{\frac {T}{B}}\right)$ Ввод-вывод, где N — количество d-мерных (гипер) прямоугольников, хранящихся в R-дереве, B — размер дискового блока, а T — выходной размер.

Размеры

В случае $d=2$ прямоугольник представлен $\,((x_{min},y_{min}),(x_{max},y_{max}))$ и MBR таким образом четыре угла $\,(x_{min},y_{min},x_{max},y_{max})$.

См. также

• Иерархия ограничивающих объемов
• B-дерево
• R-дерево