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

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 3

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