R-дерево

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

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

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

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

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

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

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

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

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

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

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

Варианты

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

Алгоритм

Макет данных

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

Поиск

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

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

Вставка

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

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

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

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

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

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

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

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

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

• 
  Квадратичное разбиение Гуттмана. ^[2]
  Страницы в этом дереве во многом перекрываются.
• 
  Линейное разбиение Гуттмана. ^[2]
  Еще худшая структура, но и построить ее быстрее.
• 
  Разделение Грина. ^[13] Страницы пересекаются гораздо меньше, чем в стратегии Гуттмана.
• 
  Линейное разделение Ang-Tan. ^[15]
  Эта стратегия создает нарезанные страницы, которые часто приводят к плохой производительности запросов.
• 
  Топологическое разделение дерева R* . ^[14]
  Страницы перекрываются гораздо меньше, поскольку дерево R* пытается минимизировать перекрытие страниц, а повторные вставки еще больше оптимизируют дерево. Стратегия разделения предпочитает квадратичные страницы, что обеспечивает лучшую производительность для обычных приложений карт.
• 
  Массовая загрузка дерева R* с использованием Sort-Tile-Recursive (STR).
  Страницы листьев вообще не перекрываются, а страницы каталогов перекрываются лишь немного. Это очень эффективное дерево, но оно требует, чтобы данные были полностью известны заранее.
• 
  M-деревья похожи на 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. Guttman, A. (1984). "R-деревья: динамическая индексная структура для пространственного поиска" (PDF) . Труды международной конференции ACM SIGMOD 1984 года по управлению данными – SIGMOD '84 . стр. 47. doi :10.1145/602259.602266. ISBN 978-0897911283. S2CID  876601.
3. Y. Manolopoulos; A. Nanopoulos; Y. Theodoridis (2006). R-деревья: теория и приложения. Springer. ISBN 978-1-85233-977-7. Получено 8 октября 2011 г.
4. Руссопулос, Н.; Келли, С.; Винсент, ФДР (1995). "Запросы ближайшего соседа". Труды международной конференции ACM SIGMOD 1995 года по управлению данными – SIGMOD '95 . стр. 71. doi : 10.1145/223784.223794 . ISBN 0897917316.
5. Шуберт, Э.; Зимек, А.; Кригель, Х. П. (2013). "Геодезические запросы расстояний на R-деревьях для индексации географических данных". Достижения в области пространственных и временных баз данных . Конспект лекций по информатике. Том 8098. стр. 146. doi :10.1007/978-3-642-40235-7_9. ISBN 978-3-642-40234-0.
6. Мэнбай Сяо, Хао Ван, Лян Гэн, Рубао Ли и Сяодун Чжан (2022). «Вычислительная платформа в памяти с поддержкой RDMA для R-дерева на кластерах» . ACM Transactions on Spatial Algorithms and Systems. стр. 1–26. doi : 10.1145/3503513 .{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )
7. Hwang, S.; Kwon, K.; Cha, SK; Lee, BS (2003). "Оценка производительности вариантов R-дерева в основной памяти" . Достижения в области пространственных и временных баз данных . Конспект лекций по информатике. Том 2750. С. 10. doi :10.1007/978-3-540-45072-6_2. ISBN 978-3-540-40535-1.
8. Arge, L. ; De Berg, M.; Haverkort, HJ; Yi, K. (2004). "Приоритетное R-дерево" (PDF) . Труды международной конференции ACM SIGMOD 2004 года по управлению данными – SIGMOD '04. стр. 347. doi :10.1145/1007568.1007608. ISBN 978-1581138597. S2CID  6817500.
9. Бринкхофф, Т.; Кригель, Х. П .; Сигер, Б. (1993). «Эффективная обработка пространственных соединений с использованием R-деревьев». ACM SIGMOD Record . 22 (2): 237. CiteSeerX 10.1.1.72.4514 . doi :10.1145/170036.170075. S2CID  7810650. 
10. Бём, Кристиан; Кребс, Флориан (2003-09-01). "Поддержка приложений KDD с помощью k-Nearest Neighbor Join". Приложения для баз данных и экспертных систем . Конспект лекций по информатике. Том 2736. Springer, Берлин, Гейдельберг. С. 504–516. CiteSeerX 10.1.1.71.454 . doi :10.1007/978-3-540-45227-0_50. ISBN  9783540408062.
11. Ахтерт, Элке; Бём, Кристиан; Крёгер, Пир (2006). «DeLi-Clu: повышение надёжности, полноты, удобства использования и эффективности иерархической кластеризации с помощью ранжирования ближайших пар». В Нг, Ви Кеонг; Кицурегава, Масару; Ли, Цзяньчжун; Чанг, Куйю (ред.). Достижения в области обнаружения знаний и интеллектуального анализа данных, 10-я Тихоокеанско-азиатская конференция, PAKDD 2006, Сингапур, 9–12 апреля 2006 г., Труды . Заметки лекций по информатике. Том 3918. Springer. стр. 119–128. doi :10.1007/11731139_16.
12. Куан, Дж.; Льюис, П. (1997). "Быстрый поиск k ближайших соседей для семейства R-tree". Труды ICICS, 1997 Международная конференция по информации, коммуникациям и обработке сигналов. Тема: Тенденции в области проектирования информационных систем и беспроводных мультимедийных коммуникаций (Кат. № 97TH8237) . стр. 924. doi :10.1109/ICICS.1997.652114. ISBN 0-7803-3676-3.
13. Greene, D. (1989). "Реализация и анализ производительности методов доступа к пространственным данным". [1989] Труды. Пятая международная конференция по инжинирингу данных . стр. 606–615. doi :10.1109/ICDE.1989.47268. ISBN 978-0-8186-1915-1. S2CID  7957624.
14. Beckmann, N.; Kriegel, HP ; Schneider, R.; Seeger, B. (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.
15. Ang, CH; Tan, TC (1997). "Новый линейный алгоритм разделения узлов для R-деревьев". В Scholl, Michel; Voisard, Agnès (ред.). Труды 5-го Международного симпозиума по достижениям в области пространственных баз данных (SSD '97), Берлин, Германия, 15–18 июля 1997 г. Lecture Notes in Computer Science. Том 1262. Springer. стр. 337–349. doi :10.1007/3-540-63238-7_38.
16. Берхтольд, Стефан; Кейм, Дэниел А.; Кригель, Ханс-Петер (1996). «X-дерево: структура индекса для многомерных данных». Труды 22-й конференции VLDB . Мумбаи, Индия: 28–39.
17. Лютенеггер, Скотт Т.; Эджингтон, Джеффри М.; Лопес, Марио А. (февраль 1997 г.). «STR: простой и эффективный алгоритм упаковки R-дерева».
18. Ли, Тэвон; Ли, Сухо (июнь 2003 г.). «OMT: алгоритм массовой загрузки сверху вниз с минимизацией перекрытия для R-дерева» (PDF) .

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

• Медиа, связанные с R-tree на Wikimedia Commons