R-tree

редактировать

R-tree

tree

Изобретено

1984

Изобретено на

Алгоритм		Среднее	Худший случай
Поиск		O (log Mn)

Простой пример R-дерева для 2D-прямоугольники

Визуализация R * -дерева для 3D-точек с использованием ELKI (кубы являются страницами каталогов)

R-деревья используются древовидные структуры данных для методов пространственного доступа, т. е. для индексации многомерной информации, такой как географические координаты, прямоугольники или многоугольники. R-дерево был предложен Антонином Гуттманом в 1984 году и нашел существенное применение как в теоретическом, так и в прикладном контексте. В реальной жизни R-дерево может использоваться для хранения пространственных объектов, таких как местоположения ресторанов или многоугольников, из которых составлены типовые карты: улиц, зданий, очертаний озер, береговых линий и т. д., а затем быстро находите ответы на такие запросы, как "Найти все музеи в пределах 2 км от моего текущего местоположения "," найти все участки дороги в пределах 2 км от моего местоположения "(чтобы отобразить их в навигационной системе ) или" найти ближайшую заправочную станцию "(хотя и не брать дороги во внимание). R-дерево также может ускорить поиск ближайшего соседа для различных показателей расстояния, включая расстояние по дуге.

Содержание

1 Идея R-дерева
2 Варианта
3 Алгоритм
- 3.1 Структура данных
- 3.2 Поиск
- 3.3 Вставка
  - 3.3.1 Выбор поддерева вставки
  - 3.3.2 Разделение переполненного узла
- 3.4 Удаление
- 3.5 Массовая загрузка
4 См. Также
5 Ссылки
6 Внешние ссылки

Идея R-дерева

Ключевая идея структуры данных состоит в том, чтобы сгруппировать близлежащие объекты и представить их с их минимумом ограничивающий прямоугольник на следующем более высоком уровне дерева; «R» в R-дереве означает прямоугольник. Поскольку все объекты лежат внутри этого ограничивающего прямоугольника, запрос, который не пересекает ограничивающий прямоугольник, также не может пересекать ни один из содержащихся в нем объектов. На уровне листа каждый прямоугольник описывает отдельный объект; на более высоких уровнях агрегация увеличивающегося числа объектов. Это также можно рассматривать как более грубое приближение набора данных.

Подобно B-дереву, R-дерево также является сбалансированным деревом поиска (так что все конечные узлы находятся на одной глубине), организует данные на страницах и спроектировано для хранения на диске (как используется в базах данных ). Каждая страница может содержать максимальное количество записей, часто обозначаемое как $M {\ displaystyle M}$ $M$ . Он также гарантирует минимальное заполнение (за исключением корневого узла), однако лучшая производительность была продемонстрирована при минимальном заполнении 30–40% от максимального количества записей (B-деревья гарантируют заполнение страницы на 50%, а B * -деревья даже на 66%). Причина этого - более сложная балансировка, необходимая для пространственных данных, в отличие от линейных данных, хранящихся в B-деревьях.

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

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

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

Когда данные организованы в R-дереве, соседи на заданном расстоянии r и k ближайшие соседи (для любого L-Norm ) всех точек можно эффективно вычислить с помощью пространственного соединения. Это полезно для многих алгоритмов, основанных на таких запросах, например, Локальный фактор выброса. DeLi-Clu, Density-Link-Clustering - это алгоритм кластерного анализа, который использует структуру R-tree для подобного типа пространственного соединения для эффективного вычисления кластеризации OPTICS.

Варианты

Алгоритм

Схема данных

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

Поиск

В поиск по диапазону входом является прямоугольник поиска (окно запроса). Поиск очень похож на поиск в B + дереве. Поиск начинается с корневого узла дерева. Каждый внутренний узел содержит набор прямоугольников и указателей на соответствующий дочерний узел, а каждый листовой узел содержит прямоугольники пространственных объектов (указатель на некоторый пространственный объект может находиться там). Для каждого прямоугольника в узле необходимо решить, перекрывает он прямоугольник поиска или нет. Если да, необходимо также найти соответствующий дочерний узел. Поиск выполняется таким образом рекурсивно до тех пор, пока не будут пройдены все перекрывающиеся узлы. Когда достигается листовой узел, содержащиеся в нем ограничивающие рамки (прямоугольники) проверяются относительно прямоугольника поиска, и их объекты (если они есть) помещаются в набор результатов, если они лежат в пределах прямоугольника поиска.

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

Вставка

Чтобы вставить объект, дерево рекурсивно просматривается из корневой узел. На каждом шаге проверяются все прямоугольники в текущем узле каталога, и кандидат выбирается с помощью эвристики, такой как выбор прямоугольника, который требует наименьшего увеличения. Затем поиск спускается на эту страницу, пока не достигнет листового узла. Если листовой узел заполнен, он должен быть разделен перед выполнением вставки. Опять же, поскольку исчерпывающий поиск слишком затратен, используется эвристика для разделения узла на два. При добавлении вновь созданного узла к предыдущему уровню этот уровень снова может переполняться, и эти переполнения могут распространяться до корневого узла; когда этот узел также переполняется, создается новый корневой узел, и дерево увеличивается в высоту.

Выбор поддерева вставки

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

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

Разделение узла с переполнением

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

Существуют и другие стратегии разделения, такие как разделение Грина, эвристика разделения R * -дерева (которая снова пытается минимизировать перекрытие, но также предпочитает квадратичные страницы) или алгоритм линейного разделения, предложенный Ang и Tan (которые, однако, могут создавать очень неправильные прямоугольники, которые менее эффективны для многих реальных запросов диапазона и окна). В дополнение к более продвинутой эвристике разделения, R * -дерево также пытается избежать разделения узла, повторно вставляя некоторые из элементов узла, что аналогично способу B-дерева уравновешивает переполненные узлы. Было показано, что это также уменьшает перекрытие и, следовательно, увеличивает производительность дерева.

Наконец, X-tree можно рассматривать как вариант R * -дерева, которое также может решить не разбивать узел, а построить так называемый суперузел, содержащий все лишние записи, когда не удается найти хорошее разделение (особенно для данных большой размерности).

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

Квадратичное разбиение Гуттмана.. Страницы в этом дереве часто перекрываются.
Линейное расщепление Гуттмана.. Еще хуже структура, но строить быстрее.
Раскол Грина. Страницы пересекаются гораздо меньше, чем в стратегии Гуттмана.
Линейное разбиение по Анг-Тану.. Эта стратегия создает нарезанные страницы, что часто приводит к снижению производительности запросов.
R * tree топологическое разбиение.. Страницы перекрываются гораздо меньше, поскольку R * -дерево пытается минимизировать перекрытие страниц, а повторные вставки дополнительно оптимизировали дерево. Стратегия разделения предпочитает квадратные страницы, что обеспечивает лучшую производительность для общих картографических приложений.
Массовая загрузка R * tree с использованием Sort-Tile-Recursive (STR).. Листовые страницы вообще не перекрываются, а страницы каталога частично перекрываются. Это очень эффективное дерево, но оно требует, чтобы данные были полностью известны заранее.
M-деревья похожи на R-дерево, но используют вложенные сферические страницы.. Однако разделение этих страниц намного сложнее, и страницы обычно намного больше перекрываются.

Удаление

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

Массовая загрузка

Ближайший-X: объекты сортируются по их первой координате ("X"), а затем разделяются на страницы желаемого размера.
Упаковано Hilbert R -tree : вариант Nearest-X, но сортировка с использованием значения Гильберта для центра прямоугольника вместо использования координаты X. Нет гарантии, что страницы не будут перекрываться.
Sort-Tile-Recursive (STR): еще один вариант Nearest-X, который оценивает общее количество требуемых листьев как $l = ⌈ количество объектов / capacity ⌉ {\ displaystyle l = \ lceil {\ text {number of objects}} / {\ text {capacity}} \ rceil}$ $l = \ lceil {\ text {количество объектов}} / {\ text {capacity}} \ rceil$ , требуемый коэффициент разделения в каждом измерении для достижения этого как $s = ⌈ l 1 / d ⌉ {\ displaystyle s = \ lceil l ^ {1 / d} \ rceil}$ $s = \ lceil l ^ {{1 / d}} \ rceil$ , затем последовательно разбивает каждое измерение на $s {\ displaystyle s}$ $s$ разделы одинакового размера с использованием одномерной сортировки. Полученные страницы, если они занимают более одной страницы, снова загружаются массово с использованием того же алгоритма. Для точечных данных конечные узлы не будут перекрываться, а «мозаика» пространства данных на страницы примерно одинакового размера.
Минимизация перекрытия сверху вниз (OMT): улучшение по сравнению с STR с использованием подхода сверху вниз, который минимизирует перекрывается между срезами и улучшает производительность запроса.
Приоритетное R-дерево

См. также

Сегментное дерево
Интервальное дерево - вырожденное R-дерево для одного измерения (обычно времени).
Иерархия ограничивающего объема
Пространственный индекс
GiST

Литература

^ Гуттман А. (1984). «R-деревья: структура динамического индекса для пространственного поиска» (PDF). Материалы международной конференции ACM SIGMOD 1984 г. по управлению данными - SIGMOD '84. п. 47. doi : 10.1145 / 602259.602266. ISBN 978-0897911283. S2CID 876601.
^Y. Манолопулос; А. Нанопулос; Я. Теодоридис (2006). R-деревья: теория и приложения. Springer. ISBN 978-1-85233-977-7. Проверено 8 октября 2011 г.
^Roussopoulos, N.; Kelley, S.; Винсент, Ф. Д. Р. (1995). «Запросы ближайшего соседа». Материалы международной конференции ACM SIGMOD по управлению данными 1995 г. - SIGMOD '95. п. 71. doi : 10.1145 / 223784.223794. ISBN 0897917316.
^ Schubert, E.; Зимек, А.; Кригель, Х. П. (2013). «Геодезические дистанционные запросы на R-деревьях для индексации географических данных». Достижения в пространственных и временных базах данных. Конспект лекций по информатике. 8098 . п. 146. doi : 10.1007 / 978-3-642-40235-7_9. ISBN 978-3-642-40234-0.
^Hwang, S.; Kwon, K.; Cha, S. K.; Ли, Б. С. (2003). «Оценка производительности вариантов R-дерева оперативной памяти». Достижения в пространственных и временных базах данных. Конспект лекций по информатике. 2750 . С. 10. doi : 10.1007 / 978-3-540-45072-6_2. ISBN 978-3-540-40535-1.
^Arge, L. ; Де Берг, М.; Haverkort, H.J.; Йи, К. (2004). «Приоритетное R-дерево» (PDF). Материалы международной конференции ACM SIGMOD 2004 г. по управлению данными - SIGMOD '04. п. 347. doi : 10.1145 / 1007568.1007608. ISBN 978-1581138597. S2CID 6817500.
^Brinkhoff, T.; Кригель, Х. П. ; Сигер, Б. (1993). «Эффективная обработка пространственных объединений с использованием R-деревьев». ACM SIGMOD Запись. 22 (2): 237. CiteSeerX 10.1.1.72.4514. doi : 10.1145 / 170036.170075.
^Бём, Кристиан; Кребс, Флориан (01.09.2003). Поддержка приложений KDD с помощью k-ближайшего соседа. Приложения баз данных и экспертных систем. Конспект лекций по информатике. Шпрингер, Берлин, Гейдельберг. С. 504–516. CiteSeerX 10.1.1.71.454. DOI : 10.1007 / 978-3-540-45227-0_50. ISBN 9783540408062.
^Achtert, E.; Böhm, C.; Крегер, П. (2006). DeLi-Clu: Повышение устойчивости, полноты, удобства использования и эффективности иерархической кластеризации с помощью ранжирования ближайшей пары. LNCS: достижения в области обнаружения знаний и интеллектуального анализа данных. Конспект лекций по информатике. 3918 . С. 119–128. doi : 10.1007 / 11731139_16. ISBN 978-3-540-33206-0.
^Куан, Дж.; Льюис, П. (1997). «Быстрый поиск k ближайших соседей для семейства R-tree». Труды ICICS, 1997 Международная конференция по информации, связи и обработке сигналов. Тема: «Тенденции в разработке информационных систем и беспроводной мультимедийной связи» (№ по каталогу 97TH8237). п. 924. DOI : 10.1109 / ICICS.1997.652114. ISBN 0-7803-3676-3.
^ Грин, Д. (1989). «Реализация и анализ производительности методов доступа к пространственным данным». [1989] Известия. Пятая международная конференция по инженерии данных. С. 606–615. doi : 10.1109 / ICDE.1989.47268. ISBN 978-0-8186-1915-1. S2CID 7957624.
^ Beckmann, N.; Кригель, Х. П. ; Schneider, R.; Сигер, Б. (1990). «R * -дерево: эффективный и надежный метод доступа для точек и прямоугольников» (PDF). Материалы международной конференции ACM SIGMOD по управлению данными 1990 г. - SIGMOD '90. п. 322. CiteSeerX 10.1.1.129.3731. doi : 10.1145 / 93597.98741. ISBN 978-0897913652. S2CID 11567855.
^ Ang, C.H.; Тан, Т. С. (1997). «Новый алгоритм разделения линейных узлов для R-деревьев». В Шолле, Мишель; Voisard, Agnès (ред.). Труды 5-го Международного симпозиума по достижениям в области пространственных баз данных (SSD '97), Берлин, Германия, 15–18 июля 1997 г. Конспект лекций по информатике. 1262 . Springer. С. 337–349. doi : 10.1007 / 3-540-63238-7_38.
^Берхтольд, Стефан; Keim, Daniel A.; Кригель, Ханс-Петер (1996). «X-Tree: структура индекса для данных большого размера». Материалы 22-й конференции VLDB. Мумбаи, Индия: 28–39.
^Leutenegger, Scott T.; Эджингтон, Джеффри М.; Лопес, Марио А. (февраль 1997 г.). «STR: простой и эффективный алгоритм упаковки R-дерева». Для цитирования журнала требуется | journal =()
^Ли, Тэвон; Ли, Сухо (июнь 2003 г.). «OMT: алгоритм минимизации перекрытия, минимизирующий массовую загрузку сверху вниз для R-дерева» (PDF). Для цитирования журнала требуется | journal =()

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

СМИ, связанные с R-tree на Wikimedia Commons