Branch-Bound Algorithm

Reducing calculations by preparation beforehand.

How it works:

1. Organize samples as subsets in a tree structure
2. Use a few params to represent a subset (node)
3. Compare with nodes instead of all samples
4. Only compare with individual samples at the end nodes

Symbols:

• ${\mathcal{X}}_p$ : sample subset of node $p$
• $N_p$: number of samples in ${\mathcal{X}}_p$
• $M_p$: sample mean of ${\mathcal{X}}_p$
• $r_p={\max }_{x_i\in {\mathcal{X}}_p}D(x_i,M_p)$: the farhest distance in ${\mathcal{X}}_p$ from its center
• $B$: record on the current nearest distance

In here, our goal is to find a point that is closer than $B$.

Rule 1:

• For new sample $x$ and node ${\mathcal{X}}_p$, if $D(x,M_p)>B+r_p$, then the nearest neighbor of $x$ cannot be in ${\mathcal{X}}_p$.
• In the drawing below, the two circles are mutually exclusive. It is obvious that $x^{\prime }$ is the closest neighbor.

  Transclude of Drawing-2025-10-11-16.40.56.excalidraw

  
  Rule 2:
• For new sample $x$ and training sample $x_i\in {\mathcal{X}}_p$, if $D(x,M_p)>B+D(x_i,M_p)$, then $x_i$ is not the nearest neighbor of $x$.
• Basically, if you subtract the distance between $x$ with $M_p$ and $x_i$ with $M_p$, it is greater than $B$. This means that $x^{\prime }$ is still the closest neighbor.