Bounding-envelope overlap is the intersection between regions enclosing neighboring nodes or indexed objects. In similarity-search trees, excessive overlap can make searches visit multiple branches, so reducing it supports faster search while preserving a usable tree balance. section 10.5.4 section 10.3.4
Treat overlap as a structural condition rather than merely a split-time objective. A variance-minimizing split can indirectly reduce average overlap, but SS+-trees check problematic configurations separately because overlap may arise across several operations, nodes, or levels. section 10.5.4 section 10.3.4
A practical overlap-reduction procedure is:
- Check whether one bounding sphere is completely contained in another by testing the smaller center and comparing centroid distance with R - r. section 10.5.4
- Avoid exact hypersphere-intersection volume when the heuristic would make its integral-based computation too expensive. section 10.5.4
- When overlap is significant, cluster all grandchildren of the affected node and replace its children with the resulting clusters. section 10.5.4
- Use centroids when grandchildren are nodes, and points when they are leaf entries. section 10.5.4 section 10.3.4
Grandchildren split
For an SS-tree with m == 2 and M >= 5, run k-means with k == 5 over points A–L when a parent and its children overlap substantially. The procedure can return four clusters instead of five, and those clusters replace the original children.
