R* деревья: оптимизированный метод индексации пространственных данных
R*-tree
R* деревья: эффективный метод индексации пространственных данных. Улучшенная эвристика разбиения для повышения производительности запросов и хранения данных.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Вариант деревьев R, используемых для индексации пространственных данных.
A variant of R trees used for indexing spatial information
В обработке данных деревья R* являются вариантом деревьев R, применяемым для индексации пространственных данных. Деревья R* имеют несколько более высокую стоимость построения, чем стандартные деревья R, так как данные могут потребовать повторной вставки, но в результате получается дерево с обычно более высокой скоростью обработки запросов. Как и стандартное дерево R, оно может хранить как точечные, так и пространственные данные. Оно было предложено Норбертом Бекманом, Хансом Петером Кригелем, Ральфом Шнайдером и Бернхардом Зигером в 1990 году.
In data processing R* trees are a variant of R trees used for indexing spatial information. R* trees have slightly higher construction cost than standard R trees, as the data may need to be reinserted; but the resulting tree will usually have a better query performance. Like the standard R tree, it can store both point and spatial data. It was proposed by Norbert Beckmann, Hans Peter Kriegel, Ralf Schneider, and Bernhard Seeger in 1990.
Выступление
Улучшенная эвристика разбиения создает страницы более прямоугольной формы, что делает их более подходящими для многих приложений. Метод повторной вставки оптимизирует существующее дерево, но повышает сложность. Эффективно поддерживает как точечные, так и пространственные данные.
Improved split heuristic produces pages that are more rectangular and thus better for many applications. Reinsertion method optimizes the existing tree but increases complexity. Efficiently supports point and spatial data at the same time.
Алгоритм и сложность
Дерево R* использует тот же алгоритм, что и обычное R-дерево для операций запроса и удаления. При вставке дерево R* использует комбинированную стратегию: для листовых узлов минимизируется перекрытие, а для внутренних узлов – увеличение размера и площадь. При разделении дерево R* использует топологическое разделение, которое выбирает ось разделения на основе периметра, а затем минимизирует перекрытие. Помимо улучшенной стратегии разделения, дерево R* также пытается избежать разделений, повторно вставляя объекты и поддеревья в дерево, что вдохновлено концепцией балансировки B-дерева. В худшем случае сложность запроса и удаления идентична R-дереву. Стратегия вставки в дерево R* сложнее, чем линейная стратегия разделения R-дерева, но менее сложна, чем квадратичная стратегия разделения для страницы заданного размера объектов, и оказывает незначительное влияние на общую сложность. Общая сложность вставки остаётся сопоставимой с R-деревом: повторные вставки затрагивают максимум одну ветвь дерева и, следовательно, по сложности сопоставимы с выполнением разделения в обычном R-дереве. Таким образом, в целом сложность дерева R* такая же, как и у обычного R-дерева. Реализация полного алгоритма должна учитывать множество крайних случаев и неоднозначных ситуаций, которые здесь не рассматриваются.
The R* tree uses the same algorithm as the regular R tree for query and delete operations. When inserting, the R* tree uses a combined strategy. For leaf nodes, overlap is minimized, while for inner nodes, enlargement and area are minimized. When splitting, the R* tree uses a topological split that chooses a split axis based on perimeter, then minimizes overlap. In addition to an improved split strategy, the R* tree also tries to avoid splits by reinserting objects and subtrees into the tree, inspired by the concept of balancing a B tree. Worst case query and delete complexity are thus identical to the R Tree. The insertion strategy to the R* tree is with more complex than the linear split strategy of the R tree, but less complex than the quadratic split strategy for a page size of objects and has little impact on the total complexity. The total insert complexity is still comparable to the R tree: reinsertions affect at most one branch of the tree and thus reinsertions, comparable to performing a split on a regular R tree. So, on overall, the complexity of the R* tree is the same as that of a regular R tree. An implementation of the full algorithm must address many corner cases and tie situations not discussed here.