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.
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.
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. 2. 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) — more general patterns this builds on
-
BK-tree is a kind of Metric Prime
The proposed strict upward parent is
prime:metric.
Hierarchy path (1) — routes to 1 parentless root
- BK-tree → Metric → Function (Mapping)
Neighborhood in Abstraction Space¶
BK-tree sits in a moderately populated region (45th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Ambient Structures & Local Geometry (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-09-08