В чем разница между KD-деревом и R-деревом?
Я посмотрел на определения KD-дерева и R-дерева. Мне кажется, что они почти одинаковы.
В чем разница между KD-деревом и R-деревом?
3 ответа
R-деревья и k d-деревья основаны на сходных идеях (разбиение пространства на основе выровненных по оси областей), но ключевые различия:
- Узлы в k d-деревьях представляют разделительные плоскости, тогда как узлы в R-деревьях представляют ограничивающие рамки.
- k-деревья разделяют все пространство на области, тогда как R-деревья разделяют только подмножество пространства, содержащее точки интереса.
- k d-деревьев представляют непересекающиеся разбиения (точки принадлежат только одной области), тогда как области в R-дереве могут перекрываться.
(Существует много похожих видов древовидных структур для разделения пространства: квадри, BSP-деревья, R*-деревья и т. Д. И т. Д.)
Они на самом деле совсем другие. Они служат сходным целям (региональные запросы к пространственным данным) и являются деревьями, но это почти все, что у них общего.
- R-деревья сбалансированы, k-деревья - нет (если не загружены в большом количестве). Вот почему R-деревья предпочтительнее для изменения данных, поскольку для повторной оптимизации может потребоваться перестроить kd-деревья.
- R-деревья ориентированы на диск. Они на самом деле организуют данные в областях, которые напрямую отображаются в представлении на диске. Это делает их более полезными в реальных базах данных и при работе с нехваткой памяти. kd-деревья ориентированы на память и нетривиальны для размещения на страницах диска
- R-деревья не покрывают все пространство данных. Пустые области могут быть обнаружены. КД-деревья всегда покрывают все пространство.
- Двоичные файлы kd-деревьев разбивают пространство данных, а r-деревья делят данные на прямоугольники. Бинарные расщепления явно не пересекаются; в то время как прямоугольники r-дерева могут перекрываться (что на самом деле иногда хорошо, хотя стараются минимизировать перекрытие)
- kd-деревья намного проще реализовать в памяти, что на самом деле является их ключевым преимуществом
- R-деревья могут хранить прямоугольники и многоугольники, kd-деревья хранят только точечные векторы (так как перекрытие необходимо для многоугольников)
- R-деревья поставляются с различными стратегиями оптимизации, различными разбиениями, массовыми загрузчиками, стратегиями вставки и повторной вставки и т. Д.
Основное различие между двумя, не упомянутыми в этом ответе, состоит в том, что KD-деревья эффективны только в ситуациях массовой загрузки. После создания модификация или изменение баланса KD-дерева нетривиальна. R-деревья от этого не страдают.