Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

BK-trees: search incident labels within edit distance

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A BK-tree stores one label per node. The edge from a parent to a child is the edit distance between their labels; one parent has at most one child for each edge distance. Insertion follows the appropriate edge until it finds an empty position or a duplicate. A radius query computes the distance d from its target to the current node and explores only child edges e in [d-r,d+r], where r is the requested tolerance. That band follows from the triangle inequality: a subtree attached through a more distant edge cannot contain a qualifying label. The program uses Levenshtein distance over Python code points and sorts matches by distance then label. Its labels are immutable after insertion.

Operational case

A review queue indexes invoice, invoces, invoices, incident, invoker, and voice. A radius-one lookup for invoice returns invoice itself and invoices. A second insertion of invoice returns false rather than creating a duplicate branch. The query must still examine a child at edge distance d+r, because a valid result may lie exactly on the tolerance boundary. Likewise, a node outside the radius does not justify dropping its entire subtree; its child edges may lead back toward the query. Case folding and Unicode normalization are caller decisions: this exact model treats differently encoded labels as different strings.

Working Python program

python
def edit_distance(first_label, second_label):
    previous = list(range(len(second_label) + 1))
    for row, first_letter in enumerate(first_label, 1):
        current = [row]
        for column, second_letter in enumerate(second_label, 1):
            current.append(min(current[-1] + 1, previous[column] + 1,
                               previous[column - 1] + (first_letter != second_letter)))
        previous = current
    return previous[-1]


class IncidentLabelBKTree:
    def __init__(self):
        self.root = None

    def insert(self, label):
        if not label:
            raise ValueError("empty labels are not indexed")
        if self.root is None:
            self.root = {"label": label, "children": {}}
            return True
        node = self.root
        while True:
            distance = edit_distance(label, node["label"])
            if distance == 0:
                return False
            child = node["children"].get(distance)
            if child is None:
                node["children"][distance] = {"label": label, "children": {}}
                return True
            node = child

    def within(self, query, radius):
        if radius < 0:
            raise ValueError("radius must be nonnegative")
        if self.root is None:
            return []
        matches = []
        pending = [self.root]
        while pending:
            node = pending.pop()
            distance = edit_distance(query, node["label"])
            if distance <= radius:
                matches.append((distance, node["label"]))
            for edge, child in node["children"].items():
                if distance - radius <= edge <= distance + radius:
                    pending.append(child)
        return sorted(matches)


if __name__ == "__main__":
    labels = IncidentLabelBKTree()
    for label in ["invoice", "invoces", "invoices", "incident", "invoker", "voice"]:
        labels.insert(label)
    print("near invoice:", labels.within("invoice", 1))
    print("duplicate:", labels.insert("invoice"))

Output

Output
near invoice: [(0, 'invoice'), (1, 'invoices')]
duplicate: False

Time, space, and tradeoff

Computing edit distance between strings of lengths A and B takes O(AB) time and O(B) row space in this implementation. A lookup may visit every stored label, giving O(NAB) worst-case time, and an unbalanced insertion path can do the same. The tree stores O(N) nodes and edges. Small radii and a useful label distribution can prune many branches, but no universal sublinear query guarantee follows from the shape alone. The structure answers approximate whole-label matching; a trie serves exact prefixes, while a trigram index can produce substring candidates that need verification.

Common Mistakes

  • Do not prune the entire subtree merely because its parent label is outside the radius.
  • Do not omit the equality cases at either edge-band boundary.
  • Do not call code-point edit distance locale-aware spelling correction.
  • Do not assume the tree stays balanced after adversarial insertion order.

Connected lessons

Compare its update and query contract with Vantage-point trees: nearest depots by a metric radius, Centroid decomposition: nearest marked depot on a fixed tree, Two-level perfect hashing: exact static case membership, then complete the structure audit and decision quiz.

SimHash bands: find near-duplicate incident fingerprints examines a related structure with a different operation boundary.

data structures
trees-and-heaps
Storage details