Lesson plan

BK-tree

A BK-tree (short for Burkhard-Keller tree) is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller specifically adapted to discrete metric spaces. For simplicity, given a way to measure the distance between any two elements of a set, a BK-tree is built with a single root node and several subtrees, each connected to the root as a child. All nodes in a subtree have an equal distance to the root node, and the edge weight of the edge connecting the subtree to the root is equal to the distance. As shown in the picture. Also, each subtree of a BK-tree is a BK-tree. BK-trees can be used for approximate string matching in a dictionary . The problem is formulated as follows: Given a pattern string P = p_1p_2...p_m and a text string T = t_1t_2\dots t_n , we need to find a substring T_{j',j} = t_{j'}\dots t_j in T , which, of all substrings of T , has the smallest edit distance to the pattern P . An ordinary way using BK-tree is to insert all \Theta(n^2) substrings of T and the pattern string P into the BK-tree, and find the subtree containing nodes with the smallest distance from the root. This will lead to a time complexity of \Theta(n^2 \log n) . However, this algorithm is very accurate and can find every substrings with the smallest edit distance to P .

Back to article

Article summary

A BK-tree (short for Burkhard-Keller tree) is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller specifically adapted to discrete metric spaces. For simplicity, given a way to measure the distance between any two elements of a set, a BK-tree is built with a single root node and several subtrees, each connected to the root as a child. All nodes in a subtree have an equal distance to the root node, and the edge weight of the edge connecting the subtree to the root is equal to the distance. As shown in the picture. Also, each subtree of a BK-tree is a BK-tree. BK-trees can be used for approximate string matching in a dictionary . The problem is formulated as follows: Given a pattern string P = p_1p_2...p_m and a text string T = t_1t_2\dots t_n , we need to find a substring T_{j',j} = t_{j'}\dots t_j in T , which, of all substrings of T , has the smallest edit distance to the pattern P . An ordinary way using BK-tree is to insert all \Theta(n^2) substrings of T and the pattern string P into the BK-tree, and find the subtree containing nodes with the smallest distance from the root. This will lead to a time complexity of \Theta(n^2 \log n) . However, this algorithm is very accurate and can find every substrings with the smallest edit distance to P .

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.