BK-tree

In the list of the hundred thousand most common leaked passwords, qwerty123 is number 310. Within one edit of it are eight more passwords from the list: Qwerty123, qwert123, qwerty12, qwerty1234, qwerty13… Whoever guesses passwords starts with exactly these: a common word and one or two edits. To find all words of a dictionary within k edits of a given one, you do not have to compare it with all of them: if the dictionary is put into a BK-tree, for qwerty123 with one edit 722 comparisons out of 99,999 are enough. Type your own word, but not a real password.

At the top are the children of the root by their distance from it, at the bottom the whole tree: the width of a piece is how many words lie under it. Light is what was compared with the query, grey what was thrown away without being opened. Try a long phrase like correcthorsebatterystaple: it is 25 edits from the root 123456, and all the root's children lie at most 19 away, so the tree throws out the whole list in one comparison. And try three edits: more than a third turns light.

The idea

The edit distance, the smallest number of insertions, deletions and substitutions of letters, behaves like a true distance: it is zero only for identical words, it is symmetric, and it obeys the triangle inequality: d(a, c) ≤ d(a, b) + d(b, c), since the edits from a to b and from b to c together turn a into c.

Take any word as the root. Arrange the rest by their distance to it: on edge 1, the subtree of words one edit from the root; on edge 2, two edits; and so on. In each subtree repeat the same with its first word. Everything is built one word at a time: a new word goes down from the root, computes the distance d at each node and follows edge d; if there is no such edge, it becomes a new child. This is the BK-tree, named after Burkhard and Keller.

If the query is at distance d from a node, the words under edge e are no closer to the query than |d − e|. So for a search within k edits it is enough to go down only the edges with e from d − k to d + k; the other subtrees are thrown away whole, unopened.

The same walk finds the nearest neighbour too: the radius is the distance to the best word found so far, and it shrinks as the search goes on; nodes are conveniently taken from a queue by the lower bound |d − e|. But the gain is more modest here: on 6156 names of cities of a hundred thousand people and more, a search for the name nearest to one with one to three typos compares 27 % of the names on average.

The tree requires nothing of the distance beyond these three properties. The Hamming distance between perceptual hashes of pictures, the number of differing bits, is a metric too, and BK-trees are used to find similar photographs. What matters is only that the values are small integers: otherwise a node has too many different edges.

Code

The tree is kept in two lists: a node's word and a dictionary “distance → child”. The listing takes the 10,000 most common passwords: in Python each insertion costs a dozen or two comparisons with a full table, and a hundred thousand words would take almost nine seconds to build. The scene above builds the tree from all 99,999 the same way, in order of frequency.

What it costs

Here the BK-tree has no neat bound, and that is the main thing to know about it. Pruning works when distances to a node are varied and the window [d − k, d + k] is narrow. Short passwords have their distances bunched together: from the root 123456 almost forty thousand words lie at distance 6, and more than ninety thousand from 5 to 8. A window of width 2k + 1 at k = 2 takes in almost everything.

These are a hundred queries, common passwords with one random edit, to a tree of 99,999 passwords. The depth of the tree is 40. The measurement below compares the tree with comparing against everything, at a limit of two edits.

On a hundred thousand passwords a search within one edit is almost six times faster than brute force in Go, and within two less than one and a half times, and on small dictionaries the tree even loses to brute force: the walk and the edge dictionaries cost more than the comparisons saved. For two or more edits on short words, look at techniques that do not go through the dictionary at all, symmetric deletion and a Levenshtein automaton over a trie, from the article on edit distance.

Easy mistakes

• Not a metric. If a “distance” breaks the triangle inequality, pruning can throw away a true neighbour. This is how the simplified distance with transpositions of neighbouring letters behaves, where a transposed pair cannot be edited afterwards: by it CA is three edits from ABC, while via AC it is one plus one. The full Damerau–Levenshtein distance is a metric, and the tree works with it.
• The window on the wrong side. You have to go down the edges in [d − k, d + k], not merely those below d + k: with d = 10 and k = 1 edge 3 is certainly not needed.
• Duplicates. A word at distance 0 from a node is the same word. It is not hung as a child on edge 0, otherwise the search will find duplicates.
• Insertion order. The tree depends on the order of the words: a dictionary sorted alphabetically gives long chains of similar words and a deep tree. Frequency order or random order is better.
• Recursion. The depth of the password tree is 40, but an unlucky insertion order can give a thousand. A walk with its own stack is safer.

Where it is used

Typo correction and suggestions for one edit; finding similar pictures by the Hamming distance between 64-bit perceptual hashes, where distances from 0 to 64 are more varied than for short words; checking whether a new password is a couple of edits from a leaked one. In general, any integer metric where all neighbours within a small radius are needed and the properties of the space are unknown. Numbers and points have trees of their own: the k-d tree, and for real-valued metrics, vantage-point trees.

History

Walter Burkhard and Robert Keller described this tree in 1973 in the paper “Some approaches to best-match file searching” in Communications of the ACM, among several ways of finding in a file the key nearest to a query under any integer metric. The idea of arranging data by distances to chosen points later became the basis of a whole family of metric trees, vantage-point trees and M-trees. A set of ten million leaked passwords was published in 2015 by the security researcher Mark Burnett; the hundred thousand most common of them are in the open SecLists list.

Problems

The neighbours of a password: how many words of the dictionary lie within k edits of a query, and which of them is the most common.