В чем разница между KD-деревом и R-деревом?

Question

Я посмотрел определения KD-дерева и R-дерева. Мне кажется, что они почти одинаковы.

В чем разница между KD-деревом и R-деревом?

Answer 1

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

• R-деревья сбалансированы , кД-деревья нет (если не загружен).Вот почему R-деревья предпочтительнее для изменения данных, поскольку для повторной оптимизации может потребоваться перестроение kd-деревьев.
• R-деревья ориентированы на диск .Они на самом деле организуют данные в областях, которые напрямую отображаются в представлении на диске.Это делает их более полезными в реальных базах данных и для работы с нехваткой памяти.kd-деревья ориентированы на память и нетривиальны для размещения на страницах диска
• R-деревья не покрывают все пространство данных.Пустые области могут быть обнаружены.kd-деревья всегда покрывают все пространство.
• kd-деревья двоичное разбиение пространство данных, r-деревья разбивают данные на прямоугольники .Бинарные расщепления явно не пересекаются;в то время как прямоугольники r-дерева могут перекрываться (что на самом деле иногда хорошо, хотя стараются минимизировать перекрытие)
• kd-деревья намного проще реализовать в памяти, что на самом деле является их ключевым преимуществом
• R-деревья могут хранить прямоугольников и многоугольников , kd-деревья хранят только точечные векторы (поскольку перекрытие необходимо для многоугольников)
• R-деревья поставляются с различными стратегиями оптимизации, различнымиСплит, массовые загрузчики, стратегии вставки и вставки и т. д.

Answer 2

R-деревья и k d-деревья основаны на сходных идеях (разбиение пространства на основе выровненных по оси областей), но ключевые отличия:

• Узлы в k d-деревьях представляют разделительные плоскости, тогда как узлы в R-деревьях представляют ограничивающие рамки.
• k d-деревья разбивают все пространство на области, тогда как R-деревья разбивают только подмножество пространства, содержащее точки интереса.
• k d-деревья представляют собой непересекающиеся разбиения (точки принадлежат толькоодна область), тогда как области в R-дереве могут перекрываться.

(Существует много аналогичных видов древовидных структур для разбиения пространства: дерева квадрантов, деревья BSP, дерева R * и т. д.и др.)

Answer 3

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