Аноним

R-дерево: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Строка 13: Строка 13:


== R-деревья ==
== R-деревья ==
R-дерево, введенное Гуттманом [9], представляет собой многовариантное дерево <math>\mathcal{T} \;</math>, очень похожее на [[B-дерево (дерево многоканального поиска)|B-дерево]], использующееся для хранения множества S, благодаря чему на оконные запросы можно эффективно получать ответы. Каждая вершина <math>\mathcal{T} \;</math> помещается в один блок диска. Гиперкубы из S хранятся только в листьях <math>\mathcal{T} \;</math>. Все листья <math>\mathcal{T} \;</math> находятся на одном и том же уровне, в каждом из них хранится <math>\Theta(B) \;</math> гиперкубов из S; каждая внутренняя вершина, кроме корня, имеет [[\Theta(B) \;]] инцидентных ей исходящих дуг. Корень <math>\mathcal{T} \;</math> имеет только две исходящих дуги. Для любой вершины <math>u \in \mathcal{T} \;</math> обозначим за R(u) наименьший параллельный осям гиперкуб, называемый [[минимальный ограничивающий прямоугольник|минимальным ограничивающим прямоугольником]], который включает все гиперкубы, хранящиеся ниже u. В каждой внутренней вершине <math>v \in \mathcal{T} \;</math> с детьми <math>v_1, ..., v_b \;</math> ограничивающий прямоугольник <math>R(v_i) \;</math> хранится вместе с указателем на <math>v_i \;</math> для i = 1, ..., k. Заметим, что эти ограничивающие прямоугольники могут перекрываться. На рис. 1 представлен пример R-дерева в двух измерениях.
R-дерево, введенное Гуттманом [9], представляет собой многовариантное дерево <math>\mathcal{T} \;</math>, очень похожее на [[B-дерево (дерево многоканального поиска)|B-дерево]], использующееся для хранения множества S, благодаря чему на оконные запросы можно эффективно получать ответы. Каждая вершина <math>\mathcal{T} \;</math> помещается в один блок диска. Гиперкубы из S хранятся только в листьях <math>\mathcal{T} \;</math>. Все листья <math>\mathcal{T} \;</math> находятся на одном и том же уровне, в каждом из них хранится <math>\Theta(B) \;</math> гиперкубов из S; каждая внутренняя вершина, кроме корня, имеет <math>\Theta(B) \;</math> инцидентных ей исходящих дуг. Корень <math>\mathcal{T} \;</math> имеет только две исходящих дуги. Для любой вершины <math>u \in \mathcal{T} \;</math> обозначим за R(u) наименьший параллельный осям гиперкуб, называемый [[минимальный ограничивающий прямоугольник|минимальным ограничивающим прямоугольником]], который включает все гиперкубы, хранящиеся ниже u. В каждой внутренней вершине <math>v \in \mathcal{T} \;</math> с детьми <math>v_1, ..., v_b \;</math> ограничивающий прямоугольник <math>R(v_i) \;</math> хранится вместе с указателем на <math>v_i \;</math> для i = 1, ..., k. Заметим, что эти ограничивающие прямоугольники могут перекрываться. На рис. 1 представлен пример R-дерева в двух измерениях.




Строка 25: Строка 25:


Любое R-дерево занимает линейное число O(N/B) блоков на диске, однако у разных R-деревьев может быть разная стоимость запроса, обновления и построения. При анализе сложности оконных запросов наряду со значениями N, M и B также учитывается размер выходных данных T.
Любое R-дерево занимает линейное число O(N/B) блоков на диске, однако у разных R-деревьев может быть разная стоимость запроса, обновления и построения. При анализе сложности оконных запросов наряду со значениями N, M и B также учитывается размер выходных данных T.


== Основные результаты ==
== Основные результаты ==
Строка 43: Строка 44:


Было также отмечено, что R-деревья с приоритетами на практике работают весьма успешно [3]. Однако неизвестно, как эффективно обновлять их с сохранением границы для наихудшего случая. Для поддержки операций вставки и удаления был предложен логарифмический метод [3], однако получающаяся структура уже не будет R-деревом. Заметим, однако, что нижняя граница из теоремы 1 относится только к R-деревьям. Если структура данных не ограничена определением R-дерева, в процессе выполнения оконных запросов можно получить более подходящие границы; см., например, [4].
Было также отмечено, что R-деревья с приоритетами на практике работают весьма успешно [3]. Однако неизвестно, как эффективно обновлять их с сохранением границы для наихудшего случая. Для поддержки операций вставки и удаления был предложен логарифмический метод [3], однако получающаяся структура уже не будет R-деревом. Заметим, однако, что нижняя граница из теоремы 1 относится только к R-деревьям. Если структура данных не ограничена определением R-дерева, в процессе выполнения оконных запросов можно получить более подходящие границы; см., например, [4].


== Применение ==
== Применение ==
Строка 50: Строка 52:
Несколько интересных вопросов, касающихся R-деревьев, остаются нерешенными. Среди них можно выделить следующие.
Несколько интересных вопросов, касающихся R-деревьев, остаются нерешенными. Среди них можно выделить следующие.


• Возможно ли разработать R-дерево с оптимальной границей запросов O((WB)1"1/d + T/B) и возможностью эффективного обновления или доказать значение нижней границы стоимости обновления у такого R-дерева?
• Возможно ли разработать R-дерево с оптимальной границей запросов <math>O((N/B)^{1 - 1/d} + T/B) \;</math> и возможностью эффективного обновления или доказать значение нижней границы стоимости обновления у такого R-дерева?


• Существует ли R-дерево, поддерживающее объединенные запросы для параллельных осям гиперкубов за О((Ш)1"1И) операций ввода-вывода? Это было бы оптимально, поскольку нижняя граница из теоремы 1 также верна для объединенных запросов на R-деревьях. Впрочем, стоит отметить, что для запросов о ближайших соседях не существует сублинейной границы в наихудшем случае, поскольку несложно разработать пример для наихудшего случая, в котором расстояние между точкой запроса q и любым ограничивающим прямоугольником будет меньше расстояния между q и его истинным ближайшим соседом.
• Существует ли R-дерево, поддерживающее объединенные запросы для параллельных осям гиперкубов за <math>O((N/B)^{1 - 1/d}) \;</math> операций ввода-вывода? Это было бы оптимально, поскольку нижняя граница из теоремы 1 также верна для объединенных запросов на R-деревьях. Впрочем, стоит отметить, что для запросов о ближайших соседях не существует сублинейной границы в наихудшем случае, поскольку несложно разработать пример для наихудшего случая, в котором расстояние между точкой запроса q и любым ограничивающим прямоугольником будет меньше расстояния между q и его истинным ближайшим соседом.


• Когда оконный запрос Q стягивается в точку, иначе говоря, когда требуется найти все гиперкубы из S, содержащие точку запроса, такую задачу часто называют прокалывающим запросом или запросом с замыканием на точку. Нижняя граница из теоремы 1 для этого специального случая не действует; для модели сильной индексируемости в [5] была доказана нижняя граница £?(log2 N + T/B). Любопытно было бы узнать истинную сложность прокалывающих запросов при помощи R-деревьев, которая находится в интервале между Q{\og2 N + T/B) и O{{NIB)l~lld + T/B).
• Когда оконный запрос Q стягивается в точку, иначе говоря, когда требуется найти все гиперкубы из S, содержащие точку запроса, такую задачу часто называют ''прокалывающим запросом'' или ''запросом с замыканием на точку''. Нижняя граница из теоремы 1 для этого специального случая не действует; для модели сильной индексируемости в [5] была доказана нижняя граница <math>\Theta(log_2 \; N + T/B)</math>. Любопытно было бы узнать истинную сложность прокалывающих запросов при помощи R-деревьев, которая находится в интервале между <math>\Theta(log_2 \; N + T/B)</math> и <math>O((N/B)^{1 - 1/d} + T/B) \;</math>.




4551

правка