Приоритетное R-дерево
-
Приоритетное R-дерево
- Альтернатива пространственному R-дереву
- Предложено Арджем, Де Бергом, Хаверкортом и Йи в 2004 году
- Гибридное между k-мерным деревом и R-деревом
-
Определение MBR
- MBR — минимальные ограничивающие прямоугольники
- MBR представляют объект как точку в N-измерениях
- MBR имеют четыре угла
-
Приоритетные листья
- Введены четыре приоритетных листа
- Листья представляют экстремальные значения каждого измерения
-
Процесс запроса
- Приоритетное R-дерево сначала проверяет совпадения в приоритетных узлах
- Подсети просматриваются по значению первого измерения
-
Производительность
- O(N^1-1/d + T/B) операций ввода-вывода
- N — количество d-мерных прямоугольников, B — размер дискового блока, T — размер выходных данных
-
Пример для d=2
- Прямоугольник представлен как (xmin, ymin), (xmax, ymax)
- MBR имеет четыре угла: (xmin, ymin, xmax, ymax)