KD-tree and ball-tree nearest-neighbour search uses a hierarchy of enclosing regions to find nearby data points while skipping groups that cannot contain a better answer. For a quant searching a library of historical market states, the benefit is computational: retrieve close feature vectors without necessarily comparing the query with every stored record.
The tree is an index, not a prediction rule. K-nearest neighbors regression or classification can use its results, but the tree itself returns point identities and distances. No outcome labels are needed to build a Euclidean search index.
The shortcut needs a certificate
Suppose a search has already found a candidate at distance from query . A node encloses every point in one branch. Compute a lower bound on the distance from to any point in that enclosure. If , the whole branch can be pruned: even its closest possible point is farther away than the candidate.
A small lower bound does not establish that a good neighbour exists. The enclosure may contain empty space. It merely means the branch cannot yet be ruled out. Search promising branches first, update the best candidate, and revisit other branches whose bounds still allow improvement. This is the branch-and-bound logic described in Omohundro's ball-tree report.
Consider four synthetic, one-dimensional feature coordinates: 0, 2, 5 and 9. Use ordinary Euclidean distance, query , and request one nearest neighbour. A split at 3.5 groups 0 and 2 on the left, and 5 and 9 on the right.
Search the right group first. Its distances are 1 and 5, so keep coordinate 5 with current radius . The left group's tight enclosing interval runs from 0 to 2. Its nearest possible location to the query is its right endpoint, giving
Skip that group. For an independent exhaustive check, distances to coordinates 0, 2, 5 and 9 are respectively 4, 2, 1 and 5: the exact nearest neighbour is indeed 5.
The current radius spans coordinates 3 to 5. The left-node enclosure ends at 2, so it cannot contain a closer point or a tied nearest neighbour.
The interval here encloses the node's actual data. It is tighter than the entire half-line below the split at 3.5; using that half-line alone would give a bound of only 0.5 and would not justify this prune. Different valid enclosures can therefore produce different amounts of search work without changing the exact answer.
Boxes and balls encode different bounds
A KD-tree splits points using a coordinate axis and a threshold, recursively creating a binary hierarchy. The original construction appears in Bentley's 1975 paper. For a Euclidean search, an axis-aligned box with lower coordinates and upper coordinates gives the bound
Each coordinate contributes zero when the query lies inside that coordinate's interval, or its distance to the nearer endpoint otherwise. A compact box around the stored points can be more informative than the larger partition cell. SciPy exposes this distinction through its
compact_nodes option.A ball tree encloses a node's points inside a ball with centre and radius . Under Euclidean distance, the triangle inequality gives
For the same left group, a one-dimensional ball with centre 1 and radius 1 is the interval from 0 to 2, so it gives the same bound of 2. In higher dimensions, balls and boxes have different shapes. Ball-tree sibling enclosures can overlap; being inside one child does not eliminate the need to check the other. Omohundro discusses this difference explicitly. Neither shape is uniformly best for every data geometry.
Exactness, ties and approximation are separate choices
For requested neighbours, retain the best candidates found so far. Once there are , the pruning radius is the distance to the worst retained candidate, not the closest one. In the example, the two nearest coordinates are 5 and 2, at distances 1 and 2; the one-neighbour prune cannot simply be reused unchanged for a two-neighbour request.
The strict rule excludes both improvements and ties. At equality, a node might contain another point at the same distance. If any one minimiser is acceptable, equality can be skipped after finding one. If the result must include every tie, or follow an identity-based tie-break, equality needs further consideration. Exact distance does not by itself specify which tied record is returned.
Approximate search relaxes the result requirement. With Euclidean
p=2 and eps=0, SciPy's KDTree.query performs exact search. For a nonnegative eps, its documented approximation guarantee bounds the returned kth-neighbour distance by times the true kth-neighbour distance. This is a distance guarantee, not a promise of identical neighbour identities or prediction accuracy. A finite distance_upper_bound also restricts eligible results; missing neighbours are reported with infinite distance and a sentinel index.Faster lookup does not fix an unsuitable geometry
Pruning works when many enclosures are clearly farther away than the retained candidates. With high dimension, large requested neighbourhoods or overlapping enclosures, a search may inspect much of the dataset. A balanced tree does not guarantee sublinear exact nearest-neighbour query time. The scikit-learn algorithm guide discusses these dependencies and the trade-off between construction cost and repeated queries. Benchmark total build-and-query time against brute force on the actual workload; the four-point example demonstrates correctness, not a speed advantage.
The curse of dimensionality also affects whether retrieved neighbours are meaningfully similar. Feature units and transformations define the geometry: a fast exact answer to an unsuitable distance measure remains unsuitable. For the separate prediction problem, k-Nearest Neighbours and the Curse of Dimensionality develops the regression and classification rules (membership; public preview).
For historical analogue retrieval, restrict the index to records eligible at the query time and fit learned scaling using training data only. Otherwise, faster search can faithfully retrieve information that creates look-ahead bias. The index accelerates the specified search; it does not establish economic relevance or forecast skill.
Sources
- Jon Louis Bentley (1975), Multidimensional Binary Search Trees Used for Associative Searching, §2 and §4.2. The nearest-neighbour section includes an editorial note referring to a modified algorithm; its historical empirical timing claims are not worst-case guarantees.
- Stephen M. Omohundro (1989), Five Balltree Construction Algorithms, “Balltrees” and “Queries which use Branch and Bound,” printed pp. 2–3 and 5–6.
- SciPy,
KDTree, parameters and notes, andKDTree.query, exact/approximate query parameters and return conventions. Documentation checked 1 November 2026. - scikit-learn, Nearest Neighbor Algorithms, KD-tree, ball-tree and algorithm-choice sections. Documentation checked 1 November 2026.