✖


Jump to content

R-дерево

Эта статья о структуре данных. Чтобы узнать о типе метрического пространства, см. Реальное дерево .
R-дерево
Тип дерево
Изобретенный 1984
Изобретён Антонин Гуттман
Временная сложность в обозначении большого О
Операция Средний Худший случай
Поиск О( журнал M n ) На ​ ) [1]
Вставлять На ​ )
Пространственная сложность
Простой пример 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-деревьях.

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

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

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

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

Варианты [ править ]

Алгоритм [ править ]

Расположение данных [ править ]

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

Поиск [ править ]

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

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

Вставка [ править ]

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

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

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

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

Разделение переполненного узла [ править ]

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

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

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

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

Удаление [ править ]

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

Массовая загрузка [ править ]

  • Ближайший-X: объекты сортируются по первой координате («X»), а затем разбиваются на страницы желаемого размера.
  • Упакованное гильбертово R-дерево : вариант Nearest-X, но сортировка с использованием значения Гильберта центра прямоугольника вместо использования координаты X. Нет никакой гарантии, что страницы не будут перекрываться.
  • Сортировка-плитка-рекурсивная (STR): [17] Еще один вариант Nearest-X, который оценивает общее количество требуемых листьев как , необходимый коэффициент разделения в каждом измерении для достижения этого как , затем последовательно разбивает каждое измерение на разделы одинакового размера с использованием одномерной сортировки. Полученные страницы, если они занимают более одной страницы, снова загружаются массово по тому же алгоритму. Для точечных данных конечные узлы не будут перекрываться и «разбивать» пространство данных на страницы примерно одинакового размера.
  • Минимизация перекрытия сверху вниз (OMT): [18] Улучшение по сравнению с STR с использованием нисходящего подхода, который сводит к минимуму перекрытие между срезами и повышает производительность запросов.
  • Приоритетное 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 . дои : 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) .

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=R-tree&oldid=1192723243"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 87c1fda9fb0947917d714e76167cc7c0__1703969580
URL1:https://arc.ask3.ru/arc/aa/87/c0/87c1fda9fb0947917d714e76167cc7c0.html
Заголовок, (Title) документа по адресу, URL1:
R-tree - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)