liveBook · Manning

Hypersphere

As explained in Advanced Algorithms and Data Structures

A hypersphere is the set of points at a fixed distance from a center in a Euclidean space of arbitrary dimension.

Suppose you have a candidate nearest neighbor for a target point, but other branches of a spatial index remain unexplored. Draw a circle centered on the target with a radius equal to the candidate’s distance. In higher dimensions, the corresponding boundary is a hypersphere: points at a fixed distance from a center. For searching, the important region is everything within that radius—any closer point must lie there. section 9.3.5

Two search structures use that geometry differently:

  • In a k-d tree, search the branch on the target’s side of each split first. On backtracking, search the other branch if the target’s distance to the split is less than the current nearest-neighbor distance. A closer point shrinks the radius and may rule out further branches. section 9.3.5
  • In an SS-tree, hyperspheres bound groups of nearby points or child spheres. Unlike an R-tree’s hyper-rectangles, these envelopes are symmetric in every direction; they can waste space when the data extends farther in some directions than others. section 8.3 section 10.5.1

When backtracking matters

A k-d tree can direct a query to one side of a split even though its true nearest neighbor lies on the other side. If the current search radius reaches across that split, the other branch still needs checking. Finding a closer point there reduces the radius for subsequent checks. section 9.3.5

Figure 9.21 The second step, after an unsuccessful search, is to backtrack to check other branches of the tree for closer points. It is possible to have such points because when we traverse the tree, we cycle through the coordinates that we compare at each level, so we don’t always go in the direction of the closest point, but we are forced to go on one side of the pivot, depending only on a single coordinate. This means it is possible that the nearest neighbor is on the wrong side of the pivot with respect to our target point P. In this example, when we reached D, since it creates a vertical split, we needed to move to the left, as shown in figure 9.20. Unfortunately, the target point P and its nearest neighbor lie on opposite sides of the split line for D. So, once we reach the end of the path, we need to backtrack to check other branches.

The figure shows why following only the target’s side of each k-d tree split can miss its nearest neighbor. section 9.3.5

Shape matters when choosing a bounding envelope. A spherical cluster can fit a hypersphere with less empty space than a surrounding hyper-rectangle, and a hypersphere is efficient to store and measure distance to. For unevenly shaped data, a hyper-rectangle may fit more tightly. High dimensions make this trade-off harder: enclosing a hypercube in a hypersphere wastes rapidly growing volume, while distances to different neighbors can become nearly indistinguishable. Hypersphere-based pruning is therefore useful, but it does not guarantee a small search; a k-d tree query can still visit the whole tree. section 10.5.1 section 12.2.2 section 9.3.5

How Advanced Algorithms and Data Structures covers it

How deep it goes
Explains split-distance checks and compares bounding shapes, without deriving hypersphere geometry.
Examples
Uses a k-d tree query that must revisit another branch and high-dimensional clusters that fit spherical bounds poorly.
What it assumes
Assumes familiarity with points, coordinates, distances, and tree branches; introduces the higher-dimensional circle analogy.
What you can do after
Diagnose/debug with it why a nearest-neighbor search must revisit a branch, and evaluate when spherical bounds waste space.
How it connects
Connects k-d trees, SS-trees, R-trees, nearest-neighbor search, clustering, and the curse of dimensionality.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.