Ball Tree already showed this site one way to index points with nothing but pairwise distances — no coordinate axis required. A VP-Tree (vantage-point tree) answers the identical question with a different mechanism. A ball tree anchors each split with two far-apart points and a computed centroid; a VP-tree anchors it with exactly one point pulled straight from the data — the vantage point — and splits everything else by whether it's closer than or farther than the median distance to that single point. That one change buys a guarantee Ball Tree's own page never makes: the split is a literal coin-flip on count every time, so the tree's depth is always ⌈log₂ n⌉, regardless of how the data clusters — verified below directly against Ball Tree on the same adversarial input.
This site's BK-tree already builds on the same core idea — partition by distance from a pivot, prune with the triangle inequality — but keys each child by the exact distance value, which only works because small-integer edit distances repeat often enough to make real children. A VP-tree never looks at the raw distance value, only whether it's above or below the median, so the identical two-way split works just as well for continuous, real-valued metrics where BK-tree's per-value child map would degenerate toward one child per point.
Ten points. Press Step or Run to watch the tree get built: each node picks the first remaining point as its vantage point, computes the median distance from it to everything else remaining, and draws that as a dashed circle — the median-distance shell. Points inside the shell recurse into one subtree, points outside into the other. Once the tree is built, the demo switches to a nearest-neighbor query for the square point Q: watch it check each vantage point directly (every node holds a real, checkable data point, not just a routing threshold), track the best distance found so far (dashed circle around Q), and skip a whole subtree the instant that subtree's shell proves nothing inside it can beat the current best.
Building the tree needs only a distance function. Pick any point as the vantage point vp
(the reference implementation below always takes the first remaining point — no farthest-pair search,
no centroid, nothing else to compute). Measure the distance from vp to every other
remaining point, sort those distances, and take the median as mu. Every
point at distance ≤ mu goes into the inside subtree; everything farther
goes into the outside subtree. Because mu is the literal median of the
remaining set, that split always puts (within one element) exactly half the remaining points on each
side — no matter which point got picked as vp, no matter how the data is distributed in
space. Recurse on each half. The resulting tree's depth is always ⌈log₂ n⌉,
a guarantee that comes from counting, not geometry.
Querying leans on the same triangle inequality Ball Tree uses, applied to a single point instead of
two. For a node with vantage point vp, split distance mu, and a query at
distance d from vp: any point in the inside subtree is at
distance ≤ mu from vp, so by the triangle inequality its distance from the
query is at least d - mu. Any point in the outside subtree is at distance
> mu from vp, so its distance from the query is at least
mu - d. If the best distance found so far (bestD) already beats one of those
lower bounds, that whole subtree is safe to skip — the inside subtree only needs visiting when
d - bestD ≤ mu, the outside subtree only when d + bestD ≥ mu. Both
checks run at every node regardless of which side d itself falls on; only the order
(visit whichever side contains d first, to tighten bestD before the other
side's check runs) depends on that. And because every node is a real data point, not just a
routing decision, the vantage point itself is checked as a candidate answer at every single node along
the way — there's no separate leaf layer where "the real points" live, the way Ball Tree's leaves hold
buckets and its internal nodes hold only bounding balls.
function dist(a, b) { return Math.hypot(a[0] - b[0], a[1] - b[1]); }
function buildVPTree(points) {
if (points.length === 0) return null;
const vp = points[0];
const rest = points.slice(1);
if (rest.length === 0) return { vp, mu: 0, inside: null, outside: null };
const dists = rest.map(p => dist(vp, p));
const sorted = [...dists].sort((a, b) => a - b);
const mu = sorted[Math.floor(sorted.length / 2)]; // median distance
const inside = [], outside = [];
rest.forEach((p, i) => {
(dists[i] <= mu ? inside : outside).push(p);
});
return { vp, mu, inside: buildVPTree(inside), outside: buildVPTree(outside) };
}
function nearestNeighbor(root, target) {
let best = null;
let bestD = Infinity;
function visit(node) {
if (!node) return;
const d = dist(node.vp, target);
if (d < bestD) { bestD = d; best = node.vp; } // every node is a real candidate point
if (d < node.mu) {
if (d - bestD <= node.mu) visit(node.inside);
if (d + bestD >= node.mu) visit(node.outside);
} else {
if (d + bestD >= node.mu) visit(node.outside);
if (d - bestD <= node.mu) visit(node.inside);
}
}
visit(root);
return best;
}Only ever descending into the side containing d — wrong 40.1% of the
time. The tempting shortcut: since d < node.mu already tells you which side
the query itself falls on, just recurse into that one side and skip the second check entirely — it
reads like an ordinary binary-search branch. It compiles, it terminates, it returns a point
every time. It's just not reliably the nearest one, because it drops the case where the query is close
to the shell boundary and the other side still has a real point within bestD.
Stress-tested directly: 20,000 trials of random point sets (1 to 30 points each), the reference
implementation above against a brute-force linear scan, then the single-branch version against the
same oracle. The reference implementation matched brute force in all 20,000. The single-branch version
disagreed in 8,030 — 40.1% of the time.
Only checking candidates at leaves — wrong 62.5% of the time. A second, more
specific-to-this-structure bug: porting the mental model from a leaf-bucket structure like Ball Tree,
where only leaves hold real points and internal nodes are pure routing. Skip the
if (d < bestD) candidate check at every internal node and only run it at nodes with no
children, and the search silently stops treating most of the tree's own data as real answers — every
internal vantage point is a real, checkable data point, not a bounding summary. Stress-tested
the same way: 20,000 trials, reference implementation 0 mismatches, leaf-only version wrong in
12,502 — 62.5% of the time, the more damaging of the two bugs since it discards a real
candidate at every single internal node it passes through, not just at one boundary condition.
The balance guarantee is real, not just asymptotic hand-waving. Built both a VP-tree
and this site's own Ball Tree over the same deliberately adversarial input — a tight 2-unit cluster of
points plus one lone outlier 350+ units away, repeated at five sizes — and measured actual tree depth
against the theoretical ideal ⌈log₂ n⌉:
| n | Ideal ⌈log₂ n⌉ | VP-Tree depth | Ball Tree depth |
|---|---|---|---|
| 15 | 4 | 5 | 7 |
| 31 | 5 | 6 | 8 |
| 63 | 6 | 7 | 10 |
| 127 | 7 | 8 | 11 |
| 255 | 8 | 9 | 13 |
VP-Tree's depth stays exactly one level above the theoretical ideal at every size tested — the one extra level comes from the vantage point itself being removed from the count before the median split, not from any imbalance. Ball Tree's farthest-pair anchor split has no such guarantee, and on this clustered-plus-outlier input it shows: 30-60% deeper across the same five sizes. This isn't a claim that Ball Tree is broken — its own page is honest that its split is a heuristic, not a guarantee — it's a direct, measured demonstration of what that difference actually costs on a real adversarial shape.
Anywhere a metric-space nearest-neighbor structure is needed and either a hard depth guarantee matters or the data genuinely can't support a computed centroid — perceptual-hash near-duplicate image search (compare Hamming or similarity distances between hash codes, never raw pixel coordinates), metric-space indexing libraries for arbitrary user-supplied distance functions, and any nearest-neighbor search where the input is embeddings, fingerprints, or other objects with only a distance between them, never a coordinate. First described by Peter Yianilos in 1993 ("Data structures and algorithms for nearest neighbor search in general metric spaces"), independently as "metric trees" by Jeffrey Uhlmann the same year.
Not a replacement for BK-tree on this site's own turf —
BK-tree's own demo works over a fixed small dictionary where exact integer edit-distance buckets stay
genuinely populated, and its per-distance child map makes a range query (≤ k) a single
lookup per level rather than the two-sided bound check a VP-tree needs. VP-tree earns its keep on the
other side of that trade: continuous or large-range metrics where BK-tree's per-value buckets would
mostly hold one point each, and a guaranteed-balanced binary split matters more than distance-value
locality.
Build: each level scans the current remaining set once to compute distances from the
vantage point, sorts to find the median, and partitions — O(n) work per level (the sort
dominates; an unranked quickselect for the median would drop this to true linear-per-level, the same
trade this site's Quickselect page covers, but this reference
implementation keeps the simple sort for clarity). Across the guaranteed O(log n) levels,
that's O(n log n) total, with no dependency on the input's spatial distribution.
Query: O(log n) on typical data, degrading toward O(n) in
the worst case if both branches keep needing a visit at every level (a query sitting exactly on every
shell boundary, or a metric with very little separation between points) — the same shape of worst case
every tree on this page's own Spatial neighbors shares, not something VP-tree escapes. What it does
guarantee, unlike Ball Tree, is that the worst case is bounded by a depth that's fixed at build time,
not one that depends on how badly a bad split happened to cluster the data.
Space: O(n) — one node per input point, no separate leaf-bucket layer.
This site's guide, Choosing a Spatial Structure, compares this entry against the other seven Spatial entries that share the same "index points, query later" question.