BK-tree¶

Index objects in a discrete metric space by recursively grouping equal pivot distances, then use the triangle inequality to restrict a radius query to only child distances that can contain a match.

Version: v3 · 2026-09-19 · History
Domain-specific #: 1389
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Metric Indexing, Exact Similarity Search → Computer Science & Software Engineering

Core Idea¶

A BK-tree is a rooted metric index in which a node containing pivot (p) has at most one child edge labeled by each distance value (k), and every object in that child's subtree was routed by recursive comparisons beginning with (d(p,x)=k). For a query (q) at radius ®, compute (a=d(q,p)). If a descendant first entered the child labeled (k), the triangle inequality gives \(|a-k|\le d(q,x)\); therefore only labels \(k\in[a-r,a+r]\) can contain an object within radius ®. Recursing only through that interval gives correctness-preserving pruning rather than a heuristic omission.

How would you explain it like I'm…

Word Drawers by Distance

Imagine a big box of words and one boss word at the top. Every other word goes into a drawer numbered by how many letter changes it takes to turn the boss word into it. Inside each drawer, a new boss word sorts the rest the same way. When you look for words close to your word, you only open drawers whose numbers are near your own number, and you can safely skip the rest because they can't hold a close word.

Close-Match Finder Tree

A BK-tree is a way to store things, like words, so you can quickly find ones that are similar. It needs a distance, such as how many letters you must change to turn one word into another. Pick one word as the root. Each other word goes into the branch labeled by its distance from the root, and each label is used only once per word; inside that branch the same rule repeats with a new starting word. To find all words within, say, 2 changes of your word, measure your word's distance to the root, then only follow branches whose labels are within 2 of that number. Because of a rule about distances, the skipped branches truly cannot contain a match, so nothing is missed.

Metric Tree With Exact Pruning

A BK-tree is an index for objects measured by a metric, a distance that obeys the triangle inequality (going through a third point is never shorter than going direct). Each node holds a pivot object, and its child branches are labeled by exact distance values, with at most one child per value. A new object is inserted by computing its distance k to the pivot and descending into the child labeled k, repeating until it finds an empty spot. For a query q with radius r, compute a = d(q, pivot); the triangle inequality guarantees that any object in branch k is at least |a - k| away from q, so only branches with k between a - r and a + r can contain matches. Skipping the others is exact pruning, not a guess, which is what distinguishes a BK-tree from approximate nearest-neighbor methods. A classic use is spell-checking with edit distance.

A BK-tree is a rooted metric index: each node stores a pivot p and has at most one outgoing edge per integer (or discrete) distance label k, and every object in the subtree under label k first entered it because d(p, x) = k. Insertion walks from the root, computing the distance to each pivot and following or creating the matching labeled edge. Range search for query q and radius r computes a = d(q, p) at each visited node; by the triangle inequality, any x under label k satisfies d(q, x) >= |a - k|, so only labels in the interval [a - r, a + r] can hold results, and the pivot itself is reported if a <= r. This is correctness-preserving pruning: exact results are guaranteed as long as d is a true metric, labels are exact pivot distances rather than ranges, sibling labels are unique, and every admissible branch is visited. Violating any of these, for instance by capping how many branches are searched, silently turns exact search into approximation. Typical uses include spelling suggestion and similarity or duplicate search under edit distance or other discrete metrics, though how much pruning helps depends on the data and the radius.

Scope of Application¶

BK-tree applies when the analyst can specify a finite collection of objects in a discrete metric space ((X,d)), stored one object per node with integer- or discrete-valued child-edge labels and establish that node values are metric objects, outgoing labels at one node are distinct exact pivot distances, insertion recurses through the matching label, and queries retain every child label allowed by the triangle-inequality interval. The entry treats the exact Burkhard–Keller metric index. It does not promise logarithmic time, prescribe an implementation language, or characterize arbitrary similarity search.

Clarity¶

A clear claim names the carrier, governing rule, assumptions, and recognition test. This matters because metric tree can name several incompatible data structures, and approximate string matching can describe either exact retrieval within a nonzero edit radius or a deliberately inexact algorithm. The disciplined statement is that the object counts as BK-tree exactly when node values are metric objects, outgoing labels at one node are distinct exact pivot distances, insertion recurses through the matching label, and queries retain every child label allowed by the triangle-inequality interval

Manages Complexity¶

The abstraction compresses edit, Hamming, and other discrete metrics; iterative and recursive implementations; duplicate buckets; bulk and online construction; range and nearest-neighbor query wrappers; and post-retrieval ranking into a stable carrier, rule, invariant, and failure boundary. It makes comparison tractable while retaining the variables that control validity.

Abstract Reasoning¶

Type the carrier. Establish a finite collection of objects in a discrete metric space ((X,d)), stored one object per node with integer- or discrete-valued child-edge labels and reject examples from a different problem.
Lock the rule. Express that node values are metric objects, outgoing labels at one node are distinct exact pivot distances, insertion recurses through the matching label, and queries retain every child label allowed by the triangle-inequality interval independently of one notation or implementation.

Knowledge Transfer¶

Transfer within metric indexing is strong when new cases preserve the same carrier, mechanism, and diagnostic. The move from Insert the words book, books, cake, boo, boon, cook, cape, and cart using Levenshtein distance. If book is the root, every first-level child is keyed by its exact edit distance from book; later words recurse under the already existing equal-distance child. to A dictionary service searches for every stored token within edit distance two of a misspelling and returns all exact matches before ranking them by a separate language model. demonstrates that continuity.

Relationships to Other Abstractions¶

Current abstraction BK-tree Domain-specific

Parents (1) — outgoing typed relations

BK-tree is a kind of Metric Prime

The triangle inequality of a genuine metric is constitutive both to the stored edge labels and to safe query pruning; What makes it its own entry: the equal-pivot-distance recursive partition and its annular triangle-inequality query test, not a generic search tree or any approximate-neighbor implementation.

Hierarchy path (1) — routes to 1 parentless root

BK-tree → is a kind of Metric → is a kind of Function (Mapping)

Neighborhood in Abstraction Space¶

BK-tree sits in a crowded region of the domain-specific corpus (27^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Metric Space Foundations (9 abstractions)

Nearest neighbors

Triangle inequality — 0.90
Positively separated sets — 0.90
Ultrametric space — 0.90
Gromov's compactness theorem (geometry) — 0.89
Covering number — 0.89

Computed from structural-signature embeddings · 2026-10-25