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

редактировать

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

Содержание

1 Производительность
2 Размеры
3 См. Также
4 Ссылки

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

Arge et al. пишет, что дерево приоритетов всегда отвечает на запросы окна с помощью $O ((NB) 1-1 d + TB) {\ displaystyle O \ left (\ left ({\ frac {N} {B}} \ right) ^ {1 - {\ frac {1} {d}}} + {\ frac {T} {B}} \ right)}$ ${\ displaystyle O \ left (\ left ({\ frac {N} {B}} \ right) ^ {1- { \ frac {1} {d}}} + {\ frac {T} {B}} \ right)}$ I / Os, где N - количество d-мерных (гипер -) прямоугольники, хранящиеся в R-дереве, B - размер блока диска, а T - размер вывода.

Размеры

В случае N = 2 прямоугольник представлен как $((xmin, ymin), (xmax, ymax)) {\ displaystyle \, ((x_ { min}, y_ {min}), (x_ {max}, y_ {max}))}$ $\, ((x_ { {min}}, y _ {{min}}), (x _ {{max}}, y _ {{max}}))$ и MBR, таким образом, четыре угла $(xmin, ymin, xmax, ymax) {\ displaystyle \, (x_ {min}, y_ {min}, x_ {max}, y_ {max})}$ $\, (x _ {{min}}, y _ {{min}) }, x _ {{max}}, y _ {{max}})$ .

См. также

Ссылки

^Л. Ардж ; М. де Берг; Х. Дж. Хаверкорт; К. Йи (2004). «Приоритетное R-дерево: Практически эффективное и оптимальное для наихудшего случая R-дерево» (PDF). SIGMOD. Проверено 12 октября 2011 г.