A radius turns a distance from a center into a boundary. For an SS-tree node, the center is its centroid and the radius must be large enough to enclose its points. Together they define a spherical bounding envelope used in similarity search. Unlike an R-tree’s rectangular envelope, a sphere needs just a center and radius to describe its extent. section 10.3
To update an envelope after insertion, first recompute its centroid from its entries. For a leaf, set the radius to the greatest distance from that centroid to an included point. For an internal node, each child already covers a region: its reach from the parent’s centroid is bounded by the distance between centroids plus the child’s radius. Take the maximum of those values across children. section 10.3.3 section 10.3
Listing 10.10 The SsNode:: updateBoundingEnvelope method
function SsNode::updateBoundingEnvelope() #1
points ← this.getCentroids() #2
for i in {0..k-1} do #3
this.centroid[i] ← mean{point[i] for point in points} #4
this.radius ←
max{distance(this.centroid, entry)+entry.radius for entry in points} #5
The update procedure shows the centroid calculation followed by the maximum-distance-plus-child-radius rule. section 10.3.3
That maximum is a covering guarantee, not a claim that the sphere is as small as possible. A radius measured from the cluster’s center of mass can exceed the radius of the smallest enclosing sphere, whose center may lie elsewhere. Moving the center toward a farthest point offers an approximation, but the detailed algorithm is deferred. Ellipsoids offer another response to skewed data, at the cost of a harder directional-radius calculation during search. section 10.5.2
When an insertion expands a sphere
Adding a point to a leaf moves its centroid and can enlarge its radius enough for its envelope to overlap another leaf. If the leaf is full, insertion instead splits it; choosing the coordinate direction of greatest variance helps avoid unnecessarily large, overlapping spheres. The new envelopes and their ancestors then need updated centroids and radii. section 10.3.2 section 10.3.3
Radius can also be a fixed neighborhood threshold rather than a computed covering distance. In DBSCAN, inspect the points within radius ε of each point. A point with enough neighbors becomes a core point; its neighbors join the current cluster, and core points can extend that cluster through further neighborhoods. A non-core point does not extend it. section 12.3.2
