THE FOLD / SPAWN / THE SANDBOX / THE BK-TREE
THE BK-TREE
fuzzy string search pruned by the triangle inequality
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The BK-tree (Burkhard–Keller tree) indexes strings for fuzzy search — finding all words within an edit distance k of a query — without comparing against every word. It stores each string as a child of another, labelled by their edit distance; a query then uses the triangle inequality to prune: a child at distance d from its parent can only contain matches whose distance to the query lies in [d−k, d+k], so most branches are skipped.
It is the classic structure behind spell-checkers and approximate matching.
LIT verified live: over 200 random string sets the BK-tree’s within-distance-k results exactly match a brute scan (window.__bktree). FIG no framing; exact search, fewer comparisons.
It is the classic structure behind spell-checkers and approximate matching.
LIT verified live: over 200 random string sets the BK-tree’s within-distance-k results exactly match a brute scan (window.__bktree). FIG no framing; exact search, fewer comparisons.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-sandbox — the spatial playground, but in a metric of edit distance rather than coordinates, beside the k-d tree. The BK-tree is that metric index. AVAN (AI) built the instrument: the edit-distance metric, the distance-labelled tree, the triangle-inequality pruned search, the brute cross-check.
Credit as content: Walter Burkhard & Robert Keller (1973). The weave: David names the sandbox; I index strings by edit distance and let the triangle inequality prune the search, confirming the results match an exhaustive scan.
Credit as content: Walter Burkhard & Robert Keller (1973). The weave: David names the sandbox; I index strings by edit distance and let the triangle inequality prune the search, confirming the results match an exhaustive scan.
3 ONE DIMENSION
A node’s children are labelled by edit distance. Querying at tolerance k, only children whose label lies within [d−k, d+k] of the query’s distance to this node can hold a match — the rest are pruned.
4 TWO DIMENSIONS · INTERACTIVE
A dictionary as a BK-tree; a fuzzy query returns all words within distance k, checked against a brute scan.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the branches within the distance window, searched.
AVAN’s addition (the inverse-companion): organise strings in a tree keyed by edit distance, and use the triangle inequality to prune — a child at distance d from its parent can only hold matches within [d−k, d+k] of the query, so most branches are skipped. The inverse of ‘measure the distance to everything’ is ‘let the metric’s triangle inequality prune the tree.’ Magenta is the strings never compared; green is the branches within the distance window. A metric space indexed for tolerant search.
LIT Genuine BK-tree (Burkhard & Keller 1973). Verified live: the edit-distance-labelled tree with triangle-inequality pruning returns exactly the same within-distance-k result set as a brute scan over all words, across 200 random string sets (window.__bktree.matchesBrute).
FIG No framing: the edit-distance metric, the distance-labelled tree, the triangle-inequality pruned search, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — indexing strings by edit distance lets the triangle inequality prune to children within [d-k, d+k] of the query, so most strings are never compared; magenta is the pruned strings, green the searched branches. A metric space indexed for tolerant search.
FIG No framing: the edit-distance metric, the distance-labelled tree, the triangle-inequality pruned search, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — indexing strings by edit distance lets the triangle inequality prune to children within [d-k, d+k] of the query, so most strings are never compared; magenta is the pruned strings, green the searched branches. A metric space indexed for tolerant search.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SANDBOX · David Lee Wise (ROOT0), with AVAN