Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
R * дерево
Изобрел1990 г.
ИзобретенныйНорберт Бекманн, Ханс-Петер Кригель , Ральф Шнайдер и Бернхард Зигер
Сложность времени в большой нотации O
АлгоритмСреднийХудший случай
КосмосО ( п )О ( п )
ПоискO (журнал n )
ВставлятьO (журнал n )

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

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

R * -Дерево, построенное многократной вставкой (в ELKI ). В этом дереве мало перекрытий, что обеспечивает хорошую производительность запросов. Красные и синие MBR - это страницы индекса, зеленые MBR - листовые узлы.

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

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

Производительность [ править ]

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

  • R-дерево с квадратичным разбиением Гутмана. [2]
    Есть много страниц, которые простираются с востока на запад по всей Германии, и страницы во многом пересекаются. Это невыгодно для большинства приложений, которым часто требуется только небольшая прямоугольная область, которая пересекается со многими срезами.

  • R-Tree с линейным разбиением по Ang-Tan. [3]
    Хотя фрагменты не расширяются так далеко, как в случае с Guttman, проблема нарезки затрагивает почти каждую конечную страницу. Листовые страницы немного перекрывают друг друга, но страницы каталогов есть.

  • Топологическое разбиение дерева R * . [1]
    Страницы очень мало перекрываются, поскольку R * -дерево пытается минимизировать перекрытие страниц, а повторные вставки дополнительно оптимизировали дерево. Стратегия разделения также не предпочитает срезы, поэтому получаемые страницы гораздо более полезны для обычных картографических приложений.

Алгоритм и сложность [ править ]

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

Таким образом, сложность запроса и удаления наихудшего случая идентична R-дереву. Стратегия вставки в R * -дерево более сложна, чем стратегия линейного разделения ( ) R-дерева, но менее сложна, чем стратегия квадратичного разделения ( ) для размера страницы объектов, и имеет небольшое влияние на общую сложность. . Общая сложность вставки по-прежнему сравнима с R-деревом: повторные вставки затрагивают не более одной ветви дерева и, следовательно, повторные вставки, сравнимы с выполнением разбиения на обычном R-дереве. Таким образом, в целом сложность R * -дерева такая же, как и у обычного R-дерева.

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

Ссылки [ править ]

  1. ^ a b Beckmann, N .; Кригель, HP ; Schneider, R .; Сигер, Б. (1990). «R * -дерево: эффективный и надежный метод доступа для точек и прямоугольников». Материалы международной конференции ACM SIGMOD по управлению данными 1990 г. - SIGMOD '90 (PDF) . п. 322. DOI : 10,1145 / 93597,98741 . ISBN 0897913655.
  2. ^ Гутман, А. (1984). "R-деревья: динамическая структура индекса для пространственного поиска". Материалы международной конференции ACM SIGMOD 1984 г. по управлению данными - SIGMOD '84 (PDF) . п. 47. DOI : 10,1145 / 602259,602266 . ISBN  0897911288.
  3. ^ Ang, CH; Тан, TC (1997). «Новый алгоритм разделения линейных узлов для R-деревьев». В Шолле, Мишель; Voisard, Agnès (ред.). Труды 5 - го Международного симпозиума по достижениям в области пространственных баз данных (SSD '97), Берлин, Германия, 15-18 июля, 1997 . Конспект лекций по информатике. 1262 . Springer. С. 337–349. DOI : 10.1007 / 3-540-63238-7_38 .

Внешние ссылки [ править ]

  • СМИ, связанные с R * tree на Викискладе?