BK-tree

A BK-tree (Burkhard–Keller tree) is a tree-based data structure for searching elements in a discrete metric space. It was introduced by Walter Austin Burkhard and Robert M. Keller in 1973.

BK-trees organize elements according to a distance function that satisfies the properties of a metric, including the triangle inequality. They are commonly used for approximate string matching, spell checking, and similarity searches over dictionaries.

When strings are stored in a BK-tree, Levenshtein distance is a commonly used metric. It measures the minimum number of single-character insertions, deletions, and substitutions needed to transform one string into another.

Structure

A BK-tree consists of a root node and zero or more child nodes. Each node stores an element of the metric space.

For every parent-child relationship, the connecting edge is labeled with the distance between the element stored in the parent and the element stored in the child.

If u is a parent node and v is a child node, the edge label is:

$k=d(w_u,w_v)$

where:

• $d$ is the distance function;
• $w_u$ is the element stored at node u;
• $w_v$ is the element stored at node v;
• $k$ is the edge distance.

For any given parent node, outgoing edges have distinct distance labels.

A child node may itself be the root of another BK-tree.

It is important to distinguish the distance assigned to an edge from the distance between the root and every descendant.

An edge labeled k identifies a child whose stored element is at distance k from its immediate parent. Elements farther down that child's subtree do not necessarily have distance k from the same parent.

Schematic structure of a BK-tree. Edge labels represent distances between directly connected nodes.

Distance metrics

The structure requires a distance function satisfying the metric properties:

Non-negativity

$d(x,y)\ge 0$

Identity of indiscernibles

$d(x,y)=0⟺x=y$

Symmetry

$d(x,y)=d(y,x)$

Triangle inequality

$d(x,z)\le d(x,y)+d(y,z)$

The triangle inequality is essential because it makes it possible to exclude subtrees without examining every stored element.

Levenshtein distance

Levenshtein distance is particularly suitable for BK-trees because the standard, unit-cost version is a metric.

It counts the minimum number of operations required to transform one string into another, where each insertion, deletion, or substitution has a cost of one.

For example:

• d("book","books") = 1
• d("book","boo") = 1
• d("book","cook") = 1
• d("book","cake") = 4

The ability to compare strings using their edit distance makes BK-trees useful for finding words with spelling variations or typographical errors.

Not every string similarity measure can be used directly as a BK-tree metric. In particular, a similarity score must not be assumed to satisfy the triangle inequality merely because it can compare two strings.

Example

An example of a BK-tree constructed using Levenshtein distance.

Consider the following dictionary:

book
books
cake
boo
boon
cook
cape
cart

A possible BK-tree can be constructed by inserting these words sequentially, using standard Levenshtein distance.

Start with:

book

Insert books.

Since:

d(book, books) = 1

the new word becomes a child of book, connected by an edge labeled 1.

Insert cake.

Since:

d(book, cake) = 4

it becomes a child connected to book by an edge labeled 4.

When another word is inserted, its distance to the current node determines which outgoing edge should be followed. If no matching edge exists, a new child is created.

The resulting tree depends on insertion order.

Insertion

Insertion proceeds recursively through the tree.

Let:

• T be the BK-tree;
• w be the element being inserted;
• d be the selected metric.

The procedure is:

1. If the tree is empty, create its root containing w.
2. Otherwise, begin at the root.
3. Calculate the distance between w and the element stored in the current node.
4. If the distance is zero, the element already exists and no new node is required.
5. If an outgoing edge with that distance exists, follow it.
6. Otherwise, create a new child with the calculated edge label.
7. Repeat until the element has been inserted or an existing identical element has been found.

Pseudocode

INSERT(tree, word):

    if tree.root does not exist:
        tree.root = new Node(word)
        return

    current = tree.root

    while true:

        k = distance(word, current.word)

        if k == 0:
            return

        if current.children[k] exists:
            current = current.children[k]

        else:
            current.children[k] = new Node(word)
            return

Here, children[k] identifies the child connected by an edge whose distance label is k.

Approximate lookup

BK-trees support searching for elements within a specified distance threshold.

Let:

• q be the query element;
• r be the maximum permitted distance;
• u be the current node;
• k be the label of an outgoing edge.

First calculate:

$\delta =d(q,w_u)$

A stored element is a valid result if:

$\delta \le r$

By the triangle inequality, only child edges whose labels satisfy the following condition need to be explored:

$|\delta -k|\le r$

Equivalently:

$\delta -r\le k\le \delta +r$

Branches outside this interval can be excluded because they cannot contain a result within the requested radius.

This pruning rule is the fundamental optimization used by BK-tree searches.

Pseudocode

SEARCH(node, query, radius, results):

    if node does not exist:
        return

    delta = distance(query, node.word)

    if delta <= radius:
        results.add(node.word)

    lower = delta - radius
    upper = delta + radius

    for each (edge_distance, child)
        in node.children:

        if lower <= edge_distance
           and edge_distance <= upper:

            SEARCH(
                child,
                query,
                radius,
                results
            )

This algorithm returns the stored elements whose distance from the query does not exceed the requested radius.

Example of approximate lookup

Consider a BK-tree containing the words:

book
books
cake
boo
boon
cook
cape
cart

Suppose the query is:

cool

and the maximum permitted Levenshtein distance is:

radius = 1

At the root containing book:

d(cool, book) = 2

The search therefore explores only outgoing edges labeled from 1 through 3.

A child reached through an edge labeled 4 can be excluded from this particular radius-one search.

When the search reaches cook:

d(cool, cook) = 1

the word satisfies the requested threshold and is added to the result set.

The example illustrates how the triangle inequality allows a BK-tree to avoid unnecessary distance calculations.

Nearest-neighbor search

A BK-tree can also be used to find a nearest stored element rather than all elements within a fixed radius.

In this case, the algorithm maintains the distance of the best candidate found so far.

Whenever a closer candidate is discovered, the current best distance is reduced.

The updated value can then be used for further pruning.

For a search that must return all equally close candidates, branches at the boundary must not be removed merely because their best possible distance equals the current best distance.

The distinction between finding one nearest element and finding all equally close elements should therefore be made explicit when implementing a BK-tree.

Time and space complexity

The performance of a BK-tree depends on several factors:

• The number of stored elements.
• The distribution of distances between elements.
• The insertion order.
• The cost of evaluating the selected distance function.
• The search radius.
• The number of candidate branches explored.

Construction

Inserting n elements requires one or more distance evaluations for each insertion.

The number of visited nodes depends on the shape of the tree and is not guaranteed to be logarithmic.

A highly unbalanced tree can require traversal through many existing nodes.

Lookup

BK-trees can substantially reduce the number of distance evaluations when the metric and data distribution permit effective pruning.

However, there is no universal logarithmic worst-case bound for lookup.

In the worst case, a search may need to visit every stored node.

The pruning efficiency generally decreases when the search radius becomes large relative to distances among stored elements.

Cost of Levenshtein distance

For strings of lengths m and n, the standard dynamic programming algorithm for Levenshtein distance takes:

$O(mn)$

time.

A conventional full-matrix implementation uses:

$O(mn)$

auxiliary space.

If only the distance value is needed, a two-row dynamic programming implementation can reduce auxiliary space to:

$O(\min (m,n))$

These costs apply to a single distance calculation and must be considered separately from the number of tree nodes visited during a search.

Applications

Spell checking

A dictionary can be stored in a BK-tree to retrieve words within a small edit distance of a misspelled query.

Approximate string matching

BK-trees can identify candidate strings that differ from a query by a bounded number of edit operations.

Duplicate detection

A BK-tree can help identify potentially duplicated short textual identifiers, provided the selected distance metric and threshold are appropriate for the application.

Dictionary search

A BK-tree can support approximate lookup in a static or moderately changing dictionary.

Biological sequence comparison

Edit-distance metrics can be applied to biological sequences in suitable applications.

However, domain-specific alignment methods may be more appropriate when substitutions, insertions, deletions, and biological scoring rules need to be modeled differently.

Unicode considerations

When BK-trees are used for natural-language strings, the definition of a character can affect the calculated distance.

Unicode text may be represented using:

• Encoded bytes.
• Unicode code points.
• Grapheme clusters representing user-perceived characters.

For example, a precomposed accented character and a canonically equivalent sequence containing a base character followed by a combining mark may be visually identical while containing different sequences of code points.

Applications may therefore benefit from applying a consistent Unicode normalization policy before constructing the tree and processing queries.

The distance function must also remain consistent across insertion and lookup.

In applications requiring comparison of user-perceived characters, grapheme segmentation may be considered.

The Unicode Standard Annex #15 defines Unicode normalization forms, while Unicode Standard Annex #29 specifies text segmentation rules.

Relationship to Levenshtein distance

A BK-tree and the Levenshtein distance algorithm serve different purposes.

Levenshtein distance calculates the edit distance between two strings.

A BK-tree organizes many stored strings so that distance-based queries can exclude irrelevant branches.

The tree does not replace the distance calculation. Instead, it uses the properties of the metric to reduce the number of candidate comparisons.

The combination is useful for approximate dictionary search, spelling correction, and other applications involving bounded edit distances.

See also

• Levenshtein distance
• Damerau–Levenshtein distance
• Approximate string matching
• Metric space
• Triangle inequality
• Dynamic programming
• Edit distance

References

• ^ W. A. Burkhard and R. M. Keller. Some Approaches to Best-Match File Searching. Communications of the ACM, 16(4):230–236, 1973.

• R. Baeza-Yates, W. Cunto, U. Manber, and S. Wu. Proximity Matching Using Fixed Queries Trees. In Combinatorial Pattern Matching, LNCS 807, 1994.

• ^ R. Baeza-Yates and G. Navarro. Fast Approximate String Matching in a Dictionary. Proceedings of SPIRE, 1998.

• ^ H. Hyyrö. Explaining and Extending the Burkhard–Keller Tree for Fast String Searching. Symposium on String Processing and Information Retrieval, 2003.

• ^ S. Mihov and K. Schulz. Fast Approximate Search in Large Dictionaries. Computational Linguistics, 30(4):451–477, 2004.

• Unicode Standard Annex #15: Unicode Normalization Forms.

• Unicode Standard Annex #29: Unicode Text Segmentation.

External links

• pybktree – Python implementation of BK-trees.
• BK-tree implementation in Common Lisp – Implementation and related performance tests.
• BK-trees and metric spaces – Technical explanation.
• Levenshtein Distance – algorithm overview – Supplementary explanation of the edit-distance metric used in BK-tree searches.