R-дерево

Структуры данных, используемые при пространственной индексации

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

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

R-деревья — это древовидные структуры данных , используемые для методов пространственного доступа , т. е. для индексации многомерной информации, такой как географические координаты , прямоугольники или многоугольники . R-дерево было предложено Антонином Гутманом в 1984 году ^[2] и нашло широкое применение как в теоретическом, так и в прикладном контексте. ^[3] Обычное практическое использование R-дерева может заключаться в хранении пространственных объектов, таких как расположение ресторанов или многоугольников, из которых состоят типичные карты: улиц, зданий, очертаний озер, береговых линий и т. д., а затем поиске ответов. быстро на такие запросы, как «Найти все музеи в пределах 2 км от моего текущего местоположения», «получить все участки дороги в пределах 2 км от моего местоположения» (чтобы отобразить их в навигационной системе ) или «найти ближайшую заправочную станцию» (хотя и не с учетом дорог). R-дерево также может ускорить поиск ближайшего соседа ^[4] для различных показателей расстояния, включая расстояние по большому кругу . ^[5]

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

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

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

Как и в большинстве деревьев, алгоритмы поиска (например, пересечение , включение, поиск ближайшего соседа ) довольно просты. Основная идея состоит в том, чтобы использовать ограничивающие рамки, чтобы решить, следует ли выполнять поиск внутри поддерева. Таким образом, большинство узлов дерева никогда не читаются во время поиска. Как и B-деревья, R-деревья подходят для больших наборов данных и баз данных , где узлы при необходимости могут быть выгружены в память, а все дерево не может храниться в основной памяти. Даже если данные можно разместить в памяти (или кэшировать), R-деревья в большинстве практических приложений обычно обеспечивают преимущества в производительности по сравнению с простой проверкой всех объектов, когда количество объектов превышает несколько сотен или около того. Однако для приложений в памяти существуют аналогичные альтернативы, которые могут обеспечить немного лучшую производительность или их проще реализовать на практике. ^{[ нужна ссылка ]} Чтобы поддерживать вычисления в памяти для R-дерева в компьютерном кластере, где вычислительные узлы соединены сетью, исследователи использовали RDMA ( Remote Direct Memory Access ) для реализации приложений с интенсивным использованием данных под R-деревом в распределенной среде. среда. ^[6] Этот подход масштабируется для все более крупных приложений и обеспечивает высокую пропускную способность и низкую задержку для R-дерева.

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

R-деревья не гарантируют хорошую производительность в худшем случае , но в целом хорошо работают с реальными данными. ^{[7] Хотя вариант} R-дерева с приоритетной загрузкой представляет больший теоретический интерес, он является оптимальным для наихудшего случая, ^[8] но из-за повышенной сложности не получил большого внимания в практических приложениях, поэтому далеко.

Когда данные организованы в R-дерево, соседи на заданном расстоянии r и k ближайших соседей (для любого L ^p -Norm ) всех точек могут эффективно вычисляться с использованием пространственного соединения. ^{[9] [10]} Это полезно для многих алгоритмов, основанных на таких запросах, например, Local Outlier Factor . ДеЛи-Клу, ^[11] Density-Link-Clustering — это алгоритм кластерного анализа , который использует структуру R-дерева для аналогичного типа пространственного соединения для эффективного расчета кластеризации OPTICS .

Варианты

• Приоритетное R-дерево
• R*-дерево
• R+ дерево
• Гильбертово R-дерево
• X-дерево

Алгоритм

Расположение данных

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

Поиск

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

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

Вставка

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

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

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

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

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

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

Существуют и другие стратегии разделения, такие как разделение Грина ^[13] , эвристика разделения R *-дерева ^[14] (которая снова пытается минимизировать перекрытие, но также предпочитает квадратичные страницы) или алгоритм линейного разделения, предложенный Энгом и Таном ^[15]. (которые, однако, могут создавать очень неправильные прямоугольники, которые менее эффективны для многих реальных диапазонных и оконных запросов). Помимо более продвинутой эвристики разделения, R*-дерево также пытается избежать разделения узла путем повторной вставки некоторых членов узла, что аналогично тому, как B-дерево уравновешивает переполненные узлы. Было показано, что это также уменьшает перекрытие и, таким образом, повышает производительность дерева.

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

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

• 
  Квадратичное расщепление Гутмана. ^[2]
  Страницы в этом дереве сильно перекрываются.
• 
  Линейный раскол Гутмана. ^[2]
  Еще хуже структура, но и быстрее построить.
• 
  Раскол Грина. ^[13] Страницы пересекаются гораздо меньше, чем в стратегии Гутмана.
• 
  Линейный раскол Анг-Тан. ^[15]
  Эта стратегия создает фрагментированные страницы, которые часто приводят к плохой производительности запросов.
• 
  Топологическое расщепление дерева R* . ^[14]
  Страницы перекрываются гораздо меньше, поскольку R*-дерево пытается минимизировать перекрытие страниц, а повторные вставки дополнительно оптимизируют дерево. Стратегия разделения отдает предпочтение квадратичным страницам, что обеспечивает лучшую производительность для обычных картографических приложений.
• 
  Массовая загрузка дерева R* с использованием рекурсивной сортировки (STR).
  Листовые страницы вообще не перекрываются, а страницы каталогов перекрываются лишь незначительно. Это очень эффективное дерево, но оно требует, чтобы данные были полностью известны заранее.
• 
  М-деревья аналогичны R-дереву, но используют вложенные сферические страницы.
  Однако разделить эти страницы гораздо сложнее, и страницы обычно перекрываются гораздо сильнее.

Удаление

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

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

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

Смотрите также

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

Рекомендации

1. Дерево R cs.sfu.ca
2. Гуттман, А. (1984). «R-деревья: структура динамического индекса для пространственного поиска» (PDF) . Материалы международной конференции ACM SIGMOD 1984 года по управлению данными – SIGMOD '84 . п. 47. дои : 10.1145/602259.602266. ISBN 978-0897911283. S2CID  876601.
3. Ю. Манолопулос; А. Нанопулос; Ю. Теодоридис (2006). R-деревья: теория и приложения. Спрингер. ISBN 978-1-85233-977-7. Проверено 8 октября 2011 г.
4. Руссопулос, Н.; Келли, С.; Винсент, Рузвельт (1995). «Запросы ближайших соседей». Материалы международной конференции ACM SIGMOD 1995 г. по управлению данными – SIGMOD '95 . п. 71. дои : 10.1145/223784.223794 . ISBN 0897917316.
5. Шуберт, Э.; Зимек, А.; Кригель, HP (2013). «Запросы геодезического расстояния на R-деревьях для индексации географических данных». Достижения в области пространственных и временных баз данных . Конспекты лекций по информатике. Том. 8098. с. 146. дои : 10.1007/978-3-642-40235-7_9. ISBN 978-3-642-40234-0.
6. Мэнбай Сяо, Хао Ван, Лян Гэн, Рубао Ли и Сяодун Чжан (2022). «Вычислительная платформа в памяти с поддержкой RDMA для R-дерева в кластерах» . Транзакции ACM в пространственных алгоритмах и системах. стр. 1–26. дои : 10.1145/3503513 .{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )
7. Хван, С.; Квон, К.; Ча, СК; Ли, бакалавр наук (2003). «Оценка производительности вариантов R-дерева основной памяти» . Достижения в области пространственных и временных баз данных . Конспекты лекций по информатике. Том. 2750. стр. 10. doi :10.1007/978-3-540-45072-6_2. ISBN 978-3-540-40535-1.
8. Арге, Л .; Де Берг, М.; Хаверкорт, HJ; Йи, К. (2004). «Приоритетное R-дерево» (PDF) . Материалы международной конференции ACM SIGMOD 2004 г. по управлению данными – SIGMOD '04. п. 347. дои : 10.1145/1007568.1007608. ISBN 978-1581138597. S2CID  6817500.
9. Бринкхофф, Т.; Кригель, HP ; Сигер, Б. (1993). «Эффективная обработка пространственных соединений с использованием R-деревьев». Запись ACM SIGMOD . 22 (2): 237. CiteSeerX 10.1.1.72.4514 . дои : 10.1145/170036.170075. S2CID  7810650. 
10. Бём, Кристиан; Кребс, Флориан (1 сентября 2003 г.). «Поддержка приложений KDD с помощью соединения k-ближайшего соседа». Приложения баз данных и экспертных систем . Конспекты лекций по информатике. Том. 2736. Шпрингер, Берлин, Гейдельберг. стр. 504–516. CiteSeerX 10.1.1.71.454 . дои : 10.1007/978-3-540-45227-0_50. ISBN  9783540408062.
11. Ахтерт, Эльке; Бём, Кристиан; Крёгер, Пер (2006). «DeLi-Clu: повышение надежности, полноты, удобства использования и эффективности иерархической кластеризации с помощью ранжирования ближайших пар». В Нг, Ви Кеонг; Кицурегава, Масару; Ли, Цзяньчжун; Чанг, Куйю (ред.). Достижения в области обнаружения знаний и интеллектуального анализа данных, 10-я Тихоокеанско-Азиатская конференция, PAKDD 2006, Сингапур, 9–12 апреля 2006 г., Материалы . Конспекты лекций по информатике. Том. 3918. Спрингер. стр. 119–128. дои : 10.1007/11731139_16.
12. Куан, Дж.; Льюис, П. (1997). «Быстрый поиск ближайшего соседа для семейства R-деревьев». Труды ICICS, Международная конференция по информации, коммуникациям и обработке сигналов 1997 г. Тема: Тенденции в разработке информационных систем и беспроводной мультимедийной связи (Кат. № 97TH8237) . п. 924. дои : 10.1109/ICICS.1997.652114. ISBN 0-7803-3676-3.
13. Грин, Д. (1989). «Реализация и анализ производительности методов доступа к пространственным данным». [1989] Труды. Пятая международная конференция по инженерии данных . стр. 606–615. дои : 10.1109/ICDE.1989.47268. ISBN 978-0-8186-1915-1. S2CID  7957624.
14. Бекманн, Н.; Кригель, HP ; Шнайдер, Р.; Сигер, Б. (1990). «R*-дерево: эффективный и надежный метод доступа к точкам и прямоугольникам» (PDF) . Материалы международной конференции ACM SIGMOD 1990 года по управлению данными – SIGMOD '90 . п. 322. CiteSeerX 10.1.1.129.3731 . дои : 10.1145/93597.98741. ISBN  978-0897913652. S2CID  11567855.
15. Анг, CH; Тан, ТК (1997). «Новый алгоритм линейного разделения узлов для R-деревьев». Ин Шолль, Мишель; Вуасар, Аньес (ред.). Материалы 5-го Международного симпозиума по достижениям в области пространственных баз данных (SSD '97), Берлин, Германия, 15–18 июля 1997 г. Конспекты лекций по информатике. Том. 1262. Спрингер. стр. 337–349. дои : 10.1007/3-540-63238-7_38.
16. Берхтольд, Стефан; Кейм, Дэниел А.; Кригель, Ханс-Петер (1996). «X-Tree: структура индекса для многомерных данных». Материалы 22-й конференции ВЛДБ . Мумбаи, Индия: 28–39.
17. Лейтенеггер, Скотт Т.; Эджингтон, Джеффри М.; Лопес, Марио А. (февраль 1997 г.). «STR: простой и эффективный алгоритм упаковки R-дерева».
18. Ли, Тэвон; Ли, Сухо (июнь 2003 г.). «OMT: Алгоритм массовой загрузки сверху вниз с минимизацией перекрытия для R-дерева» (PDF) .

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

• СМИ, связанные с R-деревом, на Викискладе?