A split heuristic decides how to partition an overflowing tree node into two groups. In an R-tree, that decision shapes the tree, its overlap, and its query performance; for internal nodes, it partitions k-dimensional shapes rather than only points. section 10.2.3
Common objectives differ with the tree’s bounding-envelope geometry:
- R-trees use aligned rectangular envelopes and seek splits that avoid inefficient overlap, although the detailed heuristics can become complicated. section 10.2.3
- The original SS-tree heuristic chooses the dimension with highest variance, sorts the children along it, and divides the list. section 10.3
- The SS+-tree heuristic applies constrained k-means to create exactly two nearby-point groups, with no cluster exceeding M points. section 10.5.3
Trading split quality for speed
For a node containing M+1 points, the original SS-tree split costs O(dM). The k-means variant costs O(jdM), where d is dimensionality and j is the iteration limit. Increasing j can improve the partition while increasing running time. section 10.5.3
Figure 10.7 An example of bad and good splits of an internal node’s rectangle, taken from the original paper by Antonin Guttman
Compare a bad and a good internal-node split to see why partition geometry affects tree efficiency. section 10.2.3
Figure 10.27 An example of the different partitions produced by the split heuristic in the original SS-tree version (center) and the k-means split heuristic (left). For the original heuristic, the direction of maximum variance was along the y axis. For this example, we assume M==12 and m==6.
Compare the original variance-based SS-tree partition with the k-means partition for M=12 and m=6. section 10.5.3
