Reducing calculations by preparation beforehand.
How it works:
- Organize samples as subsets in a tree structure
- Use a few params to represent a subset (node)
- Compare with nodes instead of all samples
- Only compare with individual samples at the end nodes
Symbols:
: sample subset of node : number of samples in : sample mean of : the farhest distance in from its center : record on the current nearest distance
In here, our goal is to find a point that is closer than
Rule 1:
- For new sample
and node , if , then the nearest neighbor of cannot be in . - In the drawing below, the two circles are mutually exclusive. It is obvious that
is the closest neighbor. Drawing 2025-10-11 16.40.56.excalidraw
⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’
Excalidraw Data
Text Elements
Link to original
Rule 2: - For new sample
and training sample , if , then is not the nearest neighbor of . - Basically, if you subtract the distance between
with and with , it is greater than . This means that is still the closest neighbor.