Quelle est la différence entre un KD-tree et un R-tree ?

Question

J'ai regardé la définition de KD-tree et R-tree. Il me semble qu'elles sont presque identiques.

Quelle est la différence entre un KD-tree et un R-tree ?

Answer 1

Ils sont en fait très différents. Ils servent un objectif similaire (requêtes régionales sur des données spatiales), sont tous deux des arbres (et appartiennent tous deux à la famille des index hiérarchiques de volumes limites), mais c'est à peu près tout ce qu'ils ont en commun.

• Les arbres R sont équilibré les arbres k-d ne le sont pas (sauf s'ils sont chargés en masse). C'est pourquoi les arbres R sont préférables pour les données changeantes, car les arbres k-d peuvent avoir besoin d'être reconstruits pour être ré-optimisés.
• Les arbres R sont orienté disque . Ils organisent en fait les données dans des zones qui correspondent directement à la représentation sur le disque. Cela les rend plus utiles dans les bases de données réelles et pour les opérations hors mémoire. Les k-d-trees sont orienté vers la mémoire et sont non-triviaux à mettre dans des pages de disque
• Les arbres k-d sont élégants lorsqu'ils sont chargés en masse (bravo à SingleNegationElimination pour l'avoir signalé), tandis que les arbres R sont plus adaptés à l'utilisation de l'informatique. en changeant (bien qu'ils bénéficient du chargement en masse, lorsqu'ils sont utilisés avec des données statiques).
• Les arbres R ne couvrent pas la totalité de l'espace de données. Des zones vides peuvent être découvertes. Les arbres k-d couvrent toujours la totalité de l'espace.
• k-d-trees division binaire l'espace de données, les arbres R partitionnent les données en rectangles . Les divisions binaires sont évidemment disjointes ; alors que les rectangles d'un R-tree peuvent se chevaucher (ce qui est en fait parfois une bonne chose, même si l'on essaie de minimiser le chevauchement).
• Les arbres k-d sont beaucoup plus faciles à mettre en œuvre en mémoire, ce qui constitue leur principal avantage.
• Les arbres R peuvent stocker rectangles et polygones les arbres k-d ne stockent que les vecteurs de points (car le chevauchement est nécessaire pour les polygones).
• Les arbres R sont dotés de diverses stratégies d'optimisation, de différents fractionnements, de chargeurs de masse, de stratégies d'insertion et de réinsertion, etc.
• Les arbres k-d utilisent la distance unidimensionnelle à l'hyperplan de séparation comme limite ; les arbres R utilisent la distance minimale d-dimensionnelle à l'hyperrectangle de délimitation pour la délimitation (ils peuvent également utiliser la distance maximale pour certaines requêtes de comptage, afin de filtrer les vrais positifs).
• Les arbres k-d prennent en charge la distance euclidienne au carré et les normes de Minkowski, tandis que les arbres R se sont révélés capables de prendre également en charge la distance géodésique (pour trouver des points proches sur des géodonnées).

Answer 2

Arbres R y k d-arbres reposent sur des idées similaires (partitionnement de l'espace basé sur des régions alignées sur l'axe), mais les principales différences sont les suivantes :

• Nœuds dans k Les nœuds des arbres d représentent des plans de séparation, tandis que les nœuds des arbres R représentent des boîtes de délimitation.
• k Les arbres d partitionnent l'ensemble de l'espace en régions alors que les arbres R ne partitionnent que le sous-ensemble de l'espace contenant les points d'intérêt.
• k Les d-arbres représentent une partition disjointe (les points n'appartiennent qu'à une seule région) alors que les régions d'un R-arbre peuvent se chevaucher.

(Il existe de nombreux types de structures arborescentes similaires pour le partitionnement de l'espace : quadtrees, BSP-trees, R*-trees, etc. etc.)

Answer 3

Une différence majeure entre les deux, non mentionnée dans cette réponse est que les arbres KD ne sont efficaces que dans les situations de chargement en masse. Une fois construite, la modification ou le rééquilibrage d'une arborescence KD n'est pas triviale. Les R-trees ne souffrent pas de ce problème.