A reorganization heuristic reduces overlap in a similarity-search tree by replacing a node’s children with clusters formed from its grandchildren. It is triggered after checking whether one bounding envelope substantially contains another, using sphere centers, radii, and centroid distance. section 10.5.4
The procedure works as follows:
- Check whether two bounding spheres are nested or sufficiently close according to a distance-to-radius threshold. section 10.5.4
- Run k-means on the node’s grandchildren, using the former child count as the initial number of clusters. section 10.5.4
- Replace the children with the resulting clusters, allowing empty clusters to disappear. section 10.5.4
- Use the heuristic infrequently because it costs O(jMk) comparisons or assignments. section 10.5.4
Reorganizing node S1
Run the heuristic on node S1’s grandchildren, points A–L, with five initial clusters. K-means may return only four clusters when one centroid receives no points, reducing overlap among S1’s children. section 10.5.4
Figure 10.28 An example where the grandchildren-split heuristic could be triggered and would lower the nodes overlap. The SS-tree in the example has m==2 and M>=5. The k-means split heuristic is run on the points A-L, with k==5. Notice how k-means can (and sometimes will) output fewer clusters than the initial number of centroids. In this case, only four clusters were returned.
Figure 10.28 visualizes the grandchildren split, the initial five-cluster request, and the four-cluster result. section 10.5.4
