picksplit

Picksplit is a split operation used in hierarchical spatial index structures, most notably R-trees and their variants, to divide a full node into two new nodes when overflow occurs. The objective is to produce two groups of entries whose bounding rectangles have minimal overlap and total area, thereby improving query performance.

The process typically consists of two stages. First, two seed entries are selected to start the two groups. Different variants use different seed selection strategies, such as quadratic or linear splits. In a quadratic split, the pair of entries that would cause the largest enlargement if placed together is chosen as seeds. In a linear split, seeds are chosen with simpler, faster heuristics that aim to maximize separation along one or more dimensions. Second, the remaining entries are distributed between the two groups using a least-enlargement criterion: each entry is assigned to the group that would require the smallest increase in its bounding rectangle. Tie-breaking rules may favor the group with smaller area or fewer entries, and if one group becomes full, the rest are assigned to the other.

Picksplit directly affects the height, occupancy, and overlap of the tree, influencing search, insertion, and delete performance. It is a core component of classic R-trees and is implemented in various spatial indexing libraries, sometimes under different names or with refinements such as those used in R*-tree variants, which further optimize split quality.

In summary, picksplit is the principled division of an overflowing node into two balanced, minimally overlapping groups to maintain efficient spatial indexing.