BKtrees

BK-trees, short for Burkhard–Keller trees, are a data structure for efficient similarity search in metric spaces, most commonly used for approximate string matching under edit distance. The structure enables fast querying for all stored strings within a given distance t of a query string, without examining every element.

A BK-tree is a rooted tree. Each node stores a string value. Each edge to a child is labeled with a non-negative integer, representing the distance between the node's string and the child's string, under a chosen metric such as Levenshtein distance. Because the distance is a metric, the triangle inequality holds, which is crucial for pruning during search.

Insertion starts at the root. For a new string w, compute d = dist(w, root.value). If the root has a child edge labeled d, descend into that child and repeat the process. Otherwise create a new child of the root with edge label d and value w. This process recurses down the tree similarly for deeper insertions.

Querying with a string q and radius t proceeds recursively. At a node with value s, compute d = dist(s, q). If d <= t, report s as a match. Then consider each child with edge label r; the child can contain matches only if |d - r| <= t. Therefore, only such children are explored. This pruning is the key efficiency gain.

Applications include spell checkers, fuzzy search, and dictionary lookups where approximate matches are acceptable. BK-trees are particularly suited when the distance metric is a true metric and the dataset is static or slowly changing. Limitations include sensitivity to data distribution, higher thresholds reducing pruning effectiveness, and potential inefficiency for large, rapidly updating collections.