Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

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

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

Отличие R*-деревьев и R-деревьев

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

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

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

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

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

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

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

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

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

Примечания

Литература

Эта страница в последний раз была отредактирована 12 декабря 2019 в 18:00.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).