Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Эта статья о структуре данных. Для типа метрического пространства см. Реальное дерево .
R-дерево
Типдерево
Изобрел1984
ИзобретенныйАнтонин Гуттман
Сложность времени в большой нотации O
АлгоритмСреднийХудший случай
ПоискO ( журнал M n )O ( 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-tree состоит в том, чтобы построить эффективное дерево, которое, с одной стороны, сбалансировано (так что листовые узлы находятся на одной высоте), с другой стороны, прямоугольники не покрывают слишком много пустого пространства и не слишком сильно перекрываются ( так что во время поиска нужно обрабатывать меньше поддеревьев). Например, первоначальная идея вставки элементов для получения эффективного дерева состоит в том, чтобы всегда вставлять в поддерево, которое требует наименьшего увеличения его ограничивающего прямоугольника. После заполнения страницы данные разделяются на два набора, каждый из которых должен занимать минимальную площадь. Большая часть исследований и улучшений для R-деревьев направлена ​​на улучшение способа построения дерева и может быть сгруппирована по двум целям: построение эффективного дерева с нуля (известная как массовая загрузка) и выполнение изменений в существующем дереве (вставка и удаление).

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

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

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

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

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

Формат данных [ править ]

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

Искать [ редактировать ]

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

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

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

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

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

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

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

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

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

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

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

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

  • Квадратичное расщепление Гуттмана. [2]
    Страницы в этом дереве часто пересекаются.

  • Линейное расщепление Гуттмана. [2]
    Еще худшая конструкция, но и быстрее в строительстве.

  • Раскол Грина. [12] Страницы пересекаются гораздо меньше, чем со стратегией Гуттмана.

  • Линейное расщепление по Анг-Тану. [14]
    Эта стратегия создает нарезанные страницы, что часто снижает производительность запросов.

  • Топологическое расщепление R * дерева . [13]
    Страницы перекрываются гораздо меньше, поскольку R * -дерево пытается минимизировать перекрытие страниц, а повторные вставки дополнительно оптимизировали дерево. Стратегия разделения отдает предпочтение квадратичным страницам, что обеспечивает лучшую производительность для обычных картографических приложений.

  • Массово загруженное дерево R * с использованием Sort-Tile-Recursive (STR).
    Листовые страницы совсем не перекрываются, а страницы каталогов частично перекрываются. Это очень эффективное дерево, но оно требует, чтобы данные были полностью известны заранее.

  • M-деревья похожи на R-дерево, но используют вложенные сферические страницы.
    Однако разделение этих страниц намного сложнее, и страницы обычно намного больше перекрываются.

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ https://www2.cs.sfu.ca/CourseCentral/454/jpei/slides/R-Tree.pdf
  2. ^ a b c Гуттман А. (1984). «R-деревья: динамическая структура индекса для пространственного поиска» (PDF) . Материалы международной конференции ACM SIGMOD 1984 г. по управлению данными - SIGMOD '84 . п. 47. DOI : 10,1145 / 602259,602266 . ISBN 978-0897911283. S2CID  876601 .
  3. ^ Y. Manolopoulos; А. Нанопулос; Я. Теодоридис (2006). R-деревья: теория и приложения . Springer. ISBN 978-1-85233-977-7. Проверено 8 октября 2011 года .
  4. ^ Roussopoulos, N .; Kelley, S .; Винсент, Рузвельт (1995). «Запросы ближайшего соседа». Материалы международной конференции ACM SIGMOD по управлению данными 1995 г. - SIGMOD '95 . п. 71. DOI : 10,1145 / 223784,223794 . ISBN 0897917316.
  5. ^ a b Schubert, E .; Зимек, А .; Кригель, HP (2013). «Геодезические дистанционные запросы на R-деревьях для индексации географических данных». Достижения в пространственных и временных базах данных . Конспект лекций по информатике. 8098 . п. 146. DOI : 10.1007 / 978-3-642-40235-7_9 . ISBN 978-3-642-40234-0.
  6. ^ Hwang, S .; Kwon, K .; Cha, SK; Ли, Б.С. (2003). "Оценка производительности вариантов R-дерева основной памяти" . Достижения в пространственных и временных базах данных . Конспект лекций по информатике. 2750 . С.  10 . DOI : 10.1007 / 978-3-540-45072-6_2 . ISBN 978-3-540-40535-1.
  7. ^ Arge, L .; Де Берг, М .; Хаверкорт, HJ; Йи, К. (2004). «Приоритетное R-дерево» (PDF) . Материалы международной конференции ACM SIGMOD 2004 г. по управлению данными - SIGMOD '04 . п. 347. DOI : 10,1145 / 1007568,1007608 . ISBN  978-1581138597. S2CID  6817500 .
  8. ^ Brinkhoff, T .; Кригель, HP ; Сигер, Б. (1993). «Эффективная обработка пространственных объединений с использованием R-деревьев». ACM SIGMOD Запись . 22 (2): 237. CiteSeerX 10.1.1.72.4514 . DOI : 10.1145 / 170036.170075 . 
  9. ^ Бём, Кристиан; Кребс, Флориан (01.09.2003). Поддержка приложений KDD с помощью k-ближайшего соседа . Приложения баз данных и экспертных систем . Конспект лекций по информатике. Шпрингер, Берлин, Гейдельберг. С. 504–516. CiteSeerX 10.1.1.71.454 . DOI : 10.1007 / 978-3-540-45227-0_50 . ISBN  9783540408062.
  10. ^ Achtert, E .; Böhm, C .; Крегер, П. (2006). DeLi-Clu: Повышение устойчивости, полноты, удобства использования и эффективности иерархической кластеризации с помощью ранжирования ближайшей пары . LNCS: достижения в области обнаружения знаний и интеллектуального анализа данных . Конспект лекций по информатике. 3918 . С. 119–128. DOI : 10.1007 / 11731139_16 . ISBN 978-3-540-33206-0.
  11. ^ Куан, Дж .; Льюис, П. (1997). «Быстрый поиск k ближайших соседей для семейства R-tree». Труды ICICS, 1997 Международная конференция по информации, связи и обработке сигналов. Тема: «Тенденции в разработке информационных систем и беспроводной мультимедийной связи» (№ по каталогу 97TH8237) . п. 924. DOI : 10,1109 / ICICS.1997.652114 . ISBN 0-7803-3676-3.
  12. ^ a b Грин, Д. (1989). «Реализация и анализ производительности методов доступа к пространственным данным». [1989] Известия. Пятая международная конференция по инженерии данных . С. 606–615. DOI : 10.1109 / ICDE.1989.47268 . ISBN 978-0-8186-1915-1. S2CID  7957624 .
  13. ^ a b Beckmann, N .; Кригель, HP ; 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 .
  14. ^ a b Ang, CH; Тан, TC (1997). «Новый алгоритм разделения линейных узлов для R-деревьев». В Шолле, Мишель; Voisard, Agnès (ред.). Труды 5 - го Международного симпозиума по достижениям в области пространственных баз данных (SSD '97), Берлин, Германия, 15-18 июля, 1997 . Конспект лекций по информатике. 1262 . Springer. С. 337–349. DOI : 10.1007 / 3-540-63238-7_38 .
  15. ^ Берхтольд, Стефан; Keim, Daniel A .; Кригель, Ханс-Петер (1996). «X-Tree: структура индекса для данных большой размерности» . Материалы 22-й конференции VLDB . Мумбаи, Индия: 28–39.
  16. ^ Leutenegger, Скотт Т .; Эджингтон, Джеффри М .; Лопес, Марио А. (февраль 1997 г.). "STR: простой и эффективный алгоритм упаковки R-Tree" . Cite journal requires |journal= (help)
  17. ^ Ли, Тэвон; Ли, Сухо (июнь 2003 г.). "OMT: алгоритм минимизации перекрытия нисходящей массовой загрузки для R-дерева" (PDF) . Cite journal requires |journal= (help)

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

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