What is the difference between a KD tree and an R tree?

Question

I looked at the definitions of KD-tree and R-tree. It seems to me that they are almost the same.

What is the difference between a KD tree and an R tree?

Answer 1

R-trees and k d-trees are based on similar ideas (dividing space based on axially aligned areas), but the key differences are:

• The nodes in k d-trees are dividing planes, while the nodes in R-trees are bounding rectangles.
• k d-trees break up the whole space into regions, while R-trees break up only a subset of the space containing points of interest.
• k d-trees represent a disjoint partition (points belong to only one region), while regions in an R-tree can overlap.

(There are many similar tree structures for dividing space: quadrants, BSP trees, R * points, etc. etc.)

Answer 2

In fact, they are completely different. They serve similar purposes (regional spatial data queries) and are trees, but that's almost all that they have in common.

• R-trees are balanced, k-trees are not (if not loaded in large numbers). This is why R-trees are preferred for modifying data, because re-optimization may require rebuilding kd-trees.
• R-trees are disk oriented. They actually organize data in areas that are directly displayed in a representation on disk. This makes them more useful in real databases and for running out of memory. kd-trees are memory oriented and non-trivial for placement on disk pages
• R-trees do not cover the entire data space. Empty areas can be detected. CD trees always cover the whole space.
• The kd-trees binaries split the data space, and the r-trees split the data into rectangles. Binary splits obviously do not intersect; while the rectangles of the r-tree can overlap (which is actually sometimes good, although they try to minimize the overlap)
• kd trees are much easier to implement in memory, which is actually their key advantage
• R-trees can store rectangles and polygons, kd-trees only store point vectors (since overlapping is necessary for polygons)
• R-trees come with different optimization strategies, different partitions, bulk loaders, insert and re-insert strategies, etc.
• Kd trees support the square of the Euclidean distance and Minkowski norms, while Rtrees also support the geodesic distance (for finding nearby points on geodata).

Answer 3

The main difference between the two not mentioned in this answer is that KD trees are only effective in bulk load situations. Once created, changing or changing the balance of the KD tree is nontrivial. R-trees do not suffer from this.