Quelqu'un peut-il me dire quelle est la différence entre KD-tree et R-tree

Question

Je regarde la définition de KD-tree et R-tree, il semble qu'ils sont presque les mêmes.

Quelqu'un pourrait-il me dire quelle est la différence entre KD-tree et R-tree? sont basés sur des idées similaires (partitionnement de l'espace basée sur les régions alignées d'axe-) Merci

Answer 1

R-trees et kd-trees, mais les principales différences sont les suivantes:

• nœuds dans k d-arbres représentent de séparation des plans, tandis que les noeuds dans les arbres R représentent des boîtes englobantes. D-trees partitionne tout 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. Les arbres d représentent une partition disjointe (les points appartiennent à une seule région) alors que les régions d'un arbre R peuvent se chevaucher.

(Il y a beaucoup de types similaires de structures d'arbres pour l'espace de partitionnement: quadtrees, BSP arbres, R * -trees, etc., etc.)

Answer 2

Une différence majeure entre les deux ne sont pas mentionnés par Gareth Rees est que les arbres Kd ne sont efficaces que dans des situations de chargement en masse. une fois construit, modifier ou rééquilibrer un Kd-tree est non-trivial. Les arbres R ne souffrent pas de cela.

Answer 3

Ils sont en réalité assez différents. Ils ont un but similaire (requêtes de région sur les données spatiales), et ils sont tous les deux des arbres, mais c'est à peu près tout ce qu'ils ont en commun.

• R Les arbres sont équilibrés, kd arbres ne sont pas (à moins chargé en vrac). C'est pourquoi les arbres R sont préférés pour changer les données, car les arbres kd peuvent avoir besoin d'être reconstruits pour être ré-optimisés.
• Les arbres R sont orientés sur le disque. Ils organisent réellement les données dans les 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 de mémoire insuffisante. kd-trees sont orientés vers la mémoire et ne sont pas triviaux à mettre dans des pages de disque
• Les arbres R ne couvrent pas l'ensemble de l'espace de données. Les zones vides peuvent être découvertes. Les kd-trees couvrent toujours tout l'espace.
• kd-trees binaire divisé l'espace de données, r-arbres partitionner les données en rectangles. Les divisions binaires sont évidemment disjointes; tandis que les rectangles d'un arbre r peuvent se chevaucher (ce qui est parfois bon, bien que l'on essaie de minimiser le chevauchement)
• Les arbres-kd sont beaucoup plus faciles à mettre en œuvre en mémoire, ce qui est leur avantage clé
• R- les arbres peuvent stocker rectangles et polygones, kd arbres que les magasins font des vecteurs (comme le chevauchement est nécessaire pour les polygones)
• R arbres viennent avec différentes stratégies d'optimisation, différentes divisions, en vrac-chargeurs, l'insertion et les stratégies de réinsertion, etc.