R*-дерево

В обработке данных R*-деревья являются вариантом R-деревьев , используемых для индексации пространственной информации. R*-деревья имеют немного более высокую стоимость построения, чем стандартные R-деревья, поскольку данные могут нуждаться в повторной вставке; но полученное дерево обычно будет иметь лучшую производительность запросов. Как и стандартное R-дерево, оно может хранить как точечные, так и пространственные данные. Оно было предложено Норбертом Бекманном, Гансом-Петером Кригелем , Ральфом Шнайдером и Бернхардом Зеегером в 1990 году. ^[1]

Разница между R*-деревьями и R-деревьями

Минимизация как покрытия, так и перекрытия имеет решающее значение для производительности R-деревьев. Перекрытие означает, что при запросе или вставке данных необходимо расширить более одной ветви дерева (из-за способа разделения данных в областях, которые могут перекрываться). Минимизированное покрытие улучшает производительность обрезки, позволяя чаще исключать целые страницы из поиска, в частности, для запросов отрицательного диапазона. R*-дерево пытается уменьшить и то, и другое, используя комбинацию пересмотренного алгоритма разделения узлов и концепцию принудительной повторной вставки при переполнении узлов. Это основано на наблюдении, что структуры R-деревьев очень восприимчивы к порядку, в котором вставляются их записи, поэтому структура, построенная путем вставки (а не с массовой загрузкой), скорее всего, будет неоптимальной. Удаление и повторная вставка записей позволяет им «найти» место в дереве, которое может быть более подходящим, чем их исходное расположение.

Когда узел переполняется, часть его записей удаляется из узла и повторно вставляется в дерево. (Чтобы избежать неопределенного каскада повторных вставок, вызванных последующим переполнением узла, процедура повторной вставки может быть вызвана только один раз на каждом уровне дерева при вставке любой новой записи.) Это приводит к созданию более хорошо сгруппированных групп записей в узлах, что снижает покрытие узла. Кроме того, фактическое разделение узлов часто откладывается, что приводит к увеличению средней занятости узла. Повторную вставку можно рассматривать как метод инкрементальной оптимизации дерева, запускаемой при переполнении узла.

R*-дерево описывает три метрики, с помощью которых можно количественно оценить качество разделения. Это перекрытие (общее для R*-деревьев и R-деревьев), определяемое как площадь пересечения ограничивающих прямоугольников двух кластеров; Area-value, представляющее собой сумму площадей двух ограничивающих прямоугольников кластера, и Margin-value, представляющее собой сумму периметров двух ограничивающих прямоугольников кластера.

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

Улучшенная эвристика разделения позволяет создавать страницы, которые имеют более прямоугольную форму и, следовательно, подходят для многих приложений.
Метод повторной вставки оптимизирует существующее дерево, но увеличивает сложность.
Эффективно поддерживает точечные и пространственные данные одновременно.

Влияние различных эвристик разделения на базу данных с почтовыми округами Германии

R-Tree с квадратичным разбиением Гуттмана. ^[2]
Существует множество страниц, которые простираются с востока на запад по всей Германии, и страницы сильно перекрываются. Это невыгодно для большинства приложений, которым часто нужна только небольшая прямоугольная область, пересекающаяся со многими срезами.
R-Tree с линейным разделением Ang-Tan. ^[3]
Хотя срезы не простираются так далеко, как у Гуттмана, проблема среза затрагивает почти каждую страницу листа. Страницы листа перекрываются мало, но страницы каталогов перекрываются.
Топологическое разделение R*-дерева. ^[1]
Страницы перекрываются очень мало, поскольку R*-дерево пытается минимизировать перекрытие страниц, а повторные вставки еще больше оптимизировали дерево. Стратегия разделения также не отдает предпочтение срезам, поэтому полученные страницы гораздо более полезны для обычных приложений карт.

Алгоритм и сложность

R*-дерево использует тот же алгоритм, что и обычное R-дерево для операций запроса и удаления.
При вставке R*-дерево использует комбинированную стратегию. Для листовых узлов минимизируется перекрытие, а для внутренних узлов минимизируются увеличение и площадь.
При разделении R*-дерево использует топологическое разделение, выбирающее ось разделения на основе периметра, а затем минимизирует перекрытие.
Помимо улучшенной стратегии разделения, R*-дерево также пытается избежать разделений путем повторной вставки объектов и поддеревьев в дерево, вдохновленное концепцией балансировки B-дерева .

Таким образом, сложность запроса и удаления в худшем случае идентична R-Tree. Стратегия вставки в R*-дерево сложнее, чем стратегия линейного разделения ( ) R-дерева, но менее сложна, чем стратегия квадратичного разделения ( ) для размера страницы объектов и мало влияет на общую сложность. Общая сложность вставки по-прежнему сопоставима с R-деревом: повторные вставки затрагивают максимум одну ветвь дерева и, таким образом, повторные вставки, сопоставимы с выполнением разделения на обычном R-дереве. Таким образом, в целом сложность R*-дерева такая же, как и у обычного R-дерева. ${\mathcal {O}}(M\log M)$ ${\mathcal {O}}(M)$ ${\mathcal {O}}(M^{2})$ $М$ ${\mathcal {O}}(\log n)$

Реализация полного алгоритма должна учитывать множество особых случаев и сложных ситуаций, которые здесь не обсуждаются.

Ссылки

^ ab Beckmann, N.; Kriegel, HP ; Schneider, R.; Seeger, B. (1990). "R*-дерево: эффективный и надежный метод доступа для точек и прямоугольников". Труды международной конференции ACM SIGMOD 1990 года по управлению данными - SIGMOD '90 (PDF) . стр. 322. doi :10.1145/93597.98741. ISBN 0897913655.
^ Гуттман, А. (1984). "R-деревья: динамическая индексная структура для пространственного поиска". Труды международной конференции ACM SIGMOD 1984 года по управлению данными - SIGMOD '84 (PDF) . стр. 47. doi :10.1145/602259.602266. ISBN 0897911288.
^ Ang, CH; Tan, TC (1997). "Новый линейный алгоритм разделения узлов для R-деревьев". В Scholl, Michel; Voisard, Agnès (ред.). Труды 5-го Международного симпозиума по достижениям в области пространственных баз данных (SSD '97), Берлин, Германия, 15–18 июля 1997 г. Lecture Notes in Computer Science. Том 1262. Springer. стр. 337–349. doi :10.1007/3-540-63238-7_38.

Внешние ссылки

Медиа, связанные с R*-tree на Wikimedia Commons