R-дерево

R-дерево

R-дерево (англ. R-trees) — древовидная структура данных (дерево), предложенная в 1984 году Антонином Гуттманом. Оно подобно B-дереву, но используется для организации доступа к пространственным данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами (широтой и долготой). Типичным запросом с использованием R-деревьев мог бы быть такой: «Найти все музеи в пределах 2 километров от моего текущего местоположения».

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

Алгоритмы вставки и удаления используют эти ограничивающие прямоугольники для обеспечения того, чтобы «близкорасположенные» объекты были помещены в одну листовую вершину. В частности, новый объект попадёт в ту листовую вершину, для которой потребуется наименьшее расширение ее ограничивающего прямоугольника. Каждый элемент листовой вершины хранит два поля данных: способ идентификации данных, описывающих объект, (либо сами эти данные) и ограничивающий прямоугольник этого объекта.

Аналогично, алгоритмы поиска (например, пересечение, включение, окрестности) используют ограничивающие прямоугольники для принятия решения о необходимости поиска в дочерней вершине. Таким образом, большинство вершин никогда не затрагиваются в ходе поиска. Как и в случае с B-деревьями, это свойство R-деревьев обуславливает их применимость для баз данных, где вершины могут выгружаться на диск по мере необходимости.

Для расщепления переполненных вершин могут применяться различные алгоритмы, что порождает деление R-деревьев на подтипы: квадратичные и линейные.

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

Структура R-дерева

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

• maxNumOfEntries — максимальное число детей у вершины
• minNumOfEntries — минимальное число детей у вершины, за исключением корня.

Для корректной работы алгоритмов необходимо, чтобы minNumOfEntries <= maxNumOfEntries / 2. В корневой вершине может быть от 2 до maxNumOfEntries потомков. Часто выбирают minNumOfEntries = 2, тогда для корня выполняются те же условия, что и для остальных вершин. Также иногда разумно выделять отдельные константы для количества точек в листовых вершинах, так как их часто можно делать больше.

Алгоритмы

Вставка

Построение R-дерева происходит, как правило, с помощью многократного вызова операции вставки элемента в дерево. Идея вставки похожа на вставку в B-дерево: пробуем добавить точку в подходящую листовую вершину, если она переполняется, разделяем её и, пока требуется, делим её предков. Приведём ниже классический алгоритм вставки, описанный Антонином Гуттманом.

Функция insert

• вызывает chooseLeaf, чтобы выбрать лист, куда мы хотим вставить точку. Если вставка совершена, то дерево могло быть поделено, и раскол мог дойти до вершины. В этом случае chooseLeaf возвращает две расколотые вершины splittedNodes для вставки в корень
• вызывается функция adjustBounds, которая расширяет ограничивающий прямоугольник корня на вставляемую точку
• проверяет, если chooseLeaf вернула ненулевые splittedNodes, то дерево растёт на уровень вверх: с этого момента корнем объявляется вершина, дети которой те самые splittedNodes

Функция chooseLeaf

• если на входе лист (база рекурсии), то:
  • вызывает функцию doInsert, которая осуществляет непосредственную вставку элемента в дерево и возвращает два листа, если состоялось разделение
  • изменяет ограничивающий прямоугольник вершины с учётом вставленной точки
  • возвращает splittedNodes, которые нам вернул doInsert
• если на входе нелистовая вершина:
  • из всех потомков выбирается тот, чьи границы требуют минимального увеличения для вставки данной точки
  • рекурсивно вызывается chooseLeaf для выбранного потомка
  • поправляются ограничивающие прямоугольники
  • если splittedNodes от рекурсивного вызова нулевые, то покидаем функцию, иначе:
    • если numOfEntries < maxNumOfEntries, то добавляем новую вершину к детям, чистим splittedNodes
    • иначе (когда нет мест для вставки), мы конкатенируем массив детей с новой вершиной и передаём полученное функции linearSplitNodes или другой функции разделения вершин, и вернём из chooseLeaf те splittedNodes, которые нам вернула используемая функция разделения.

Функция linearSplit

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

• по каждой координате для всего набора разделяемых вершин вычисляется разница между максимальной нижней границей прямоугольника по этой координате и минимальной верхней, затем эта величина нормализуется на разницу между максимальной и минимальной координатой точек исходного набора для построения всего дерева
• находится максимум этого нормализованного разброса по всем координатам
• устанавливаем в качестве первых детей для возвращаемых вершин node1 и node2 те вершины из входного списка, на которых достигался максимум, удаляем их из входного списка, корректируем bounds для node1 и node2
• далее, выполняется вставка для оставшихся вершин:
  • если в списке осталось настолько мало вершин, что если их все добавить в одну из выходных вершин, то в ней окажется minNumOfEntries вершин, то в неё добавляется остаток, возврат из функции
  • если в какой-то из вершин уже набран максимум потомков, то остаток добавляется в противоположную, возврат
  • для очередной вершины из списка сравнивается, на сколько надо увеличить ограничивающий прямоугольник при вставке в каждую из двух будущих вершин, где меньше — туда её и вставляется

Функция физической вставки doInsert

• если в вершине есть свободные места, то точка вставляется туда
• если же мест нет, то дети вершины конкатенируются со вставляемой точкой и вызывается функция linearSplit или другую функцию разделения, возвращающую две разделённые вершины, которые мы возвращаем из doInsert

Разбиение с помощью алгоритмов кластеризации

Иногда вместо R-дерева используют так называемое cR-дерево (c означает clustered). Основная идея в том, что для разделения вершин или точек используются алгоритмы кластеризации, такие как k-means. Сложность k-means тоже линейная, но он в большинстве случаев даёт лучший результат, чем линейный алгоритм разделения Гуттмана, в отличие от которого он не только минимизирует суммарную площадь огибающих параллелепипедов, но и расстояние между ними и площадь перекрытия. Для кластеризации точек используется выбранная метрика исходного пространства, для кластеризации вершин можно использовать расстояние между центрами их огибающих параллелепипедов или максимальное расстояние между ними.

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

Интересна идея использовать кластеризацию на несколько кластеров, где несколько может быть больше двух. Однако надо учитывать, что это накладывает определённые ограничения на параметры структуры р-дерева.

Отметим, что помимо cR-дерева существует его вариация clR-дерево, основанное на методе кластеризации, где в качестве центра использован итерационный алгоритм решения «задачи размещения». Алгоритм имеет квадратичную вычислительную сложность, но обеспечивает построение более компактных огибающих параллелепипедов в записях вершин структуры.

Поиск

Поиск в дереве довольно тривиален, надо лишь учитывать тот факт, что каждая точка пространства может быть покрыта несколькими вершинами.

Удаление

Обсуждение R-деревьев

Достоинства

• эффективно хранят локализованные в пространстве группы объектов
• сбалансированы, значит, быстрый поиск в худшем случае
• вставка/удаление одной точки не требует существенной перестройки дерева (динамический индекс)

Недостатки

• чувствительно к порядку добавляемых данных
• ограничивающие прямоугольники вершин могут перекрываться

Ссылки

• Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57. ISBN 0-89791-128-8
• Spatial Index Library
• R-tree Portal
• Revisiting R-tree Construction Principles. Sotiris Brakatsoulas, Dieter Pfoser, and Yannis Theodoridis
• Гулаков В.К., Трубаков А.О. Многомерные структуры данных. 2010. 387 стр. ISBN 978-5-89838-515-6