Ss-tree

Suppose an image collection is too large to compare every image with a query. Represent each image as a multidimensional feature vector, then index those vectors for similarity search. An SS-tree (similarity search tree) groups nearby points in a hierarchy of bounding spheres. It supports exact point lookup, nearest-neighbor search, and region queries; approximate similarity search can trade result quality for speed. section 10.3.1 section 10.4 section 10.6

An SS-tree resembles an R-tree, but uses hyper-spheres rather than axis-aligned bounding rectangles. Points live in leaves; internal nodes contain child spheres. Each node stores a centroid and a radius that bound its contents. The tree’s minimum and maximum occupancy settings, m and M, govern when nodes need splitting or repair. Spheres can overlap, so a query may have to explore several branches. section 10.3 section 10.3.2

The main operations follow from those bounding regions:

• Exact search tests whether the target lies within each child sphere, descends into every qualifying branch, and compares points at leaves. Overlap means there may be more than one qualifying branch. section 10.3.1
• Insertion follows just one branch at each level: the child whose centroid is closest to the new point. Update bounding spheres on the way back. If a node overflows, split it; a split can propagate upward and create a new root. This quick branch choice can enlarge a sphere even when another leaf already covers the point. section 10.3.2
• To split, find the coordinate with greatest variance, sort entries on that coordinate, and choose an occupancy-valid division that minimizes the two groups’ combined variance. The entries are points at a leaf and child centroids at an internal node. section 10.3.4
• Deletion searches all spheres that could contain the point. After removal, an underfilled node may borrow an entry from a sibling or merge with one; bounding spheres must then be updated. Unlike a k-d tree initialized on static data, an SS-tree can maintain balance through dynamic insertions and removals. section 10.3.5

For nearest-neighbor search, visit promising spheres first—typically in order of their minimum possible distance to the query. The first leaf supplies a candidate distance; each closer point tightens it. A branch can be pruned when its minimum possible distance exceeds the best distance found. For a sphere, that lower bound is zero when the query is inside it, or the distance to its boundary otherwise. section 10.4.1

function nearestNeighbor(node, target, (nnDist, nn)=(inf, null))      #1
  if node.leaf then                                                   #2
    for point in node.points do                                       #3
      dist ← distance(point, target)                                  #4
      if dist < nnDist then                                           #5
        (nnDist, nn) ← (dist, point)                                  #5
  else                                    
    sortedChildren ← sortNodesByDistance(node.children, target)       #6
    for child in sortedChildren do                                    #7
      if nodeDistance(child, target) < nnDist then                    #8
        (nnDist, nn) ← nearestNeighbor(child, target, (nnDist, nn))   #9
  return (nnDist, nn)                                                 #10

The nearest-neighbor pseudocode shows candidate updates at leaves and distance-bound pruning before descending into children. section 10.4.1

Choose the index for the data, not just its dimensions. Spherical bounds suit roughly spherical, uniformly spread clusters; rectangular bounds can work better for skewed data. SS-trees can outperform k-d trees in some higher-dimensional or dynamic settings, but overlap can force traversal of every leaf. Search, insertion, deletion, and similarity queries therefore have linear worst-case running time, despite the single-path insertion descent. section 10.5.1 section 10.6 section 10.3.2